Probabilistic frequent itemset mining in uncertain databases

TLDR

Probabilistic frequent itemset mining in uncertain transaction databases differs semantically and computationally from traditional techniques for certain databases, because existential uncertainty of items makes those techniques inapplicable. The paper introduces new probabilistic formulations of frequent itemsets based on possible world semantics. In this probabilistic context, an itemset X is frequent if the probability that X occurs in at least minSup transactions exceeds threshold τ, and the authors present a framework that efficiently solves the PFIM problem using these formulations. This is the first approach addressing PFIM under possible worlds semantics, and experimental evaluation shows it is orders of magnitude faster than straightforward methods.

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.