CP-summary: a concise representation for browsing frequent itemsets

ABSTRACT

This paper tackles the problem of summarizing frequent itemsets. We observe that previous notions of summaries cannot be directly used for analyzing frequent itemsets. In order to be used for analysis, one requirement is that the analysts should be able to browse all frequent itemsets by only having the summary.

For this purpose, we propose to build the summary based upon a novel formulation, conditional profile (or c-profile). Several features of our proposed summary are: (1) each profile in the summary can be analyzed independently, (2) it provides error guarantee (ε-adequate), and (3) it produces no false positives or false negatives.

Having the formulation, the next challenge is to produce the most concise summary which satisfies the requirement. In this paper, we also designed an algorithm which is both effective and efficient for this task. The quality of our approach is justified by extensive experiments.

The implementations for the algorithms are available from www.cais.ntu.edu.sg/~vivek/pubs/cprofile09.

REFERENCES

• 1: Foto Afrati , Aristides Gionis , Heikki Mannila, Approximating a collection of frequent sets, 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.1014057]
• 2: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 3: 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
• 4: Toon Calders , Bart Goethals, Non-derivable itemset mining, Data Mining and Knowledge Discovery, v.14 n.1, p.171-206, February 2007 [doi>10.1007/s10618-006-0054-6]
• 5: 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]
• 6: James Cheng , Yiping Ke , Wilfred Ng, \delta-Tolerance Closed Frequent Itemsets, Proceedings of the Sixth International Conference on Data Mining, p.139-148, December 18-22, 2006 [doi>10.1109/ICDM.2006.1]
• 7: Dimitrios Gunopulos , Heikki Mannila , Roni Khardon , Hannu Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.209-216, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263684]
• 8: Ruoming Jin , Muad Abu-Ata , Yang Xiang , Ning Ruan, Effective and efficient itemset pattern summarization: regression-based approaches, 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.1401941]
• 9: Jonathan A. Kelner , Daniel A. Spielman, A randomized polynomial-time simplex algorithm for linear programming, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132524]
• 10: Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191314]
• 11: Marzena Kryszkiewicz , Marcin Gajek, Concise Representation of Frequent Patterns Based on Generalized Disjunction-Free Generators, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.159-171, May 06-08, 2002
• 12: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In KDD, pages 80--86, 1998.
• 13: H. Mannila and H. Toivonen. Multiple uses of frequent sets and condensed representations (extended abstract). In KDD, pages 189--194, 1996.
• 14: 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
• 15: Chao Wang , Srinivasan Parthasarathy, Summarizing itemset patterns using probabilistic models, 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.1150495]
• 16: 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
• 17: Xifeng Yan , Hong Cheng , Jiawei Han , Dong Xin, Summarizing itemset patterns: a profile-based approach, 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.1081907]
• 18: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
concise representations, conditional profile, frequent itemset, summarization