Summarizing itemset patterns using probabilistic models

Chao Wang, Srinivasan ParthasarathyKDD 2006 · DOI

TL;DR

This paper introduces a novel probabilistic approach using Markov Random Fields (MRFs) to summarize massive sets of frequent itemsets. By modeling item relationships, their method achieves significantly better accuracy and often faster summarization times compared to existing pattern profile techniques, offering a more concise and interpretable representation of transactional data.

What Problem Does This Paper Address?

Mining frequent itemsets from large transactional datasets is a cornerstone of data mining, with applications ranging from market basket analysis to recommendation systems. However, the sheer volume of frequent itemsets generated by standard algorithms can overwhelm end-users, making interpretation and actionable insights difficult. Existing summarization techniques like closed itemsets, maximal itemsets, and pattern profiles offer compression but can still result in large summaries or lack accuracy. This paper tackles the challenge of creating a truly concise and accurate summary of frequent itemsets that is efficient to generate and easy to interpret.

Methods

The core of this paper's contribution lies in its probabilistic approach to itemset summarization. Instead of directly compressing the itemset list, they build a Markov Random Field (MRF). Here's how it works:

  • Itemset to MRF: Frequent itemsets are used to construct an MRF. Items are treated as random variables, and the relationships (correlations) between them, as revealed by frequent itemsets, are encoded as edges in the MRF.
  • Focus on Non-Derivable Itemsets: Leveraging the insight that non-derivable itemsets capture essential distributional information, the MRF is primarily constructed from these. This is justified by Lemma 1, which states that an MRF built from all frequent itemsets is equivalent to one built from only the non-derivable ones. Lemma 2 further suggests that accurate summarization of non-derivable itemsets leads to bounded errors for derivable ones.
  • Level-wise Iterative Summarization: The summarization process is iterative and level-wise. It starts with 1-itemsets to initialize the MRF. Then, it infers the supports of 2-itemsets. If an itemset's support can be accurately estimated (within a user-defined error tolerance, δ), it's considered "skewed" and bypassed. If the estimation error is too high, the itemset is considered "skewed" and its information is used to augment the MRF, refining the model. This process repeats for higher-level itemsets.
  • Inference Engines: To estimate itemset supports from the MRF, they employ two inference engines: the exact Junction Tree algorithm (efficient for low-treewidth MRFs) and approximate Gibbs sampling (MCMC) for more complex models.

Datasets

The authors evaluated their approach on four publicly available datasets:

  • Chess: A relatively dense dataset.
  • Accidents: A dataset with moderate density.
  • Mushroom: A dataset known for being relatively dense.
  • Microsoft Web Dataset: A sparse dataset.

These datasets are standard benchmarks in the frequent itemset mining community.

Key Insights and Ideas

  • MRFs as a Concise Summary: The MRF itself, built from a subset of "skewed" itemsets, acts as the summary. This probabilistic graphical model captures the conditional independence structure of the data, allowing for efficient inference of itemset supports.
  • Non-Derivable Itemsets are Key: The paper strongly emphasizes that non-derivable itemsets are crucial for accurate summarization. By focusing on them, they can achieve good overall accuracy while significantly reducing the number of itemsets needed for the summary.
  • Tunable Trade-off: The introduction of an error tolerance parameter (δ) allows users to control the trade-off between summary size and accuracy. A higher δ leads to a smaller summary but potentially lower accuracy, and vice-versa.
  • Efficiency Gains: The probabilistic approach, especially when combined with efficient inference, can be significantly faster than iterative scanning methods required by some existing techniques like pattern profiles.

Key Results

  • Superior Accuracy: On dense datasets like Chess, their probabilistic model-based (PM) approach consistently outperformed the pattern profile (PP) approach in terms of restoration error (average relative error in support estimation) for comparable summary sizes. For instance, on the Chess dataset, PM achieved significantly lower restoration error than PP for the same byte-size summary.
  • Significant Compression: The PM approach achieved substantial compression. For example, on the Chess dataset, a summary of 398 bytes represented itemsets that originally took 12480 bytes, a ~30-fold reduction.
  • Faster Summarization: For the Chess dataset, their approach summarized itemsets in under 5 seconds, while the pattern profile approach struggled with memory limitations and took much longer (e.g., 40 minutes on a more powerful machine).
  • Robustness: While performance varied with dataset sparsity and independence assumptions, the PM approach generally showed better accuracy than PP, even on sparser or less independent datasets like Mushroom.

Limitations and Future Work

  • Scalability for Complex MRFs: The authors acknowledge that scaling their approach to truly large-scale collections of itemsets, which could lead to very complex MRFs, is a challenge. They plan to explore approximate probabilistic inference techniques to address this.
  • Streaming/Incremental Settings: The paper does not discuss how the approach would perform in a streaming or incremental data setting, which is a natural area for future work.

Summary updated

BibTeX
@inproceedings{wang2006summarizing,
  author = {Chao Wang and Srinivasan Parthasarathy},
  title = {{Summarizing itemset patterns using probabilistic models}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150495},
}
Figure