Best-first search-based approach for mining top-k closed frequent itemsets from uncertain databases

Area of Science:

• Data Mining
• Database Systems
• Machine Learning

Background:

• Data mining from uncertain data sources is crucial.
• Mining top-k closed frequent itemsets is computationally intensive due to probabilistic support evaluation and large search spaces.
• Existing depth-first search (DFS) methods often discover patterns late, leading to inefficient pruning and closure verification.

Purpose of the Study:

• To propose TUFCI, a best-first-search algorithm for mining top-k closed frequent itemsets from uncertain databases.
• To improve the efficiency and reduce the computational cost of uncertain data mining.
• To enable early discovery of strong patterns and safe termination.

Main Methods:

• TUFCI employs a best-first-search strategy using a priority queue.
• Candidates are explored in descending order of probabilistic support.
• Support-ordered exploration enhances closure checking by prioritizing supersets likely to violate the closure property.

Main Results:

• TUFCI significantly outperforms DFS-based algorithms in terms of runtime.
• The number of closure checks is substantially reduced, particularly on dense datasets.
• Early discovery of strong patterns leads to rapid threshold elevation and safe early termination.

Conclusions:

• TUFCI offers a more efficient approach to mining top-k closed frequent itemsets from uncertain databases.
• The best-first-search strategy effectively prunes the search space and reduces redundant computations.
• This method provides a significant advancement for handling large-scale uncertain data.