Mining top-K frequent itemsets through progressive sampling

Andrea Pietracaprina, Matteo Riondato, Eli Upfal, Fabio Vandin

Abstract

In the era of massive data, identifying the most frequent patterns—Frequent Itemset Mining (FIM)—is a critical yet computationally expensive task. Traditional methods often require multiple passes over the entire dataset or rely on user-defined support thresholds that are difficult to tune. This paper explores the use of random sampling to identify the "Top-K" most frequent itemsets. We present a theoretical framework for determining the minimum sample size required to guarantee an $\epsilon$-approximation of the Top-K set and introduce a progressive sampling algorithm that optimizes performance based on the inherent characteristics of the data.

1. Introduction

Frequent Itemset Mining is a cornerstone of data mining, with applications ranging from market basket analysis to web link analysis. However, as datasets scale into billions of transactions, the cost of exact mining becomes prohibitive. While sampling offers a potential solution, it introduces uncertainty: how can we be sure that a sample contains the true most frequent items?

Previous research into sampling for FIM typically focused on fixed support thresholds. This paper shifts the focus to Top-K mining, where the goal is to find the $K$ most frequent itemsets regardless of their absolute frequency. The primary challenge lies in the fact that the frequency of the $K$-th itemset is unknown a priori, making it difficult to determine the necessary sample size for a reliable result.

2. Theoretical Framework and Bounds

The authors define a "good" result through the lens of an $\epsilon$-approximation. An $\epsilon$-approximation for the Top-K frequent itemsets is a set that:

  1. Includes all itemsets with a frequency significantly higher than the $K$-th most frequent itemset.
  2. Excludes itemsets with a frequency significantly lower than the $K$-th.
  3. Provides frequency estimates for all included itemsets within an error margin of $\epsilon$.

Using Chernoff bounds and union bounds, the researchers derived a tight theoretical bound for the sample size $t$. This bound ensures that the resulting sample provides an $\epsilon$-approximation with a confidence level of $1-\delta$. A key contribution of this work is the proof that this bound is independent of the total number of transactions in the dataset, depending instead on the desired accuracy ($\epsilon$), the number of items ($K$), and the maximum itemset size ($w$).

3. The Progressive Sampling Algorithm

While the theoretical bound provides a worst-case guarantee, real-world datasets often allow for much smaller samples. To exploit this, the authors proposed a progressive sampling approach:

  • Initialization: Start with a small initial sample.
  • Mining and Estimation: Mine the sample to find the Top-K candidates and estimate their frequencies.
  • Stopping Condition: Evaluate whether the "gap" between the $K$-th itemset and the potential candidates outside the Top-K is large enough to satisfy the mathematical requirements for an $\epsilon$-approximation.
  • Iteration: If the condition is not met, increase the sample size and repeat.

To maintain memory efficiency during this process, the algorithm utilizes Count-Min filters. These probabilistic data structures allow the system to track a vast number of itemset combinations in $O(\log m)$ space, preventing the memory explosion typically associated with FIM.

4. Experimental Evaluation

The methodology was tested against three diverse benchmarks from the FIMI repository:

  • T10I4D100K: A synthetic retail dataset.
  • kosarak: Clickstream data from a news portal (large-scale).
  • webdocs: A massive dataset of web page contents.

4.1 Performance and Efficiency

The progressive algorithm demonstrated significant efficiency gains. For instance, on the kosarak dataset, while the theoretical bound suggested a 20% sample, the progressive algorithm often reached a valid conclusion using a much smaller fraction of the data. The efficiency is directly tied to the "frequency gap"—the more the top items stand out from the noise, the faster the algorithm terminates.

4.2 Accuracy and Reliability

In empirical tests, the algorithm proved highly robust:

  • Recall: It consistently identified over 95% of the true Top-K itemsets.
  • Precision: The actual error in frequency estimation was frequently 5 to 10 times smaller than the user-specified $\epsilon$.
  • Success Rate: In 100% of the experimental trials, the algorithm produced a valid $\epsilon$-approximation.

5. Conclusion and Future Work

This research provides a rigorous mathematical foundation for Top-K sampling in FIM. By proving that sample sizes can remain independent of dataset size, the authors offer a scalable path forward for big data analytics.

However, some limitations remain. The progressive approach is most effective when the maximum itemset size ($w$) is relatively small; as $w$ increases, the search space expands, making the stopping condition more difficult to verify. Future research may focus on optimizing the Count-Min filter implementations and further characterizing the dataset properties that maximize the efficiency of progressive sampling.

Summary updated

BibTeX
@article{pietracaprina2010mining,
  author = {Andrea Pietracaprina and Matteo Riondato and Eli Upfal and Fabio Vandin},
  title = {{Mining top-K frequent itemsets through progressive sampling}},
  journal = {Data Min. Knowl. Discov.},
  year = {2010},
  doi = {10.1007/s10618-010-0185-7},
}
Figure