Abstract
Exceptional Model Mining (EMM) is a powerful framework for identifying subgroups that exhibit unusual local behavior relative to a global model. Despite its utility, the exponential search space of subgroup descriptions typically forces researchers to rely on heuristic search methods. This paper introduces GP-growth (Generic Pattern growth), an algorithm that generalizes the FP-growth technique to enable exhaustive EMM. By utilizing "valuation bases"—condensed statistical summaries—GP-growth achieves significant performance gains. Experimental results on benchmark and large-scale datasets show speedups of over two orders of magnitude compared to traditional exhaustive search, making complete discovery practical for complex models.
Introduction
In data mining, Subgroup Discovery aims to find subsets of a population that deviate significantly from the norm regarding a single target variable. Exceptional Model Mining (EMM) extends this by seeking subgroups where a model—such as a correlation between multiple variables or a regression slope—is exceptional.
The primary challenge in EMM is the "combinatorial explosion." With numerous attributes, the number of potential subgroup descriptions grows exponentially, making exhaustive search computationally prohibitive. Consequently, most existing EMM tools utilize heuristic methods like beam search, which may miss globally optimal patterns. This work addresses this gap by providing a framework for efficient, exhaustive search.
Methodology: The GP-growth Algorithm
The authors propose GP-growth, a generalization of the classic FP-growth algorithm. While FP-growth is designed for frequent itemset mining using simple frequency counts, GP-growth adapts this structure for complex statistical modeling.
The Valuation Basis
The core innovation is the Valuation Basis. In a standard FP-tree, each node stores a counter. In a GP-tree, nodes store a valuation basis: a condensed representation of the data necessary to compute a specific model's parameters.
For instance, to calculate variance, one only needs the count, the sum of values, and the sum of squared values. To calculate correlation, the basis includes counts, sums for both variables, and the sum of their products. This approach allows the algorithm to aggregate data as the tree is built, avoiding repeated passes over the raw dataset.
Decoupling Search and Modeling
The GP-growth framework is model-agnostic. By defining a formal "Valuation Domain," the search process is decoupled from the specific model being evaluated. As shown in the table above, different models (e.g., Correlation, Linear Regression) can be implemented simply by swapping the valuation basis and the "extractor" function.
A key insight of the paper is the link to data stream mining: any model that can be computed in a single-pass, parallelizable manner with low memory requirements can be efficiently integrated into the GP-growth framework.
Experimental Evaluation
The authors evaluated GP-growth using 19 UCI Repository datasets (e.g., credit-g, adults) and a large-scale Social Image dataset from Flickr containing ~1.1 million instances and 1200 attributes.
Key Results
- Performance: On UCI benchmarks, GP-growth was consistently two orders of magnitude faster than a naive depth-first search (DFS). At a search depth of 5, GP-growth completed in seconds or minutes, whereas DFS often required hours.
- Scalability: On the Flickr dataset, a standard DFS failed to complete a shallow search (depth 2) within 48 hours. In contrast, GP-growth finished the same task in just 8 minutes.
- Efficiency: The runtime remains stable across various model classes, indicating that the overhead of maintaining complex valuation bases is negligible compared to the structural benefits of the GP-tree.
Discussion and Future Work
While GP-growth significantly advances exhaustive EMM, it has limitations. Non-linear models like Logistic Regression or Bayesian Networks do not currently support exact single-pass computation. For these, the algorithm must store raw data in the valuation basis, which reduces performance.
Future research directions include:
- Pruning Techniques: Implementing "optimistic estimate pruning" to skip unpromising branches of the search space.
- Diversity: Developing methods to ensure discovered subgroups are distinct, preventing users from being overwhelmed by nearly identical results.
- Advanced Structures: Exploring bit vectors and other data structures to further optimize the GP-tree.
Conclusion
GP-growth makes exhaustive Exceptional Model Mining a practical reality for large datasets. By generalizing FP-growth through the concept of valuation bases, the algorithm provides a scalable, model-agnostic framework that bridges the gap between heuristic search and complete discovery.
Summary updated