A fast algorithm for mining high average-utility itemsets

摘要

Mining high-utility itemsets (HUIs) in transactional databases has become a very popular research topic in recent years. A popular variation of the problem of HUI mining is to discover high average-utility itemsets (HAUIs), where an alternative measure called the average-utility is used to evaluate the utility of itemsets by considering their lengths. Albeit, HAUI mining has been studied extensively, current algorithms often consume a large amount of memory and have long execution times, due to the large search space and the usage of loose upper bounds to estimate the average-utilities of itemsets. In this paper, we present a more efficient algorithm for HAUI mining, which includes three pruning strategies to provide a tighter upper bound on the average-utilities of itemsets, and thus reduce the search space more effectively to decrease the runtime. The first pruning strategy utilizes relationships between item pairs to reduce the search space for itemsets containing three or more items. The second pruning strategy provides a tighter upper bound on the average-utilities of itemsets to prune unpromising candidates early. The third strategy reduces the time for constructing the average-utility-list structures for itemsets, which is used to calculate their upper bounds. Substantial experiments conducted on both real-life and synthetic datasets show that the proposed algorithm with three pruning strategies can efficiently and effectively reduce the search space for mining HAUIs, when compared to the state-of-the-art algorithms, in terms of runtime, number of candidates, memory usage, performance of the pruning strategies and scalability.