High Average-Utility Pattern Mining Based on Genetic Algorithm with a Novel Pruning Strategy

The high-utility itemset mining (HUIM) has a critical influence on data mining, and the number of transactions and the profit of items are considered together in HUIM. Nevertheless, HUIM has a disadvantage: it prefers to find itemsets that contain more items, even if the itemsets contain many items with low utility. The recently proposed high average-utility itemset mining (HAUIM) redefines a fairer measurement based on the HUIM to solve the problem. The importance of different itemsets is measured by calculating their average utility, which is defined as total utility divided by length. With the expansion of business, traditional exact algorithms cannot meet the requirements of runtime when datasets are becoming increasingly large and complex. To address this issue, the algorithm proposed in this paper, called GHAUPM-NPS, uses the framework of genetic algorithm to achieve a better balance in terms of performance and the completeness of results. Furthermore, a novel pruning strategy is proposed to accelerate the runtime of the algorithm by neglecting the unpromising itemsets. Sufficient experiments on multiple data show that the proposed algorithm is superior to traditional exact algorithms regarding runtime.