PaperlayerView exact revision on arXiv

Source-linked AI summary

Mining Frequent Itemsets over Uncertain Databases

Yongxin Tong, Lei Chen, Yurong Cheng, Philip S. Yu

arXiv:1208.0292v1cs.DB

TL;DR

Mining frequent itemsets in uncertain databases is complicated by two definitions of frequency and inconsistent results from nonuniform implementations. The paper relates the definitions, supplies uniform algorithm baselines, and evaluates them experimentally, finding that large databases can unify the definitions and expose clearer performance patterns.

  • Problem

    Uncertain databases use expected support or frequent probability to define frequency, while nonuniform implementations produce inconsistent comparisons among algorithms.

  • Method

    The paper mathematically relates the two definitions, provides uniform implementations of eight representative algorithms, and evaluates them across varied benchmark datasets and measures.

  • Results

    For sufficiently large databases, the two definitions can be unified, while fair experiments clarify prior contradictions and identify distinct performance patterns among algorithms.

  • Takeaways & Limitations

    Expected-support solutions can replace more expensive probabilistic mining in sufficiently large databases when support variance is also computed.

  • Takeaways & Limitations

    Poisson-based PDUApriori only approximately determines probabilistic frequency and cannot return frequent-probability values.

Abstract

from arXiv · show

In recent years, due to the wide applications of uncertain data, mining frequent itemsets over uncertain databases has attracted much attention. In uncertain databases, the support of an itemset is a random variable instead of a fixed occurrence counting of this itemset. Thus, unlike the corresponding problem in deterministic databases where the frequent itemset has a unique definition, the frequent itemset under uncertain environments has two different definitions so far. The first definition, referred as the expected support-based frequent itemset, employs the expectation of the support of an itemset to measure whether this itemset is frequent. The second definition, referred as the probabilistic frequent itemset, uses the probability of the support of an itemset to measure its frequency. Thus, existing work on mining frequent itemsets over uncertain databases is divided into two different groups and no study is conducted to comprehensively compare the two different definitions. In addition, since no uniform experimental platform exists, current solutions for the same definition even generate inconsistent results. In this paper, we firstly aim to clarify the relationship between the two different definitions. Through extensive experiments, we verify that the two definitions have a tight connection and can be unified together when the size of data is large enough. Secondly, we provide baseline implementations of eight existing representative algorithms and test their performances with uniform measures fairly. Finally, according to the fair tests over many different benchmark data sets, we clarify several existing inconsistent conclusions and discuss some new findings.

1. INTRODUCTION

Uncertain frequent-itemset mining faces two competing definitions and inconsistent experimental results. The paper relates the definitions, standardizes algorithm comparisons, and evaluates representative methods across varied datasets.

  • Uncertain data mining is motivated by applications whose collected data contain inherent sensor or data uncertainty.
  • Expected support-based and probabilistic frequent itemsets measure frequency using different properties of the support random variable.The first uses expected support, while the second uses the probability that support exceeds a threshold.
  • The two definitions are mathematically connected through the Poisson Binomial support distribution and can be unified for sufficiently large databases.Expected value and variance can support approximate frequent-probability computation when transaction counts are large enough.
  • Prior studies report contradictory runtime conclusions for algorithms such as UFP-growth and UApriori, partly because implementations lack uniform baselines.Differences such as float versus double probability storage can distort memory comparisons.
  • The paper provides uniform implementations of representative algorithms and evaluates them with common measures across six dense or sparse datasets with varied probability distributions.The datasets include Normal versus Zipf and high versus low probability distributions.

2. DEFINITIONS

The section defines uncertain transactions, expected support, and frequent probability, then formalizes the two corresponding frequent-itemset semantics. Examples illustrate how thresholds classify itemsets under each definition.

  • An uncertain transaction contains items with appearance probabilities, making an itemset’s support a random variable over the database.
  • Expected support is the expected number of transactions containing an itemset.
  • An itemset is expected-support-based frequent when its expected support reaches the minimum expected support threshold.
  • Frequent probability is the probability that an itemset’s support reaches the minimum support threshold.
  • An itemset is probabilistic frequent when its frequent probability exceeds the probabilistic frequent threshold.
  • With min sup=0.5 and pft=0.7, itemset {A} is probabilistic frequent because its frequent probability is 0.4 + 0.32 > 0.7.

3. ALGORITHMS OF FREQUENT ITEMSET MINING

The paper groups eight algorithms into expected-support-based, exact probabilistic, and approximate probabilistic approaches. Their computational costs differ according to whether they compute expectations, exact probabilities, or moment-based approximations.

  • Expected-support-based algorithms: Expected-support-based algorithms find itemsets using expected support, with O(N) cost per itemset.N denotes the number of transactions.
  • Exact probabilistic algorithms: Exact probabilistic algorithms report exact frequent probabilities but require at least O(NlogN) computation per itemset.Chernoff-bound pruning can reduce runtime by avoiding redundant processing.
  • Approximate probabilistic algorithms: Approximate probabilistic algorithms use expectation and variance to obtain high-quality frequent-probability estimates with O(N) cost.They return complete probability information when uncertain databases are large enough.
  • Approximate probabilistic algorithms: The approximate algorithms bridge the expected-support and probabilistic definitions by combining moment computation with probability estimation.

3.1 Expected Support-based Frequent Algorithms

Expected support-based mining includes UApriori, UFP-growth, and UH-Mine, using breadth-first or depth-first search with different data structures. Their performance depends on dataset characteristics, while uncertainty reduces tree compression and can increase redundant computation.

  • Algorithm frameworks: UApriori uses generate-and-test with breadth-first search, whereas UFP-growth and UH-Mine use divide-and-conquer with depth-first search.These are the three representative expected support-based algorithms summarized in the section.
  • Performance considerations: UApriori is usually fastest on dense uncertain datasets, while UH-Mine's structure is suited to sparse data and avoids repeatedly rebuilding shared paths.The section contrasts breadth-first candidate generation with divide-and-conquer approaches across dataset densities.
  • UApriori: UApriori repeatedly joins expected support-based frequent items and applies downward-closure pruning to eliminate infrequent supersets.Decremental pruning can additionally reject candidates when an upper bound on expected support falls below minimum expected support.
  • UFP-Growth: UFP-growth builds a UFP-tree, then recursively constructs conditional subtrees to mine expected support-based frequent itemsets.Each node stores an item label, appearance probability, and the number of transactions sharing its path from the root.
  • UFP-Growth: Uncertain item probabilities reduce UFP-tree prefix sharing, producing many conditional subtrees and redundant computation compared with deterministic FP-growth.Items share a node only when both their labels and appearance probabilities match.
  • UH-Mine: UH-Mine builds a head table and UH-Struct, then recursively generates head tables for different prefixes using depth-first search.UH-Struct assigns each item a label, appearance probability, and pointer; the approach is associated with sparse databases.

3.2 Exact Probabilistic Frequent Algorithms

Exact probabilistic frequent-itemset algorithms compute frequent probabilities directly, using dynamic programming or divide-and-conquer, while Chernoff pruning accelerates rejection of unpromising itemsets.

  • Exact probabilistic algorithms: DP and DC first compute each itemset’s frequent probability, then return itemsets exceeding the probability threshold.DP uses the Apriori framework; DC recursively divides the database and combines probability distributions.
  • Divide-and-conquer algorithms: DC reduces its complexity from O(N^2) to O(NlogN) by using Fast Fourier Transform during the conquering step.N is the number of transactions in the uncertain database.
  • Chernoff-bound pruning: Chernoff bound-based pruning tests whether an itemset can be probabilistically frequent before exact probability computation.The bound uses the expected support and is designed to filter unpromising probabilistic infrequent itemsets early.
  • Chernoff-bound pruning: O(N) is the time complexity of computing the Chernoff bound, making pruning faster than exact probability calculation.N is the number of transactions.
  • Accuracy analysis: DP and DC identify probabilistic frequent itemsets accurately, whereas Chernoff pruning can produce a few false positives because it uses an upper bound.The pruning method is therefore an efficiency-oriented test rather than an exact probability computation.

3.3 Approximate Probabilistic Frequent Algorithms

Approximate probabilistic algorithms replace exact Poisson Binomial calculations with Poisson or Normal approximations, connecting probabilistic mining to expected-support methods and enabling specialized frameworks for sparse data.

  • Approximation methods: Poisson and Normal distributions can effectively approximate itemset-support distributions when uncertain databases are large enough.Both approximations rely on the support being modeled as a Poisson Binomial random variable.
  • Poisson distribution-based UApriori: PDUApriori converts a probabilistic threshold into an expected-support threshold and uses UApriori to mine the resulting itemsets.Its Poisson parameter λ equals expected support.
  • Poisson distribution-based UApriori: PDUApriori approximately determines probabilistic frequency but cannot return frequent-probability values.Its approach exploits the Poisson parameter’s relationship to expectation and variance.
  • Normal distribution-based UApriori: NDUApriori uses the Apriori framework and the Normal CDF to calculate frequent probabilities, but is impractical for very large sparse databases.The limitation follows from its use of the Apriori framework.
  • Normal distribution-based UH-Mine: NDUH-Mine combines UH-Mine with Normal approximation to target sparse uncertain databases and outperforms NDUApriori on large sparse data.The method computes each itemset’s variance while UH-Mine obtains expected support.
  • Relationship between definitions: Normal-approximation algorithms bridge expected-support and probabilistic frequent-itemset mining, allowing existing expected-support algorithms to be reused.The paper specifically identifies NDUApriori as fastest in sufficiently large databases under the probabilistic definition.
  • Algorithm comparison: All three approximate algorithms have O(N) complexity for computing each itemset’s frequent probability, so framework and approximation method become the main comparison dimensions.The paper compares these dimensions in Table 5.

4. EXPERIMENTS

Experiments show that algorithm performance depends strongly on dataset density, minimum support, and the mining definition. Across expected-support and probabilistic settings, the fastest methods trade off against memory usage under different conditions.

  • Scalability: Expected-support algorithms scale linearly with transaction count, while UApriori’s memory growth is steadier than that of structure-based methods.UApriori avoids the extra memory required to build specialized uncertain-data structures.
  • Expected Support-based Algorithms: UApriori is fastest on dense datasets with high min esup, whereas UH-Mine wins otherwise.UApriori also uses less memory in the dense, high-threshold setting; UH-Mine is generally preferable for sparse data or lower thresholds.
  • Expected Support-based Algorithms: UFP-growth is usually the slowest expected-support algorithm and has the highest memory cost.Its limited shared paths lead to redundant recursive computation and conditional subtrees.
  • Effect of the Zipf distribution: Increasing Zipf skew decreases expected-support running time and memory cost because more items receive zero probability.Under Zipf distributions, UH-Mine usually performs very well.
  • Exact Probabilistic Frequent Algorithms: DCB is fastest in most exact probabilistic experiments but uses more memory than DPB because divide-and-conquer stores recursive results.DPB and DPNB generally require less memory, while DCB and DCNB trade memory for efficiency.
  • Exact Probabilistic Frequent Algorithms: Chernoff-bound pruning accelerates exact probabilistic mining by filtering infrequent itemsets at O(N) cost instead of exact calculations costing O(NlogN) or O(N^2 × min sup).With pruning, DCB is faster than DPB; without it, DCNB is faster than DPNB.
  • Approximate Probabilistic Frequent Algorithms: Approximate probabilistic methods are fastest and use less memory than exact DCB, with PDUApriori and NDUApriori favored on dense high-threshold data and NDUH-Mine otherwise.NDUH-Mine is especially competitive on sparse datasets.

5. CONCLUSIONS

The paper unifies two frequent-itemset definitions through their close relationship and evaluates representative algorithms under a common experimental framework. Its benchmark study resolves contradictory prior findings and identifies condition-dependent performance patterns.

  • Contributions: The study clarifies a close relationship between expected-support and probabilistic frequent-itemset definitions.It argues that efficient solutions for the first definition can replace current solutions for the second under the identified relationship.
  • Contributions: Eight representative algorithms are implemented and evaluated fairly using uniform measurements across many benchmark datasets.The experiments verify inconsistent prior conclusions and reveal new rules for uncertain frequent-itemset mining.
Loading 1208.0292v1…