Cartesian contour: a concise representation for a collection of frequent sets

ABSTRACT

In this paper, we consider a novel scheme referred to as Cartesian contour to concisely represent the collection of frequent itemsets. Different from the existing works, this scheme provides a complete view of these itemsets by covering the entire collection of them. More interestingly, it takes a first step in deriving a generative view of the frequent pattern formulation, i.e., how a small number of patterns interact with each other and produce the complexity of frequent itemsets. We perform a theoretical investigation of the concise representation problem and link it to the biclique set cover problem and prove its NP-hardness. We develop a novel approach utilizing the technique developed in frequent itemset mining, set cover, and max k-cover to approximate the minimal biclique set cover problem. In addition, we consider several heuristic techniques to speedup the construction of Cartesian contour. The detailed experimental study demonstrates the effectiveness and efficiency of our approach.

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 , 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: Christan Borgelt. Apriori implementation. http://fuzzy.cs.Uni-Magdeburg.de/~borgelt/Software. Version 4.08.
• 4: Doug Burdick , Manuel Calimlim , Jason Flannick , Johannes Gehrke , Tomi Yiu, MAFIA: A Maximal Frequent Itemset Algorithm, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1490-1504, November 2005 [doi>10.1109/TKDE.2005.183]
• 5: 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]
• 6: V. Chval. A greedy heuristic for the set-covering problem. Math. Oper. Res, 4:233--235, 1979.
• 7: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 8: Jiawei Han , Jianyong Wang , Ying Lu , Petre Tzvetkov, Mining Top.K Frequent Closed Patterns without Minimum Support, Proceedings of the 2002 IEEE International Conference on Data Mining, p.211, December 09-12, 2002
• 9: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: 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]
• 11: 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
• 12: Jinyan Li , Guimei Liu , Haiquan Li , Limsoon Wong, Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix: A One-to-One Correspondence and Mining Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.19 n.12, p.1625-1637, December 2007 [doi>10.1109/TKDE.2007.190660]
• 13: 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
• 14: Ralf Schenkel, Anja Theobald, and Gerhard Weikum. Hopi: An efficient connection index for complex xml document collections. In EDBT, pages 237--255, 2004.
• 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: Yang Xiang , Ruoming Jin , David Fuhry , Feodor F. Dragan, Succinct summarization of transactional databases: an overlapped hyperrectangle scheme, 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.1401981]
• 17: Dong Xin , Hong Cheng , Xifeng Yan , Jiawei Han, Extracting redundancy-aware top-k patterns, 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.1150452]
• 18: 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
• 19: 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]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
cartesian product, concise pattern representation, frequent itemsets, set cover