An efficient rigorous approach for identifying statistically significant frequent itemsets

ABSTRACT

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work, we address significance in the context of frequent itemset mining. Specifically, we develop a novel methodology to identify a meaningful support threshold s^* for a dataset, such that the number of itemsets with support at least s^* represents a substantial deviation from what would be expected in a random dataset with the same number of transactions and the same individual item frequencies. These itemsets can then be flagged as statistically significant with a small false discovery rate.

Our methodology hinges on a Poisson approximation to the distribution of the number of itemsets in a random dataset with support at least s, for any s greater than or equal to a minimum threshold s_min. We obtain this result through a novel application of the Chen-Stein approximation method, which is of independent interest. Based on this approximation, we develop an efficient parametric multi-hypothesis test for identifying the desired threshold s^*. A crucial feature of our approach is that, unlike most previous work, it takes into account the entire dataset rather than individual discoveries. It is therefore better able to distinguish between significant observations and random fluctuations. We present extensive experimental results to substantiate the effectiveness of our methodology.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, A new framework for itemset generation, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.18-24, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275490]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: R. Arratia, L. Goldstein, and L. Gordon. Poisson approximation and the Chen-Stein method. Statistical Science, 5(4):403--434, 1990.
• 4: Y. Benjamini, and Y. Hochberg. Controlling the false discovery rate. J. Royal Statistical Society, Series B, 57:289--300, 1995.
• 5: Y. Benjamini, and D. Yekutieli The control of the false discovery rate in multiple testing under dependency Annals of Statistics, 29 (4): 1165--1188, 2001.
• 6: Richard J. Bolton , David J. Hand , Niall M. Adams, Determining Hit Rate in Pattern Search, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.36-48, September 16-19, 2002
• 7: W. J. Conover. Practical Nonparametric Statistics. Wiley Series in Probability, 3rd Ed., 1999.
• 8: S. Dudoit, J.P. Shaffer, and J.C. Boldrick. Multiple hypothesis testing in microarray experiments. Statistical Science, Vol. 18, No. 1, 2003, p. 71--103.
• 9: W. DuMouchel. Bayesian data mining in large frequency tables, with an application to the FDA spontaneous reporting system. The American Statistician, 53:177--202, 1999.
• 10: William DuMouchel , Daryl Pregibon, Empirical bayes screening for multi-item associations, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.67-76, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502526]
• 11: Aristides Gionis , Heikki Mannila , Taneli Mielikäinen , Panayiotis Tsaparas, Assessing data mining results via swap randomization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150424]
• 12: B. Goethals, R. Bayardo, and M.J. Zaki, editors. Proc. of the 2nd Workshop on Frequent Itemset Mining Implementations (FIMI04), volume 126. CEUR-WS Workshop On-line Proceedings, November 2004.
• 13: B. Goethals and M. J. Zaki, editors. Proc. of the 1st Workshop on Frequent Itemset Mining Implementations (FIMI03), volume 90. CEUR-WS Workshop On-line Proceedings, November 2003.
• 14: Wilhelmiina Hämäläinen , Matti Nykänen, Efficient Discovery of Statistically Significant Association Rules, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.203-212, December 15-19, 2008 [doi>10.1109/ICDM.2008.144]
• 15: Jiawei Han , Hong Cheng , Dong Xin , Xifeng Yan, Frequent pattern mining: current status and future directions, Data Mining and Knowledge Discovery, v.15 n.1, p.55-86, August 2007 [doi>10.1007/s10618-006-0059-1]
• 16: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 17: Szymon Jaroszewicz , Tobias Scheffer, Fast discovery of unexpected patterns in data, relative to a Bayesian network, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081887]
• 18: H.O. Lancaster. The Chi-squared Distribution. John Wiley&Sons, New York NY, 1969.
• 19: N. Megiddo, and R. Srikant Discovering predictive association rules. In Proc. of the 4th Intl. Conference on Knowledge Discovery and Data Mining, pages 274--278, 1998.
• 20: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 21: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceedings of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 22: P.W. Purdom, D. Van Gucht, and D.P. Groth. Average case performance of the apriori algorithm. SIAM J. Computing, 33 (5): 1223--1260, 2004.
• 23: Bassem Sayrafi , Dirk Van Gucht , Paul W. Purdom, On the effectiveness and efficiency of computing bounds on the support of item-sets in the frequent item-sets mining problem, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.46-55, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133912]
• 24: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 25: Craig Silverstein , Sergey Brin , Rajeev Motwani, Beyond Market Baskets: Generalizing Association Rules to Dependence Rules, Data Mining and Knowledge Discovery, v.2 n.1, p.39-68, January 1998 [doi>10.1023/A:1009713703947]
• 26: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 27: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 28: Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 29: Hong Zhang , Balaji Padmanabhan , Alexander Tuzhilin, On the discovery of significant statistical quantitative rules, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014094]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Measurement

Keywords:
false discovery rate, frequent itemset mining, multi-hypothesis test, poisson approximation, statistical significance