Quick mining in dense data: applying probabilistic support prediction in depth-first order.

Area of Science:

• Data Mining and Machine Learning
• Computational Complexity and Algorithm Design

Background:

• Frequent Itemset Mining (FIM) is crucial for association rule mining but computationally intensive, especially for dense datasets.
• Existing approximate FIM algorithms balance efficiency and accuracy, but some, like Probabilistic Breadth-First (ProbBF), suffer from high memory consumption on dense data.

Purpose of the Study:

• To propose a novel FIM algorithm, Probabilistic Depth-First (ProbDF), that addresses the memory inefficiency of breadth-first approaches.
• To leverage a Probabilistic Support Prediction Model (PSPM) for efficient and scalable FIM, particularly for dense datasets.

Main Methods:

• ProbDF employs a depth-first search strategy, discarding transaction data after initial frequent itemsets (size 1 and 2) are found.
• It utilizes a lightweight Probabilistic Support Prediction Model (PSPM) to probabilistically predict the support of larger itemsets without accessing transactional data.

Main Results:

• ProbDF demonstrates significant efficiency in both time and space compared to existing methods on real-world benchmark datasets.
• The algorithm successfully identifies the majority of frequent itemsets, showcasing its effectiveness for dense data scenarios.

Conclusions:

• ProbDF offers an efficient and memory-conscious alternative for frequent itemset mining, particularly in dense data environments.
• While achieving high efficiency, the probabilistic nature of ProbDF introduces an inherent trade-off with absolute accuracy.