New algorithms for fast discovery of association rules
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Li Wei · 1997
Association rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identify-ing the frequent itemsets, and then forming conditional implication rules among them. In this paper we present ecient algorithms for the discovery of frequent itemsets, which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The related database items are grouped together into clusters representing the potential maximal frequent itemsets in the database. Each cluster induces a sub-lattice of the itemset lattice. Ecient lattice traversal techniques are pre-sented, which quickly identify all the true maximal frequent itemsets, and all their subsets if desired. We also present the eect of using dierent database layout schemes combined with the proposed clustering and traversal techniques. The proposed algorithms scan a (pre-processed) database only once, addressing the open question in association mining, whether all the rules can be eciently extracted in a single database pass. We experimentally compare the new algo-rithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.