Mining frequent itemsets without support threshold: with and without item constraints

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. In this paper, 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 kmax value. We call the results the N-most interesting itemsets. Generally, it is more straightforward for users to determine N and kmax. 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. Index Terms—Association rules, N-most interesting itemsets, FP-tree, item constraints