Efficient mining high average-utility itemsets with effective pruning strategies and novel list structure

• Published in: Applied intelligence (Dordrecht, Netherlands) Netherlands), 2023-03, Vol.53 (5), p.6099-6118
• Main Authors: Li, Gufeng, Shang, Tao, Zhang, Yinling
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Computer Science; Data mining; Decision making; Machines; Manufacturing; Mechanical Engineering; Mining; Processes; Upper bounds
• ISSN: 0924-669X; 1573-7497
• DOI: 10.1007/s10489-022-03722-x

High utility itemset mining can mine all itemsets that meet the minimum utility threshold set by the decision maker, thus becomes a popular and prominent data-mining technique. High average utility itemset mining(HAUIM) can determine the desired pattern by considering the utility and length of itemset, which is a fairer alternative measurement. Recently, several algorithms use various utility-list structures and upper bounds to improve the pruning methods. However, these algorithms generated too many unpromising candidates, since they overestimated the average-utility of itemsets too much. This paper designs a novel utility list structure and presents an efficient upper-bound model for improving the performance of HAUIM methods. This list structure captures all key feature informations to estimate the tighter upper-bound of itemset average-utility, it also can be used to calculate the actual itemset average-utility. For avoiding the processing of unpromising candidates, this pruning strategy utilizes the tighter upper-bound. Thus it reduces the number of join operations greatly compared with the state-of-art HAUIM methods. Various experiments were performed by several benchmark datasets to measure the performances of proposed algorithm. The experimental results show that the proposed algorithm has runtime, memory consumption, number of join operations, and scalability performances superior to those of existing algorithms.