Mining frequent itemsets without support threshold: with and without item constraints
Authors:
- 26 July 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 16 (9) , 1052-1069
Abstract
In classical association rules mining, a minimum support threshold is assumed to be available for mining frequent itemsets. However, setting such a threshold is typically hard. We handle a more practical problem; roughly speaking, it is to mine N k-itemsets with the highest supports for k up to a certain k/sub max/ value. We call the results the N-most interesting itemsets. Generally, it is more straightforward for users to determine N and k/sub max/. We propose two new algorithms, LOOPBACK and BOMO. Experiments show that our methods outperform the previously proposed Itemset-Loop algorithm, and the performance of BOMO can be an order of magnitude better than the original FP-tree algorithm, even with the assumption of an optimally chosen support threshold. We also propose the mining of "N-most interesting k-itemsets with item constraints." This allows user to specify different degrees of interestingness for different itemsets. Experiments show that our proposed Double FP-trees algorithm, which is based on BOMO, is highly efficient in solving this problem.Keywords
This publication has 18 references indexed in Scilit:
- Pushing Convertible Constraints in Frequent Itemset MiningData Mining and Knowledge Discovery, 2004
- Clustering association rules2002
- Efficient mining of constrained correlated sets2002
- Exploiting succinct constraints using FP-treesACM SIGKDD Explorations Newsletter, 2002
- Constrained frequent pattern miningACM SIGKDD Explorations Newsletter, 2002
- FP-tree approach for mining N-most interesting itemsets2002
- Real world performance of association rule algorithms2001
- Turbo-charging vertical mining of large databases2000
- Mining frequent patterns without candidate generation2000
- Finding interesting rules from large sets of discovered association rules1994