Fast Estimation of the Pattern Frequency Spectrum

Matthijs van Leeuwen, Antti UkkonenECML/PKDD 2014 · DOI

TL;DR

This paper introduces FASTEST and SPECTRA, two novel algorithms that efficiently estimate the number of frequent patterns in a dataset. FASTEST provides accurate counts for a given frequency threshold, while SPECTRA estimates the entire "pattern frequency spectrum" (how pattern counts change with the threshold), enabling quick data characterization and threshold tuning.

What Problem Does This Paper Address?

Discovering frequent patterns (like sets of items that often appear together in transactions) is a cornerstone of data mining. However, a major hurdle is the "pattern explosion": even small changes in the minimum frequency threshold (σ) can lead to a massive, unmanageable number of patterns. This makes it difficult to choose an appropriate threshold and understand the overall pattern landscape. Existing methods for counting these patterns are computationally expensive, often taking hours or days, and even approximate methods can be complex. This paper aims to provide fast and accurate ways to estimate pattern counts, both for specific thresholds and for the entire spectrum of thresholds.

Methods

The core of the paper lies in two main contributions:

  • FASTEST (Fast Estimation): This algorithm adapts Knuth's classical method for estimating the size of a search tree. Instead of a literal search tree, FASTEST constructs a conceptual "itemset lattice" where nodes are frequent itemsets and children are frequent expansions. It then uses a sampling approach to estimate the size of this lattice, which directly corresponds to the number of frequent itemsets. A key modification is made to account for the fact that itemsets can appear multiple times in this lattice structure, ensuring each itemset is counted only once. FASTEST is also extended to handle non-monotonic constraints, like closed patterns, though with some caveats.
  • SPECTRA: This algorithm builds upon FASTEST to estimate the entire "pattern frequency spectrum" – a curve showing the number of frequent patterns for every possible frequency threshold. Instead of running FASTEST for many specific thresholds and interpolating, SPECTRA samples random thresholds and uses isotonic regression to fit a smooth, non-increasing curve that represents the spectrum. This provides a holistic view of the data's pattern landscape.

Datasets

The paper evaluates FASTEST and SPECTRA on 14 "moderately-sized" datasets. These datasets were sourced from the FIMI (Frequent Itemset Mining Implementations) and LUCS-KDD repositories. The paper notes that these datasets were chosen because exact frequent itemset counting was still feasible within a reasonable time frame for certain thresholds.

Key Insights and Ideas

  • Pattern Frequency Spectrum as a "Fingerprint": The paper proposes that the pattern frequency spectrum can serve as a unique "fingerprint" for a dataset. By comparing a dataset's spectrum to that of a random data model (where items are independent), one can quickly discern if the dataset exhibits significant structure beyond simple item independence.
  • Knuth's Algorithm's Versatility: The paper demonstrates that Knuth's algorithm, originally designed for search tree size estimation, can be effectively adapted for pattern counting problems, highlighting its broad applicability.
  • Efficiency Gains: The proposed methods offer substantial speedups compared to exact counting, reducing computation times from hours to seconds or minutes, making pattern analysis more accessible.
  • Threshold Tuning Aid: The ability to quickly estimate the pattern frequency spectrum provides a valuable tool for users to tune the minimum frequency threshold (σ) to find a balance between too few and too many patterns.

Key Results

  • FASTEST Accuracy: FASTEST provides highly accurate estimates for the number of frequent itemsets, often matching the exact counts in expectation, with 95% confidence intervals indicating results within the same order of magnitude.
  • FASTEST Efficiency: FASTEST significantly outperforms exact counting in terms of runtime, achieving speedups of up to 1230x on some datasets. It also requires substantially fewer frequency computations than exact methods.
  • SPECTRA Accuracy: SPECTRA provides accurate estimates of the pattern frequency spectrum. With 1000 samples, it can estimate 95% of the full spectrum with an error of less than one order of magnitude, and with 10000 samples, this error is often reduced to 0.1-0.2.
  • Closed Pattern Estimation: The adaptation of FASTEST for closed patterns also yields good estimates, though it can be more sensitive to the number of samples for datasets with extreme ratios of frequent to closed itemsets.

Limitations and Future Work

  • Non-monotonic Constraints: While FASTEST has an extension for non-monotonic constraints like closed patterns, the paper notes that this approach can lead to poor estimates if not enough samples are used, especially for datasets with a high variance in individual path estimates. More detailed investigation into this area is suggested.
  • Dataset Size: The experiments were conducted on "moderately-sized" datasets. The paper suggests that the approach can be parallelized for very large datasets, which would be a valuable future direction.
  • Advanced Models for Spectra: The paper mentions that more advanced models could be used for generating expected frequency curves, which could lead to more nuanced comparisons with actual data spectra.
  • Query-Based Spectra: The authors propose exploring "query-based frequency spectra," which would focus on patterns that are supersets of a given query pattern, offering insights into local data structure.

Summary updated

BibTeX
@inproceedings{leeuwen2014fast,
  author = {Matthijs van Leeuwen and Antti Ukkonen},
  title = {{Fast Estimation of the Pattern Frequency Spectrum}},
  booktitle = {ECML/PKDD},
  year = {2014},
  doi = {10.1007/978-3-662-44851-9\_8},
}
Figure