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

作者：Hamalainen Wilhelmiina^*

来源：Computational Statistics & Data Analysis, 2016, 93: 469-482.

DOI：10.1016/j.csda.2015.08.002

• Fisher's exact test
• p-value
• Hypergeometric distribution
• Upper bound
• Approximation Dependency rule
• Data mining

In the dependency rule mining, the goal is to discover the most significant statistical dependencies among all possible collapsed 2 x 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 0(n), where n is the data size. The traditional solution is to approximate the significance with the x(2)-measure, which can be estimated in a constant time. However, the x2-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 x(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.

• 出版日期2016-1