Boosting association rule mining in large datasets via Gibbs sampling.

Area of Science:

• Data Mining
• Computational Statistics

Background:

• Traditional association rule mining algorithms are deterministic and enumerative, leading to computational intractability with large datasets.
• Constraining the search space is crucial for efficient mining of transaction data.

Purpose of the Study:

• To develop a computationally efficient stochastic search procedure for association rule mining.
• To propose a general rule importance measure to guide the search process.
• To demonstrate the effectiveness of the proposed method in uncovering important association rules.

Main Methods:

• A Gibbs-sampling-induced stochastic search procedure is developed to sample association rules from the itemset space.
• Rule mining is performed on a reduced transaction dataset generated by the stochastic sample.
• A rule importance measure is introduced to direct the stochastic search, forming an ergodic Markov chain.

Main Results:

• The stochastic search procedure effectively samples association rules, enabling mining on a reduced dataset.
• The proposed importance measure guides the search towards uncovering the most significant rules.
• Integration with the Apriori algorithm boosts association rule mining performance, as shown in simulations and genomic data.

Conclusions:

• The Gibbs-sampling-induced stochastic search offers a computationally efficient alternative to deterministic methods for association rule mining.
• This approach enhances the ability to discover important association rules, particularly in large and complex datasets.
• The integrated use of stochastic search and the Apriori algorithm provides a powerful framework for association rule discovery.