Efficient mining of high utility itemsets with multiple minimum utility thresholds

摘要

Mining high utility itemsets is considered to be one of the important and challenging problems in the data mining literature. The problem offers greater flexibility to a decision maker in using item utilities such as profits and margins to mine interesting and actionable patterns from databases. Most of the current works in the literature, however, apply a single minimum utility threshold value and fail to consider disparities in item characteristics. This paper proposes an efficient method (MHUI) to mine high utility itemsets with multiple minimum utility threshold values. The presented method generates high utility itemsets in a single phase without an expensive intermediate candidate generation process. It introduces the concept of suffix minimum utility and presents generalized pruning strategies for efficiently mining high utility itemsets. The performance of the algorithm is evaluated against the state-of-the-art methods (HUI-MMU-TE and HIMU-EUCP) on eight benchmark datasets. The experimental results show that the proposed method delivers two to three orders of magnitude execution time improvement over the HUI-MMU-TE method. In addition, MHUI delivers one to two orders of magnitude execution time improvement over the HIMU-EUCP method, especially on moderately long and dense benchmark datasets. The memory requirements of the proposed algorithm was also found to be significantly lower.