Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report)

Details Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report) Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report)

2010-08-13

arxiv.org/abs/1008.2300v1

Computer Science

Databases

Technical Report, 21 pages

Scientific paper

Frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied on standard (certain) transaction databases. Uncertain transaction databases consist of sets of existentially uncertain items. The uncertainty of items in transactions makes traditional techniques inapplicable. In this paper, we tackle the problem of finding probabilistic frequent itemsets based on possible world semantics. In this context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold. We make the following contributions: We propose the first probabilistic FP-Growth algorithm (ProFP-Growth) and associated probabilistic FP-Tree (ProFP-Tree), which we use to mine all probabilistic frequent itemsets in uncertain transaction databases without candidate generation. In addition, we propose an efficient technique to compute the support probability distribution of an itemset in linear time using the concept of generating functions. An extensive experimental section evaluates the our proposed techniques and shows that our ProFP-Growth approach is significantly faster than the current state-of-the-art algorithm.

Affiliated with

Also associated with

No associations

Rating

Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-503138