Traversing Itemset Lattice with Statistical Metric Pruning Shinichi Morishita and Jun Sese   View Paper (PDF)   Return to Data Mining / Information Dependencies Abstract We study how to efficiently compute significant association rules according to common statistical measures such as a chi-squared value or correlation coefficient. For this purpose, one might consider to use of the Apriori algorithm, but the algorithm needs major conversion, because none of these statistical metrics are anti-monotone, and the use of higher support for reducing the search space cannot guarantee solutions in its the search space. We here present a method of estimating a tight upper bound on the statistical metric associated with any superset of an itemset, as well as the novel use of the resulting information of upper bounds to prune unproductive supersets while traversing itemset lattices. Experimental tests demonstrate the efficiency of this method. References Note: References link to DBLP on the Web. [1] Charu C. Aggarwal , Philip S. Yu : A New Framework For Itemset Generation. PODS 1998 : 18-24 [2] Rakesh Agrawal , Tomasz Imielinski , Arun N. Swami : Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993 : 207-216 [3] Rakesh Agrawal , Ramakrishnan Srikant : Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994 : 487-499 [4] Roberto J. Bayardo Jr. : Efficiently Mining Long Patterns from Databases. SIGMOD Conference 1998 : 85-93 [5] Roberto J. Bayardo Jr. , Rakesh Agrawal : Mining the Most Interesting Rules. KDD 1999 : 145-154 [6] Sergey Brin , Rajeev Motwani , Craig Silverstein : Beyond Market Baskets: Generalizing Association Rules to Correlations. SIGMOD Conference 1997 : 265-276 [7] Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur : Dynamic Itemset Counting and Implication Rules for Market Basket Data. SIGMOD Conference 1997 : 255-264 [8] Sergey Brin , Rajeev Rastogi , Kyuseok Shim : Mining Optimized Gain Rules for Numeric Attributes. KDD 1999 : 135-144 [9] Takeshi Fukuda , Yasuhiko Morimoto , Shinichi Morishita , Takeshi Tokuyama : Constructing Efficient Decision Trees by Using Optimized Numeric Association Rules. VLDB 1996 : 146-155 [10] Takeshi Fukuda , Yasuhiko Morimoto , Shinichi Morishita , Takeshi Tokuyama : Constructing Efficient Decision Trees by Using Optimized Numeric Association Rules. VLDB 1996 : 146-155 [11] Takeshi Fukuda , Yasuhiko Morimoto , Shinichi Morishita , Takeshi Tokuyama : Data Mining Using Two-Dimensional Optimized Accociation Rules: Scheme, Algorithms, and Visualization. SIGMOD Conf. 1996 : 13-23 [12] Takeshi Fukuda , Yasuhiko Morimoto , Shinichi Morishita , Takeshi Tokuyama : Mining Optimized Association Rules for Numeric Attributes. PODS 1996 : 182-191 [13] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [14] ... [15] Laks V. S. Lakshmanan , Raymond T. Ng , Jiawei Han , Alex Pang : Optimization of Constrained Frequent Set Queries with 2-variable Constraints. SIGMOD Conference 1999 : 157-168 [16] Bing Liu , Wynne Hsu , Yiming Ma : Pruning and Summarizing the Discovered Associations. KDD 1999 : 125-134 [17] Yasuhiko Morimoto , Takeshi Fukuda , Hirofumi Matsuzawa , Takeshi Tokuyama , Kunikazu Yoda : Algorithms for Mining Association Rules for Binary Segmentations of Huge Categorical Databases. VLDB 1998 : 380-391 [18] Yasuhiko Morimoto , Hiromu Ishii , Shinichi Morishita : Efficient Construction of Regression Trees with Range and Region Splitting. VLDB 1997 : 166-175 [19] Shinichi Morishita : On Classification and Regression. Discovery Science 1998 : 40-57 [20] ... [21] ... [22] Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang : Exploratory Mining and Pruning Optimizations of Constrained Association Rules. SIGMOD Conference 1998 : 13-24 [23] Jong Soo Park , Ming-Syan Chen , Philip S. Yu : An Effective Hash Based Algorithm for Mining Association Rules. SIGMOD Conference 1995 : 175-186 [24] Craig Silverstein , Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman : Scalable Techniques for Mining Causal Structures. VLDB 1998 : 594-605 [25] Shalom Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal : Query Flocks: A Generalization of Association-Rule Mining. SIGMOD Conference 1998 : 1-12 BIBTEX @inproceedings{DBLP:conf/pods/MorishitaS00,   author    = {Shinichi Morishita and                 Jun Sese},    title     = {Traversing Itemset Lattice with Statistical Metric Pruning},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {226-236},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.