Efficient mining of the most significant patterns with permutation testing

The extraction of patterns displaying significant association with a class label is a key data mining task with wide application in many domains. We introduce and study a variant of the problem that requires to mine the top-kstatistically significant patterns, thus providing tight control on the number of patterns reported in output. We developTopKWY, the first algorithm to mine the top-ksignificant patterns while rigorously controlling the family-wise error rate of the output, and provide theoretical evidence of its effectiveness.TopKWYcrucially relies on a novel strategy to explore statistically significant patterns and on several key implementation choices, which may be of independent interest. Our extensive experimental evaluation shows thatTopKWYenables the extraction of the most significant patterns from large datasets which could not be analyzed by the state-of-the-art. In addition,TopKWYimproves over the state-of-the-art even for the extraction ofallsignificant patterns.