2011 DirectLocalPatternSamplingbyEff

• (Boley et al., 2011) ⇒ Mario Boley, Claudio Lucchese, Daniel Paurat, and Thomas Gärtner. (2011). “Direct Local Pattern Sampling by Efficient Two-step Random Procedures.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020500

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Direct+Local+Pattern+Sampling+by+Efficient+Two-step+Random+Procedures
• http://dl.acm.org/citation.cfm?id=2020408.2020500&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; data mining; frequent sets; local pattern discovery; pattern-based classification; sampling; theory

Abstract

We present several exact and highly scalable local pattern sampling algorithms. They can be used as an alternative to exhaustive local pattern discovery methods (e.g, frequent set mining or optimistic-estimator-based subgroup discovery) and can substantially improve efficiency as well as controllability of pattern discovery processes. While previous sampling approaches mainly rely on the Markov Chain Monte Carlo method, our procedures are direct, i.e., non process-simulating, sampling algorithms. The advantages of these direct methods are an almost optimal time complexity per pattern as well as an exactly controlled distribution of the produced patterns. Namely, the proposed algorithms can sample (item -) sets according to frequency, area, squared frequency, and a class discriminativity measure. Experiments demonstrate that these procedures can improve the accuracy of pattern-based models similar to frequent sets and often also lead to substantial gains in terms of scalability.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 DirectLocalPatternSamplingbyEff	Thomas Gärtner Mario Boley Claudio Lucchese Daniel Paurat			Direct Local Pattern Sampling by Efficient Two-step Random Procedures				10.1145/2020408.2020500		2011