2010 ProbablytheBestItemsets

• (Tatti, 2010) ⇒ Nikolaj Tatti. (2010). “Probably the Best Itemsets.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835843

Subject Headings:

Notes

• Categories and Subject Descriptors: H.2.8 Database management: Database applications — Data mining; G.3 Probability and Statistics: Markov processes
• General Terms: Algorithms, Theory

Cited By

• http://scholar.google.com/scholar?q=%22Probably+the+best+itemsets%22+2010
• http://portal.acm.org/citation.cfm?id=1835843&preflayout=flat#citedby

Quotes

Author Keywords

Itemset mining, exponential models, decomposable models, junction trees, Bayesian model selection, MCMC.

Abstract

One of the main current challenges in itemset mining is to discover a small set of high-quality itemsets. In this paper we propose a new and general approach for measuring the quality of itemsets. The method is solidly founded in Bayesian statistics and decreases monotonically, allowing for efficient discovery of all interesting itemsets. The measure is defined by connecting statistical models and collections of itemsets. This allows us to score individual itemsets with the probability of them occuring in random models built on the data.

As a concrete example of this framework we use exponential models. This class of models possesses many desirable properties. Most importantly, Occam's razor in Bayesian model selection provides a defence for the pattern explosion. As general exponential models are infeasible in practice, we use decomposable models; a large sub-class for which the measure is solvable. For the actual computation of the score we sample models from the posterior distribution using an MCMC approach.

 Experimentation on our method demonstrates the measure works in practice and results in interpretable and insightful itemsets for both synthetic and real-world data.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 ProbablytheBestItemsets	Nikolaj Tatti			Probably the Best Itemsets		KDD-2010 Proceedings		10.1145/1835804.1835843		2010