%0 Journal Article %1 1411744 %A Wang, J. %A Han, J. %A Lu, Y. %A Tzvetkov, P. %D 2005 %J Knowledge and Data Engineering, IEEE Transactions on %K closedSetMining dataMining listing patternMining topk %N 5 %P 652-663 %R 10.1109/TKDE.2005.81 %T TFP: an efficient algorithm for mining top-k frequent closed itemsets %V 17 %X 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 is 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.

@article{1411744, 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 is 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.}, added-at = {2009-06-19T12:35:28.000+0200}, author = {Wang, J. and Han, J. and Lu, Y. and Tzvetkov, P.}, biburl = {https://www.bibsonomy.org/bibtex/216e8185b5b4845fde175771df52c629a/mboley}, description = {Welcome to IEEE Xplore 2.0: TFP: an efficient algorithm for mining top-k frequent closed itemsets}, doi = {10.1109/TKDE.2005.81}, interhash = {c5fb61cdaddf4d0894dee8c5fd9b6b74}, intrahash = {16e8185b5b4845fde175771df52c629a}, issn = {1041-4347}, journal = {Knowledge and Data Engineering, IEEE Transactions on}, keywords = {closedSetMining dataMining listing patternMining topk}, month = May, number = 5, pages = { 652-663}, timestamp = {2009-07-28T11:20:59.000+0200}, title = {TFP: an efficient algorithm for mining top-k frequent closed itemsets}, volume = 17, year = 2005 }