Probabilistic frequent itemset mining in uncertain databases
Authors:
Open Access
- 28 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 119-128
Abstract
Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets), indicating the probability that an item(set) occurs in a transaction, makes traditional techniques inapplicable. In this paper, we introduce new probabilistic formulations of frequent itemsets based on possible world semantics. In this probabilistic context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold τ. To the best of our knowledge, this is the first approach addressing this problem under possible worlds semantics. In consideration of the probabilistic formulations, we present a framework which is able to solve the Probabilistic Frequent Itemset Mining (PFIM) problem efficiently. An extensive experimental evaluation investigates the impact of our proposed techniques and shows that our approach is orders of magnitude faster than straight-forward approaches.Keywords
This publication has 12 references indexed in Scilit:
- Fast and Simple Relational Processing of Uncertain Data2008
- Efficient Processing of Top-k Queries in Uncertain Databases2008
- Bit Sequences and Biclustering of Text Documents2007
- Efficient Top-k Query Evaluation on Probabilistic Data2007
- Representing and Querying Correlated Tuples in Probabilistic Databases2007
- Geometrically Inspired Itemset Mining2006
- Efficient query evaluation on probabilistic databasesThe VLDB Journal, 2006
- Probabilistic Similarity Join on Uncertain Data2006
- Mining association rules with non-uniform privacy concerns2004
- Mining frequent patterns without candidate generationACM SIGMOD Record, 2000