Mining Probabilistic Frequent Itemsets with Exact Methods

Probabilistic frequent itemset mining over uncertain databases is a challenging problem. The state-of-the-art algorithm uses O(nlog(2)n) time complexity to conduct the mining. We focus on this problem and design a framework, which can discover the probabilistic frequent itemsets with traditional exact frequent itemset mining methods; thus, the time complexity can be reduced to O(n). In this framework, we supply a minimum confidence to convert the uncertain database to exact database; furthermore, a sampling method is used to find the reasonable minimum confidence so that the accuracy is guaranteed. Our experiments show our method can significantly outperform the existing algorithm.