Discovering significant rules

ABSTRACT

In many applications, association rules will only be interesting if they represent non-trivial correlations between all constituent items. Numerous techniques have been developed that seek to avoid false discoveries. However, while all provide useful solutions to aspects of this problem, none provides a generic solution that is both flexible enough to accommodate varying definitions of true and false discoveries and powerful enough to provide strict control over the risk of false discoveries. This paper presents generic techniques that allow definitions of true and false discoveries to be specified in terms of arbitrary statistical hypothesis tests and which provide strict control over the experiment wise risk of false discoveries.

REFERENCES

• 1: 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
• 2: A. Agresti. A survey of exact inference for contingency tables. Statistical Science, 7(1):131--153, February 1992.
• 3: Yves Bastide , Nicolas Pasquier , Rafik Taouil , Gerd Stumme , Lotfi Lakhal, Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of the First International Conference on Computational Logic, p.972-986, July 01, 2000
• 4: Stephen D. Bay , Michael J. Pazzani, Detecting Group Differences: Mining Contrast Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.213-246, July 2001 [doi>10.1023/A:1011429418057]
• 5: Roberto J. Bayardo, Jr. , Rakesh Agrawal , Dimitrios Gunopulos, Constraint-Based Rule Mining in Large, Dense Databases, Data Mining and Knowledge Discovery, v.4 n.2-3, p.217-240, July 2000 [doi>10.1023/A:1009895914772]
• 6: Y. Benjamini and Y. Hochberg. Controlling the false discovery rate: A new and powerful approach to multiple testing. Journal of the Royal Statistical Society Series B, 57:289--300, 1995.
• 7: Y. Benjamini and D. Yekutieli. The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4):1165--1188, 2001.
• 8: Jean-Francois Boulicaut , Artur Bykowski, Frequent Closures as a Concise Representation for Binary Data Mining, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.62-73, April 18-20, 2000
• 9: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 10: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 11: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 12: 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]
• 13: S. Hettich and S. D. Bay. The UCI KDD archive. {http://kdd.ics.uci.edu} Irvine, CA: University of California, Department of Information and Computer Science., 2006.
• 14: B. Holland and C. M. D. Improved Bonferroni-type multiple testing procedures. Psychological Bulletin, 104(1):145--149, 1988.
• 15: S. Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6:65--70, 1979.
• 16: International Business Machines. IBM intelligent miner user's guide, version 1, release 1, 1996.
• 17: Christopher Jermaine, Finding the most interesting correlations in a database: how hard can it be?, Information Systems, v.30 n.1, p.21-46, March 2005 [doi>10.1016/j.is.2003.08.004]
• 18: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 19: H. Mannila and H. Toivonen. Multiple uses of frequent sets and condensed representations. In Proc. Int. Conf. Knowledge Discovery and Data Mining KDD'96, pages 189--194, Portland, USA, 1996.
• 20: N. Megiddo and R. Srikant. Discovering predictive association rules. In Proc. Fourth Int. Conf. Knowledge Discovery and Data Mining (KDD-98), pages 27--78, Menlo Park, US, 1998. AAAI Press.
• 21: D. J. Newman, S. Hettich, C. Blake, and C. J. Merz. UCI repository of machine learning databases. {Machine-readable data repository}. University of California, Department of Information and Computer Science, Irvine, CA., 2006.
• 22: G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro and J. Frawley, editors, Knowledge Discovery in Databases, pages 229--248. AAAI/MIT Press, Menlo Park, CA., 1991.
• 23: T. Scheffer. Finding association rules that trade support optimally against confidence. Intelligent Data Analysis, 9(4):381 -- 395, 1995.
• 24: J. P. Shaffer. Multiple hypothesis testing. Ann. Rev. Psychology, 46:561--584, 1995.
• 25: G. I. Webb. Magnum Opus Version 1.3. Software, G. I. Webb & Associates, Melbourne, Aust., 2002.
• 26: G. I. Webb. Magnum Opus Version 3.1. Software, G. I. Webb & Associates, Melbourne, Aust., 2006.
• 27: Geoffrey I. Webb , Songmao Zhang, K-Optimal Rule Discovery, Data Mining and Knowledge Discovery, v.10 n.1, p.39-79, January 2005 [doi>10.1007/s10618-005-0255-4]
• 28: Mohammed J. Zaki, Mining Non-Redundant Association Rules, Data Mining and Knowledge Discovery, v.9 n.3, p.223-248, November 2004 [doi>10.1023/B:DAMI.0000040429.96086.c7]
• 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]
• 30: Zijian Zheng , Ron Kohavi , Llew Mason, Real world performance of association rule algorithms, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.401-406, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502572]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
association rules, rule discovery, statistics