Efficiently mining high average-utility itemsets with an improved upper-bound strategy

Utility mining has recently been discussed in the field of data mining. A utility itemset considers both profits and quantities of items in transactions, and thus its utility value increases with increasing itemset length. To reveal a better utility effect, an average-utility measure, which is the total utility of an itemset divided by its itemset length, is proposed. However, existing approaches use the traditional average-utility upper-bound model to find high average-utility itemsets, and thus generate a large number of unpromising candidates in the mining process. The present study proposes an improved upper-bound approach that uses the prefix concept to create tighter upper bounds of average-utility values for itemsets, thus reducing the number of unpromising itemsets for mining. Results from experiments on two real databases show that the proposed algorithm outperforms other mining algorithms under various parameter settings.