Boosting association rule mining in large datasets via Gibbs sampling.
Current algorithms for association rule mining from transaction data are mostly deterministic and enumerative. They can be computationally intractable even for mining a dataset containing just a few hundred transaction items, if no action is taken to constrain the search space. In this paper, we develop a Gibbs-sampling-induced stochastic search procedure to randomly sample association rules from the itemset space, and perform rule mining from the reduced transaction dataset generated by the sample. Also a general rule importance measure is proposed to direct the stochastic search so that, as a result of the randomly generated association rules constituting an ergodic Markov chain, the overall most important rules in the itemset space can be uncovered from the reduced dataset with probability 1 in the limit. In the simulation study and a real genomic data example, we show how to boost association rule mining by an integrated use of the stochastic search and the Apriori algorithm.
School of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia;
Guoqi
G
Qian
Department of Biostatistics, University at Buffalo, The State University of New York, Buffalo, NY 14221-3000; CRRAO Advanced Institute of Mathematics, Statistics and Computer Science, Hyderabad-500046, India; crr1@psu.edu.
Calyampudi Radhakrishna
CR
Rao
Department of Mathematics and Statistics, York University, Toronto, ON, Canada M3J1P3.
Xiaoying
X
Sun
Department of Mathematics and Statistics, York University, Toronto, ON, Canada M3J1P3.
Yuehua
Y
Wu
Gibbs sampling; association rule; genomic data; transaction data