Abstract
High Average-Utility Itemset Mining (HAUIM) addresses the bias of traditional utility mining toward longer itemsets by considering the average profit per item. However, real-world databases are dynamic, necessitating incremental mining techniques. This paper surveys the evolution of Incremental HAUIM (iHAUIM), categorizing 19 algorithms into four main lineages and evaluating their performance in dynamic environments.
Introduction
This survey paper, published in Scientific Reports, provides a comprehensive roadmap of the evolution of Incremental High Average-Utility Itemset Mining (iHAUIM). Data mining has evolved significantly from simple frequency-based patterns. While Frequent Itemset Mining (FIM) identifies common item combinations, it fails to account for the economic value of transactions. High Utility Itemset Mining (HUIM) was introduced to address this by considering profit; however, HUIM often exhibits a bias toward longer itemsets, as more items typically generate higher total profit. HAUIM provides a more equitable measure by calculating the average profit per item, identifying "lean" but highly profitable patterns.
The Challenge of Dynamic Data
A significant limitation of standard HAUIM algorithms is their assumption of static databases. In modern applications like e-commerce or financial markets, data is generated continuously. Re-running batch algorithms every time new data arrives is computationally expensive and inefficient. Incremental High Average-Utility Itemset Mining (iHAUIM) addresses this by updating discovered patterns without rescanning the entire historical database, ensuring that the computational cost scales with the volume of new data rather than the total database size.
Taxonomy of iHAUIM Algorithms
The field of iHAUIM has seen the development of numerous algorithms, which can be broadly categorized into four technical lineages based on their underlying data structures and search strategies.
- Apriori-based: These algorithms utilize breadth-first search and candidate generation. They rely on pruning techniques like the Downward Closure Property to eliminate low-utility items early in the process.
- Tree-based: These use compact structures like FP-trees to store transaction data. While they minimize database scans, they can suffer from high memory overhead and slow restructuring speeds in highly dynamic environments.
- List-based: Currently considered the state-of-the-art, these algorithms (e.g., PRE-HAUIMI) use "Average Utility Lists" (AU-lists). This structure supports depth-first searching and avoids the "candidate explosion" problem inherent in Apriori-based methods.
- Index List-based: A newer evolution that further optimizes list structures for faster indexing and retrieval.
The Pre-large Concept
A pivotal innovation in incremental mining is the "Pre-large" concept. This strategy introduces a buffer zone between "high-utility" and "low-utility" itemsets. By tracking itemsets that are close to the utility threshold (pre-large), the algorithm can avoid frequent rescans of the original database. An itemset only triggers a full update if its utility shifts significantly enough to move from the pre-large or small categories into the large (high-utility) category.
As shown in the figure above, the pre-large strategy manages nine distinct cases of itemset transitions when new data is added. This robust framework ensures that only essential updates are performed, maintaining high efficiency even as the database grows.
Empirical Performance and Key Results
Recent surveys and benchmarks have highlighted several key findings regarding the performance of these algorithms:
- Execution Speed: The PRE-HAUIMI algorithm consistently outperforms its peers, especially as the ratio of new data increases. Its use of AU-lists and the pre-large strategy makes it highly resilient to data growth.
- Memory Efficiency: HAUI-Miner remains a top performer for memory-constrained environments due to its superior data compression capabilities within its utility list structure.
- Scalability: Incremental algorithms demonstrate near-linear scalability, whereas batch-processing methods exhibit exponential growth in execution time as datasets expand.
Future Directions and Conclusion
Despite significant progress, iHAUIM faces several "frontier" challenges. Current algorithms are primarily designed for single-node execution, leaving a gap in parallelized or distributed mining for cloud-scale environments. Furthermore, handling high-velocity data streams and complex data types—such as those involving negative utilities (e.g., discounts or returns)—remains an open area for research.
In conclusion, the shift toward list-based incremental frameworks represents the current pinnacle of HAUIM. By leveraging specialized data structures and intelligent buffering strategies like the pre-large concept, researchers can now identify high-value patterns in massive, ever-changing datasets with unprecedented efficiency.
Summary updated