Fast algorithms for mining maximal erasable patterns. (15th June 2019)

• Record Type: Journal Article
• Authors: Nguyen, Linh; Nguyen, Giang; Le, Bac
• Is Part Of: Expert systems with applications. Volume 124(2019)
• Page Start: 50
• Page End: 66
• Publication Date: 2019-06-15
• Subjects: Data mining -- Erasable itemset -- Maximal erasable itemset -- Pruning strategy; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.01.034
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We propose the concept of maximal erasable itemset from product databases. We develop Proposition 1 to check whether an itemset is maximal or not. We propose an efficient algorithm for mining erasable itemsets. We develop Proposition 2 for early pruning nodes. We use Proposition 2 to develop an algorithm for efficient mining. Abstract: Since the problem of mining erasable itemsets was identified in 2009, many algorithms have been proposed to improve mining time and/or memory usage. However, algorithms for mining maximal erasable itemsets (MaxEIs) have not been developed, and this article therefore focuses on this problem. Firstly, a GenMax-based algorithm (GenMax-EI) is developed as a baseline algorithm. Secondly, a proposition is developed for fast checking of whether or not an erasable itemset is maximal, and based on this proposition, we develop an algorithm entitled Flag-GenMax-EI for the fast mining of MEIs. Finally, a second proposition for the fast pruning of non-MaxEIs is also developed; based on this proposition, we propose an algorithm entitled PE-GenMax-EI for mining MaxEIs.