2013 SummarizingProbabilisticFrequen

• (Liu et al., 2013) ⇒ Chunyang Liu, Ling Chen, and Chengqi Zhang. (2013). “Summarizing Probabilistic Frequent Patterns: A Fast Approach.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487618

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Summarizing+Probabilistic+Frequent+Patterns%3A+A+Fast+Approach
• http://dl.acm.org/citation.cfm?id=2487575.2487618&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; pattern summarization; uncertain data

Abstract

Mining probabilistic frequent patterns from uncertain data has received a great deal of attention in recent years due to the wide applications. However, probabilistic frequent pattern mining suffers from the problem that an exponential number of result patterns are generated, which seriously hinders further evaluation and analysis. In this paper, we focus on the problem of mining probabilistic representative frequent patterns (P-RFP), which is the minimal set of patterns with adequately high probability to represent all frequent patterns. Observing the bottleneck in checking whether a pattern can probabilistically represent another, which involves the computation of a joint probability of the supports of two patterns, we introduce a novel approximation of the joint probability with both theoretical and empirical proofs. Based on the approximation, we propose an Approximate P-RFP Mining (APM) algorithm, which effectively and efficiently compresses the set of probabilistic frequent patterns. To our knowledge, this is the first attempt to analyze the relationship between two probabilistic frequent patterns through an approximate approach. Our experiments on both synthetic and real-world datasets demonstrate that the APM algorithm accelerates P-RFP mining dramatically, orders of magnitudes faster than an exact solution. Moreover, the error rate of APM is guaranteed to be very small when the database contains hundreds transactions, which further affirms APM is a practical solution for summarizing probabilistic frequent patterns.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 SummarizingProbabilisticFrequen	Chengqi Zhang Ling Chen Chunyang Liu			Summarizing Probabilistic Frequent Patterns: A Fast Approach				10.1145/2487575.2487618		2013