TL;DR
This paper introduces Recursive Pattern Mining (RPM), a novel framework that iteratively treats the output of a mining process as the input for the next step. By applying this to "emerging patterns"—features that distinguish one data class from another—the authors can generate a concise k-summary of at most $k$ highly representative patterns, solving the long-standing problem of "pattern explosion" in data mining.
What Problem Does This Paper Address?
In the field of Knowledge Discovery in Databases (KDD), contrast mining aims to find patterns that distinguish different classes (e.g., "cancerous" vs. "healthy" cells). While algorithms like Emerging Pattern (EP) mining are powerful, they suffer from two major flaws:
- The Pattern Explosion: A single search can return millions of patterns, making it impossible for a human expert to interpret the results.
- The "Crisp" Threshold Effect: Traditional mining relies on rigid thresholds (like minimum support). A pattern that is 0.1% below the threshold is discarded, even if it is highly relevant, while a slightly more frequent but trivial pattern is kept.
The authors seek a method that provides a "tunable concision"—allowing a user to say, "Give me the 10 most important contrasts," and receiving a representative, high-quality summary.
Methods
The core innovation is the Recursive Theory. Instead of mining a dataset once, the algorithm follows these steps:
- Initialization: Start with the original dataset ($D^1$).
- Recursion: Mine the dataset to find patterns satisfying a constraint (like frequency or growth rate). These discovered patterns then become the "transactions" for the next dataset ($D^2$).
- Convergence: Repeat this process until the set of patterns becomes stable (the output no longer changes).
To create a REP k-summary (Recursive Emerging Pattern summary), the authors set the support threshold $\gamma$ to $1/k$. They mathematically prove that this specific configuration guarantees the final summary will contain no more than $k$ patterns. This approach "softens" the impact of thresholds because patterns are refined through multiple steps, allowing significant but slightly less frequent patterns to survive if they are highly representative of the class.
Datasets
The authors validated their approach across three distinct domains:
- UCI Benchmarks: Standard machine learning datasets including wine, new-thyroid, cmc, abalone, and ionosphere.
- SAGE Genomic Data: A dataset of 27,679 genes across 90 biological situations (cancerous vs. normal).
- Biomedical Text Mining: A massive collection of 19 million PubMed publications, specifically searching for linguistic patterns that describe gene interactions.
Key Insights and Ideas
- Patterns as Data: The "aha moment" is treating a collection of patterns as a transactional dataset itself. This allows the algorithm to find "patterns of patterns," naturally distilling the most essential information.
- Mathematical Guarantee of Concision: Unlike heuristic "top-k" methods that might pick the 10 best patterns but leave the rest of the data unrepresented, the REP k-summary is proven to be bounded by $k$ while maintaining high "class coverage."
- Overcoming the Crisp Effect: Because the mining is recursive, a pattern doesn't just need to pass a single bar; it needs to be a consistent "winner" across iterations. This leads to more robust and less arbitrary selections.
Key Results
- Extreme Compression: In the ionosphere dataset, traditional mining produced over 100,000 emerging patterns. The RPM framework successfully distilled this into a 10-pattern summary that still covered 89.2% of the transactions.
- Biological Relevance: On the SAGE cancer dataset, a 4-summary identified three specific genes (HNRPH1, GPX1, and NIFIE14). These results were not just statistically significant but were confirmed by existing biological literature as being correlated with cancerous situations.
- Efficiency in Text Mining: In the PubMed experiment, the recursion reduced 65,000 potential patterns down to just 667. An expert was able to validate these in just 90 minutes, identifying 232 high-quality sequential patterns describing gene interactions with high precision (0.83) and recall (0.75).
Limitations and Future Work
- Data Complexity: The current work focuses primarily on itemsets and sequences. The authors acknowledge that future research should extend this recursive framework to more complex structures like trees or graphs.
- Exception Mining: While this paper focuses on summarizing the most prominent contrasts, the authors suggest that the recursive framework could be inverted to find "exceptions"—rare but interesting patterns that deviate from the norm.
- Computational Overhead: Although the authors state the first mining step is the most time-consuming, the cost of multiple recursive passes on large-scale datasets remains an area for further optimization.
Summary updated