Mining high average-efficiency itemsets based on a compact list structure

High utility itemset mining is a pivotal research direction in data mining, aiming to discover high-value itemsets within datasets. However, traditional approaches ignore product costs, complicating the identification of truly high-revenue combinations. To address this issue, high efficiency itemset mining has been proposed, which defines efficiency as the utility-to-cost ratio. Nevertheless, this measure fails to consider itemset sizes, potentially causing efficiency to inflate as the itemset expands and posing a fairness problem when a uniform threshold is used to evaluate itemsets of different sizes. Consequently, high average-efficiency itemset mining has been introduced for more equitable assessment. To enhance the performance of this algorithm, we propose an improved high average-efficiency itemset mining algorithm based on a compact list structure. Our algorithm introduces a novel average-efficiency list structure, derives a tight upper bound for the maximum average efficiency, and incorporates an innovative pruning strategy. Furthermore, by leveraging an estimated average-efficiency co-occurrence structure, our algorithm significantly reduces the number of join operations. These optimizations collectively result in a substantial improvement in the mining of high average-efficiency itemsets. Experimental results confirm that the proposed algorithm achieves significant improvements in both computational efficiency and scalability.

Authors

• Gufeng Li
• Xuanwei Zhang
• Tao Shang
• Shuo Chen

Keywords

• Data mining
• High average-efficiency itemset mining
• Tighter upper bound
• Pruning strategy