Maintenance algorithm for high average-utility itemsets with transaction deletion

作者：Lin, Jerry Chun-Wei^*; Shao, Yina; Fournier-Viger, Philippe; Djenouri, Youcef; Guo, Xiangmin

来源：Applied Intelligence, 2018, 48(10): 3691-3706.

DOI：10.1007/s10489-018-1180-8

• High average-utility mining
• Dynamic database
• Transaction deletion
• MFUP

High-utility itemset mining (HUIM) is an extension of traditional association-rule mining that can find profitable itemsets for decision-making. It faces, however, a limitation since the utility of an itemset increases along with the size of it. High-average utility itemset mining (HAUIM) provides a fair measure to find the average-utility of an itemset, which is more reasonable to design the sales strategies for making the efficient decision. Traditional algorithms of HAUIM mostly focus on mining high average-utility itemsets (HAUIs) from the static database. When the database size is changed, for example, transaction insertion/deletion, the discovered information is required to be updated, thus the updated database is necessary to be re-scanned for identifying the set of HAUIs in the batch manner. In this paper, we present an updating algorithm called FUP-HAUIMD to maintain the discovered HAUIs with transaction deletion. When some transactions in the database are deleted, the designed FUP-HAUIMD algorithm can easily update the discovered HAUIs without scanning the database all the time. The designed FUP-HAUIMD algorithm divides the itemsets into four cases based on the modified fast updated (MFUP) concept. The average-utility (AU)-list structure is further utilized to keep the necessary ramification for later mining progress. Experiments are then conducted to compare the designed FUP-HAUIMD algorithm with the state-of-the-art baseline algorithm running on the batch mode, and the developed approach shows better performance in terms of runtime, number of examined patterns, and scalability.

• 出版日期2018-10
• 单位哈尔滨工业大学