Abstract
International audience. This paper introduces Recursive Pattern Mining (RPM), a novel framework designed to address the "pattern explosion" in contrast mining by iteratively treating the output of a mining process as the input for the next step.
Introduction
In Knowledge Discovery in Databases (KDD), contrast mining is a powerful tool used to identify features that distinguish one data class from another—for instance, identifying genetic markers that differentiate cancerous cells from healthy ones. However, traditional methods like Emerging Pattern (EP) mining face two significant hurdles: the "pattern explosion," where a single search can yield millions of results, and the "crisp threshold effect," where rigid support requirements arbitrarily discard relevant but slightly less frequent patterns.
The Recursive Pattern Mining Framework
To overcome these limitations, the authors propose Recursive Pattern Mining (RPM). This framework shifts the paradigm by treating a collection of discovered patterns as a new transactional dataset.
The Recursive Theory
The algorithm operates through three main phases:
- Initialization: The process begins with the original dataset ($D^1$).
- Recursion: The dataset is mined to find patterns satisfying specific constraints (e.g., frequency or growth rate). These patterns are then transformed into "transactions" to form the next dataset ($D^2$).
- Convergence: This cycle repeats until the set of patterns stabilizes.
By setting a support threshold $\gamma = 1/k$, the authors mathematically guarantee a REP k-summary containing no more than $k$ patterns. This approach "softens" thresholds; patterns that are consistently representative across iterations survive, even if they don't meet a high initial frequency bar.
Key Results and Validation
The RPM framework was validated across UCI benchmarks, SAGE genomic data, and large-scale biomedical text mining (PubMed).
Extreme Compression and Coverage
The most striking result is the framework's ability to distill massive pattern sets without losing significant information. In the ionosphere dataset, over 100,000 emerging patterns were reduced to a 10-pattern summary that maintained 89.2% class coverage.
As shown in the figure above for the wine dataset, the number of patterns drops precipitously between the first and second steps, effectively filtering out noise and redundant information to reach the desired $k$ summary.
Domain-Specific Impact
- Genomics: On SAGE cancer data, a 4-summary identified three specific genes (HNRPH1, GPX1, and NIFIE14) already known in biological literature to be linked to cancer.
- Text Mining: In a PubMed experiment involving 19 million publications, recursion reduced 65,000 potential patterns to 667. This allowed human experts to validate high-quality gene interaction patterns in just 90 minutes, achieving high precision (0.83).
Conclusion and Future Work
Recursive Pattern Mining provides a mathematically grounded solution to the pattern explosion problem, offering "tunable concision" for data analysts. While currently focused on itemsets and sequences, future work aims to extend this recursive logic to more complex data structures like trees and graphs, and to explore "exception mining" by inverting the summarization process.
Summary updated