Abstract
Frequent itemset mining is a foundational task in data science, yet traditional frequency-based methods often suffer from "pattern explosion," generating thousands of redundant results. This paper introduces a Bayesian framework that reframes itemset mining as a statistical model selection problem. By scoring itemsets based on their posterior probability within an exponential model family and utilizing the Bayesian Information Criterion (BIC), the proposed method naturally suppresses noise and identifies a concise, high-quality core of patterns. To ensure computational tractability, the search is restricted to decomposable models and navigated via a Markov Chain Monte Carlo (MCMC) algorithm. Results across synthetic and real-world datasets demonstrate that this approach successfully recovers ground-truth dependencies and produces highly interpretable results.
Introduction
In the world of data mining, finding groups of items that frequently appear together—such as products in grocery receipts—is a classic challenge. However, traditional association rule algorithms often lead to a "pattern explosion." If two items, like bread and butter, are highly correlated, then every superset containing them (e.g., {bread, butter, milk}) will also appear frequent and significant, leading to thousands of redundant discoveries.
Nikolaj Tatti’s paper, "Probably the Best Itemsets," addresses this by moving away from simple frequency counting. Instead, it treats itemset mining as a Bayesian model selection problem. By scoring itemsets based on their probability of being part of a "good" statistical model, it uses Occam's razor to naturally suppress redundant patterns.
Methodology: Mining as Modeling
The core innovation of this work is viewing an itemset not as a count, but as a parameter in a statistical model. The author proposes a scoring system based on Exponential Models.
The Bayesian Score and BIC
The score of an itemset $X$ is defined as the posterior probability that $X$ belongs to the "true" model family, given the observed data $D$. To calculate this, the paper employs the Bayesian Information Criterion (BIC). BIC rewards models that fit the data well but penalizes complexity (models with too many itemsets). This penalty is the mechanism that prevents pattern explosion: once a dependency (like $a \leftrightarrow b$) is explained, larger sets containing $a$ and $b$ no longer provide enough statistical "boost" to overcome the BIC penalty, causing their scores to drop.
Decomposable Models and MCMC
General exponential models are computationally NP-hard. To make the mathematics tractable, the author restricts the search to decomposable models. These models can be represented as junction trees, allowing for efficient likelihood calculations.
To navigate the vast space of possible models, the author uses a Markov Chain Monte Carlo (MCMC) algorithm. The algorithm "walks" through model space using two primary moves:
- Merge: Combining two itemsets to create a more complex dependency.
- Split: Breaking an itemset down into simpler components.
Experimental Evaluation
The method was evaluated on both synthetic and real-world datasets, including fossil records (Paleo), DNA amplification data (Dna), and university enrollment records (Courses).
Key Results
- Convergence to Truth: On synthetic data, as the number of transactions increased, the algorithm's scores converged perfectly to the ground truth. For independent datasets, only single items remained significant; for chained datasets, only singletons and adjacent pairs were flagged.
- Manageable Output: Unlike traditional methods that return thousands of rules, this framework produces a concise set of high-probability patterns. In the Courses dataset, the top-scoring pairs represented logical academic clusters, such as (Computer Architectures, Performance Analysis) with a score of 0.95.
- Monotonicity: The author proves the score decreases monotonically (if $X \subseteq Y$, then $sc(X) \geq sc(Y)$), a property that allows for efficient pruning of the search space.
Conclusion and Future Work
By treating itemsets as model parameters, this framework provides a principled way to eliminate redundancy. While the restriction to decomposable models may miss certain non-chordal dependencies (like a simple four-item cycle), and MCMC sampling introduces higher computational overhead than standard algorithms like Apriori, the gain in result quality is significant. Future work may focus on relaxing the decomposability constraint or optimizing the MCMC convergence for even larger datasets.
Summary updated