A novel pruning algorithm for mining long and maximum length frequent itemsets. (15th March 2020)

• Record Type: Journal Article
• Authors: Lessanibahri, Sina; Gastaldi, Luca; González Fernández, Camino
• Is Part Of: Expert systems with applications. Volume 142(2020)
• Publication Date: 2020-03-15
• Subjects: Association rules mining -- Maximum length frequent itemsets -- Data mining -- Long frequent itemsets; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.113004
• Languages: English
• ISSNs: 0957-4174

Abstract

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.