2015 MiningFrequentItemsetsthroughPr

• (Riondato & Upfal, 2015) ⇒ Matteo Riondato, and Eli Upfal. (2015). “Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783265

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Mining+Frequent+Itemsets+through+Progressive+Sampling+with+Rademacher+Averages
• http://dl.acm.org/citation.cfm?id=2783258.2783265&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; frequent itemsets; pattern mining; rademacher averages; sampling; statistical learning theory

Abstract

We present an algorithm to extract a high-quality approximation of the (top-k) Frequent itemsets (FIs) from random samples of a transactional dataset. With high probability the approximation is a superset of the FIs, and no itemset with frequency much lower than the threshold is included in it. The algorithm employs progressive sampling, with a stopping condition based on bounds to the empirical Rademacher average, a key concept from statistical learning theory. The computation of the bounds uses characteristic quantities that can be obtained efficiently with a single scan of the sample. Therefore, evaluating the stopping condition is fast, and does not require an expensive mining of each sample. Our experimental evaluation confirms the practicality of our approach on real datasets, outperforming approaches based on one-shot static sampling.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 MiningFrequentItemsetsthroughPr	Eli Upfal Matteo Riondato			Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages				10.1145/2783258.2783265		2015