Fast Algorithms for Mining Association Rules（挖掘关联规则的快速算法）.pdf

Fast Algorithms for Mining Association Rules Rakesh Agrawal Ramakrishnan Sant* IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120 Abstract tires and auto accessoriesalso get automotive services We consider the problem of discovering association rules done. Finding all such rules is valuable for cross- between items in a large database of sales transactions. marketing and attached mailing applications. Other We present two new algorithms for solving thii problem applications include catalog design, add-on sales, that are fundamentally different from the known algo- store layout, and customer segmentation based on rithms. Empirical evaluation shows that these algorithms buying patterns. The databases involved in these outperform the known algorithms by factors ranging from applications are very large. It is imperative, therefore, three for small problems to more than an order of mag- to have fast algorithms for this task. nitude for large problems. We also show how the best features of the two proposedalgorithms can be combined The following is a formal statement of the problem into a hybrid algorithm, called AprioriHybrid. Scale-up [4]: Let Z = {ir,iz, . . . , im} be a set of literals, experiments show that AprioriHybrid scales linearly with called items. Let 2) be a set of