EHAUPM: Efficient High Average-Utility Pattern Mining with Tighter Upper-Bounds

Abstract– High-utility itemset mining (HUIM) has become a popular data mining task, as it can reveal patterns having a high-utility, contrarily to frequent pattern mining (FIM), which focuses on discovering frequent patterns. High average-utility itemset mining (HAUIM) is a variation of HUIM that provides an alternative measure, called the average utility, to select patterns by considering both their utilities and lengths. In the last decades, several algorithms have been developed to mine high average-utility itemsets (HAUIs). But most of them consume large amounts of memory and have long execution times since they generally utilize the average-utility upper-bound ( auub) model to overestimate the average-utilities of itemsets. To improve the performance of HAUIM, this paper proposes two novel tighter upper-bound models as alternative to the traditional auub model for mining HAUIs. The looser upper-bound model (lub) considers the remaining-maximum utility in transactions to reduce the upper-bound on the utilities
of itemsets. The second upper-bound (rtub) model ignores irrelevant items in transactions to further tighten the upper-bound. Three pruning strategies are also designed to reduce the search space for mining HAUIs by a greater amount, compared to the state-of-the-art HAUI-Miner algorithm. Experiments conducted on several benchmark datasets show that the designed algorithm integrating the two novel upper-bound models outperforms the traditional HAUI-Miner algorithm in terms of runtime, memory usage, number of join operations, and scalability.