TFP: An efficient algorithm for mining top-k frequent closed itemsets

Jianyong Wang, Jiawei Han, Ying Lu, Petre Tzvetkov

Research output: Contribution to journalArticlepeer-review

Abstract

Frequent itemset mining has been studied extensively in literature. Most previous studies require the specification of a min_support threshold and aim at mining a complete set of frequent itemsets satisfying min_support. However, in practice, it is difficult for users to provide an appropriate min_support threshold. In addition, a complete set of frequent itemsets is much less compact than a set of frequent closed itemsets. In this paper, we propose an alternative mining task: mining top-k frequent closed itemsets of length no less than min_l, where k is the desired number of frequent closed itemsets to be mined, and min_l the minimal length of each itemset. An efficient algorithm, called TFP, is developed for mining such itemsets without mins_support. Starting at min_support= 0 and by making use of the length constraint and the properties of top-k frequent closed itemsets, min_support can be raised effectively and FP-Tree can be pruned dynamically both during and after the construction of the tree using our two proposed methods: the closed node count and descendant_sum. Moreover, mining is further speeded up by employing a top-down and bottom-up combined FP-Tree traversing strategy, a set of search space pruning methods, a fast 2-level hash-indexed result tree, and a novel closed itemset verification scheme. Our extensive performance study shows that TFP has high performance and linear scalability in terms of the database size.

Original languageEnglish (US)
Pages (from-to)652-664
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume17
Issue number5
DOIs
StatePublished - May 1 2005

Keywords

  • Association rules
  • Data mining
  • Frequent itemset
  • Mining methods and algorithms

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'TFP: An efficient algorithm for mining top-k frequent closed itemsets'. Together they form a unique fingerprint.

Cite this