Correlated itemset mining in ROC space: a constraint programming approach

ABSTRACT

Correlated or discriminative pattern mining is concerned with finding the highest scoring patterns w.r.t. a correlation measure (such as information gain). By reinterpreting correlation measures in ROC space and formulating correlated itemset mining as a constraint programming problem, we obtain new theoretical insights with practical benefits. More specifically, we contribute 1) an improved bound for correlated itemset miners, 2) a novel iterative pruning algorithm to exploit the bound, and 3) an adaptation of this algorithm to mine all itemsets on the convex hull in ROC space. The algorithm does not depend on a minimal frequency threshold and is shown to outperform several alternative approaches by orders of magnitude, both in runtime and in memory requirements.

REFERENCES

• 1: Stephen D. Bay , Michael J. Pazzani, Detecting change in categorical data: mining contrast sets, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.302-306, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312263]
• 2: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 3: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 4: Francesco Bonchi , Claudio Lucchese, Extending the state-of-the-art of constraint-based pattern discovery, Data & Knowledge Engineering, v.60 n.2, p.377-399, February, 2007 [doi>10.1016/j.datak.2006.02.006]
• 5: B. Bringmann and A. Zimmermann. Tree2 - decision trees for tree structured data. In PKDD, pages 46--58, 2005.
• 6: B. Bringmann, A. Zimmermann, L. De Raedt, andS. Nijssen. Don't be afraid of simpler patterns. InPKDD, pages 55--66, 2006.
• 7: Cristian Bucilă , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: A Dual-Pruning Algorithm for Itemsets with Constraints, Data Mining and Knowledge Discovery, v.7 n.3, p.241-272, July 2003 [doi>10.1023/A:1024076020895]
• 8: H. Cheng, X. Yan, J. Han, and C.-W. Hsu. Discriminative frequent pattern analysis for effective classification. In ICDE, pages 716--725, 2007.
• 9: Hong Cheng , Xifeng Yan , Jiawei Han , Philip S. Yu, Direct Discriminative Pattern Mining for Effective Classification, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.169-178, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497425]
• 10: Luc De Raedt , Tias Guns , Siegfried Nijssen, Constraint programming for itemset mining, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401919]
• 11: Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005 [doi>10.1109/TKDE.2005.127]
• 12: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 13: Wei Fan , Kun Zhang , Hong Cheng , Jing Gao , Xifeng Yan , Jiawei Han , Philip Yu , Olivier Verscheure, Direct mining of discriminative and essential frequent patterns via model-based search tree, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401922]
• 14: Tom Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, v.27 n.8, p.861-874, June 2006 [doi>10.1016/j.patrec.2005.10.010]
• 15: Johannes Fürnkranz , Peter A. Flach, ROC `n' Rule Learning—Towards a Better Understanding of Covering Algorithms, Machine Learning, v.58 n.1, p.39-77, January 2005 [doi>10.1007/s10994-005-5011-x]
• 16: Henrik Grosskreutz , Stefan Rüping , Stefan Wrobel, Tight Optimistic Estimates for Fast Subgroup Discovery, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_47]
• 17: Masahiro Hirao , Hiromasa Hoshino , Ayumi Shinohara , Masayuki Takeda , Setsuo Arikawa, A practical algorithm to find the best subsequence patterns, Theoretical Computer Science, v.292 n.2, p.465-479, 27 January 2003 [doi>10.1016/S0304-3975(02)00182-2]
• 18: B. Kavsek, N. Lavrac, and V. Jovanoski. APRIORI-SD: Adapting association rule learning to subgroup discovery. In IDA, pages 230--241, 2003.
• 19: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 20: Yasuhiko Morimoto , Takeshi Fukuda , Hirofumi Matsuzawa , Takeshi Tokuyama , Kunikazu Yoda, Algorithms for Mining Association Rules for Binary Segmentations of Huge Categorical Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.380-391, August 24-27, 1998
• 21: Shinichi Morishita , Jun Sese, Transversing itemset lattices with statistical metric pruning, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.226-236, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335226]
• 22: S. Nijssen and J. N. Kok. Multi-class correlated pattern mining. In KDID, pages 165--187, 2005.
• 23: R. C. Prati and P. A. Flach. ROCCER: An algorithm for rule learning based on ROC analysis. In IJCAI, pages 823--828, 2005.
• 24: Jun Sese , Shinichi Morishita, Answering the Most Correlated N Association Rules Efficiently, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.410-422, August 19-23, 2002
• 25: T. Uno, M. Kiyomi, and H. Arimura. Lcm ver. 2: Efficient mining algorithms forfrequent/closed/maximal itemsets. In FIMI, 2004.
• 26: Stefan Wrobel, An Algorithm for Multi-relational Discovery of Subgroups, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.78-87, June 24-27, 1997
• 27: Xifeng Yan , Hong Cheng , Jiawei Han , Philip S. Yu, Mining significant graph patterns by leap search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376662]
• 28: M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In KDD, pages 283--286, 1997.
• 29: J. Zhu and G. Grahne. Reducing the main memory consumptions of FPmax* and FPclose. In FIMI, 2004.
• 30: Albrecht Zimmermann , Bjorn Bringmann, CTC — Correlating Tree Patterns for Classification, Proceedings of the Fifth IEEE International Conference on Data Mining, p.833-836, November 27-30, 2005 [doi>10.1109/ICDM.2005.49]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Theory

Keywords:
ROC analysis, constraint programming, itemset mining