Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we propose OP-TKC (Order Preserving Top K Closed itemsets) algorithm for mining top-k frequent closed itemsets. Our methodology visits the closed itemsets lattice in breadth first manner and generates all the top-k closed itemsets without generating all the closed itemsets of a given dataset i.e. in the search space, only closed itemsets that belongs to top-k are expanded and all other closed itemsets are pruned off. Our algorithm computes all the top-k closed itemsets with O(D+ k) space complexity, where D is the dataset. Experiments involving publicly available datasets show that our algorithm takes less memory and running time than TFP algorithm.

REFERENCES

• 1: Claudio Lucchese , Salvatore Orlando , Raffaele Perego, Fast and Memory Efficient Mining of Frequent Closed Itemsets, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.21-36, January 2006 [doi>10.1109/TKDE.2006.10]
• 2: Jianyong Wang , Jiawei Han , Ying Lu , Petre Tzvetkov, TFP: An Efficient Algorithm for Mining Top-K Frequent Closed Itemsets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.652-664, May 2005 [doi>10.1109/TKDE.2005.81]
• 3: Liping Ji , Kian-Lee Tan , Anthony Tung, Compressed Hierarchical Mining of Frequent Closed Patterns from Dense Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.19 n.9, p.1175-1187, September 2007 [doi>10.1109/TKDE.2007.1047]
• 4: Mingjun Song , Sanguthevar Rajasekaran, A Transaction Mapping Algorithm for Frequent Itemsets Mining, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.472-481, April 2006 [doi>10.1109/TKDE.2006.52]
• 5: Gosta Grahne , Jianfei Zhu, Fast Algorithms for Frequent Itemset Mining Using FP-Trees, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1347-1362, October 2005 [doi>10.1109/TKDE.2005.166]
• 6: 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]
• 7: 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]
• 8: 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
• 9: D. -I. Lin , Z. M. Kedem, Pincer-Search: An Efficient Algorithm for Discovering the Maximum Frequent Set, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.553-566, May 2002 [doi>10.1109/TKDE.2002.1000342]
• 10: K. Makino and T. Uno, "New algorithms for enumerating all maximal cliques," in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004), Springer-Verlag, 2004, pp. 260--272.
• 11: Guizhen Yang, The complexity of mining maximal frequent itemsets and maximal frequent patterns, 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.1014091]
• 12: 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 [doi>10.1145/170035.170072]
• 13: T. Uno, M. Kiyomi, and H. Arimura, "LCM ver. 2: Efficient mining algorithms for Frequent/closed/maximal itemsets," In Proc. IEEE ICDM'04 Workshop FIMI'04, 2004.
• 14: Karam Gouda , Mohammed J. Zaki, GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets, Data Mining and Knowledge Discovery, v.11 n.3, p.223-242, November 2005 [doi>10.1007/s10618-005-0002-x]
• 15: C. Lucchese, S. Orlando, P. Palmerini, R. Perego, and F. Silvestri, "KDCI: A Multi-Strategy Algorithm for Mining Frequent Sets," Proc. IEEE ICDM FIMI'03 Workshop, Dec 2003
• 16: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 17: 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
• 18: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 19: 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 [doi>10.1145/342009.335372]
• 20: 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 [doi>10.1145/276304.276313]
• 21: Ferenc Bodon, "A Fast APRIORI Implementation," IEEE ICDM FIMI'03, USA, 2003.
• 22: M. J. Zaki, S. Parthasarathy, M. Ogihara and W. Li, "New Algorithms for fast Discovery of Association Rules", Proc. 3^rd Intl. Conf. Knowledge Discovery and Data Mining, pages: 283--286, 1997
• 23: I. Rigoutsos and A. Floratos, "Combinatorial Pattern Discovery in Biological Sequences: The Teiresias Algorithm, Bioinformatics, Vol 14, pages 55--67, 1998.
• 24: Jianyong Wang , Jiawei Han , Jian Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956779]
• 25: Guimei Liu , Lionel M. Ni, Supporting efficient and scalable frequent pattern mining, Hong Kong University of Science and Technology (People's Republic of China), 2005
• 26: C. Lucchese, S. Orlando, P. Palmerini, R. Perego and F. Silvestri, "KDCI: A multistrategy Algorithm for Mining Frequent Sets," In Proc. IEEE ICDM'03 Workshop FIMI'03, 2003.
• 27: Jérémy Besson , Céline Robardet , Jean-François Boulicaut , Sophie Rome, Constraint-based concept mining and its application to microarray data analysis, Intelligent Data Analysis, v.9 n.1, p.59-82, January 2005
• 28: Feng Pan , Gao Cong , Anthony K. H. Tung , Jiong Yang , Mohammed J. Zaki, Carpenter: finding closed patterns in long biological datasets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956832]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
algorithms, closed itemsets, data mining, mining methods