A condensed representation to find frequent patterns

ABSTRACT

Given a large set of data, a common data mining problem is to extract the frequent patterns occurring in this set. The idea presented in this paper is to extract a condensed representation of the frequent patterns called disjunction-free sets, instead of extracting the whole frequent pattern collection. We show that this condensed representation can be used to regenerate all frequent patterns and their exact frequencies. Moreover, this regeneration can be performed without any access to the original data. Practical experiments show that this representation can be extracted very efficiently even in difficult cases. We compared it with another representation of frequent patterns previously investigated in the literature called frequent closed sets. In nearly all experiments we have run, the disjunction-free sets have been extracted much more efficiently than frequent closed sets.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 2: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: Jean-Francois Boulicaut , Artur Bykowski , Christophe Rigotti, Approximation of Frequency Queris by Means of Free-Sets, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.75-85, September 13-16, 2000
• 6: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 7: H. Mannila and H. Toivonen. Multiple uses of frequent sets and condensed representations. In Proceedings KDD'96, pages 189-194, Portland, USA, Aug. 1996.
• 8: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 9: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4]
• 10: J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In Proceedings of the 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 21-30, Dallas, Texas, May 2000.
• 11: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Experimentation, Management, Theory