A novel pruning algorithm for mining long and maximum length frequent itemsets. (15th March 2020) - Lessanibahri, Sina; Gastaldi, Luca; González Fernández, Camino
Highlights: We propose LengthSort, an efficient algorithm for mining maximum length itemsets. LengthSort prunes items and transactions prior to constructing the initial tree. LengthSort can be easily integrated with other tree-based algorithms. LengthSort can be used to mine frequent itemsets that are longer than a threshold. Abstract: Frequent itemset mining is today one of the most popular data mining techniques. Its application is, however, hindered by the high computational cost in many real-world datasets, especially for smaller values of support thresholds. In many cases, moreover, the large number of frequent itemsets discovered is overwhelming. In some real-world applications, it is sufficient to find a smaller subset of frequent itemsets, such as identifying the frequent itemsets with a maximum length. In this paper, we present a pruning algorithm, called LengthSort, that reduces the search space effectively and improves the efficiency of mining frequent itemsets with a maximum length. LengthSort prunes both the items and the transactions before constructing a Frequent Pattern tree structure. Our experiments on several datasets show that the proposed pruning techniques reduce the time needed to discover the frequent itemsets with a maximum length. The proposed pruning algorithm can also be applied to efficiently discover frequent itemsets that are longer than a user-specified threshold.