Computing exact permutation p-values for association rules

Association rule mining is an important task in the field of data mining, and many efficient algorithms have been proposed to address this problem. However, a large portion of the rules reported by these algorithms just satisfy the user-defined constraints purely by accident, and those that are not statistically meaningful should be filtered out through statistical significance testing. In the context of association rule discovery, the permutation-based approach can achieve better performance than other competitive methods, although several drawbacks of this effective approach narrow its usability. In this paper, we provide an analysis of these disadvantages and propose an algorithm called Exact Permutation p-values for Association Rules (EPAR) to calculate the exact p-values of all tested rules. Experiments on different types of data sets demonstrate that EPAR can successfully alleviate the disadvantages and outperform the direct permutation-based method over several performance measures.