Exploring constraints to efficiently mine emerging patterns from large high-dimensional datasets
Xiuzhen Zhang, Guozu Dong, Kotagiri Ramamohanarao · 2000
Emerging patterns (EPs) were proposed recently to capture changes or dierences betw een datasets: an EP is a multivariate feature whose support increases sharply from a background dataset to a target dataset, and the support ratio is called its gro wth rate.Interesting long EPs often have l o w support; mining suc h EPs from high-dimensional datasets is a great challenge due to the combinatorial explosion of the number of candidates.We propose a Constraint-based EP Miner, ConsEPMiner, that utilizes tw o types of constraints for eectively pruning the search space: External constrain tsare user-giv en minimums on support, growth rate, and growth-rate improvement to con ne the resulting EP set.Inheren t constrain ts | same subset support, top growth rate, and same origin | are deriv ed from the propertiesof EPs and datasets, and are solely for pruning the search space and saving computation.ConsEPMiner can eÆciently mine all EPs at low support on large highdimensional datasets, with low minimums on growth rate and growth-rate improvement.In comparison, the widely known Apriori-like approach is ineective on high-dimensional data.While ConsEPMiner adopts several ideas from Dense-Miner [4], a recent constrain t-based association rule miner, its main new contributions are the introduction of inherent constrain ts and the w ays to use them together with externalconstrain ts for eÆcien t EP mining from dense datasets.Experiments on dense data sho w that, at low support, Con-sEPMiner outperforms the Apriori-like approach b y o r d e r s of magnitude and is more than twice as fast as the Dense-Miner approach.D, supp(X), is jft2DjXtgj jDj .