New upper bounds for tight and fast approximation of Fisher’s exact test in dependency rule mining

In the dependency rule mining, the goal is to discover the most significant statistical dependencies among all possible collapsed 2×2 contingency tables. Fisher's exact test is a robust method to estimate the significance and it enables efficient pruning of the search space. The problem is that evaluating the required p-value can be very laborious and the worst case time complexity is O(n), where n is the data size. The traditional solution is to approximate the significance with the χ2-measure, which can be estimated in a constant time. However, the χ2-measure can produce unreliable results (discover spurious dependencies but miss the most significant dependencies). Furthermore, it does not support efficient pruning of the search space. As a solution, a family of tight upper bounds for Fisher's p is introduced. The new upper bounds are fast to calculate and approximate Fisher's p-value accurately. In addition, the new approximations are not sensitive to the data size, distribution, or smallest expected counts like the χ2-based approximation. In practice, the execution time depends on the desired accuracy level. According to experimental evaluation, the simplest upper bounds are already sufficiently accurate for dependency rule mining purposes and they can be estimated in 0.004-0.1% of the time needed for exact calculation. For other purposes (testing very weak dependencies), one may need more accurate approximations, but even they can be calculated in less than 1% of the exact calculation time.