Pruning strategies for mining high utility itemsets

• Presents an efficient high utility mining method.
• Employs novel pruning strategies to limit the search space of utility mining.
• Compares the proposed method against a state-of-the-art utility mining method.
• Experimentally evaluates the system on eight real and synthetic benchmark datasets.
• Empirical results are found to be quite promising, especially for sparse transactional databases.

High utility itemset mining problem involves the use of internal and external utilities of items (such as profits, margins) to discover interesting patterns from a given transactional database. It is an extension of the basic frequent itemset mining problem and is proven to be considerably hard and intractable. This is due to the lack of inherent structural properties of high utility itemsets that can be exploited. Several heuristic methods have been suggested in the literature to limit the large search space. This paper aims to improve the state-of-the-art and proposes a high utility mining method that employs novel pruning strategies. The utility of the proposed method is demonstrated through rigorous experimentation on several real and synthetic benchmark sparse and dense datasets. A comparative evaluation of the method against a state-of-the-art method is also presented. Our experimental results reveal that the proposed method is very effective in pruning unpromising candidates, especially for sparse transactional databases.