On the discovery of significant statistical quantitative rules

ABSTRACT

In this paper we study market share rules, rules that have a certain market share statistic associated with them. Such rules are particularly relevant for decision making from a business perspective. Motivated by market share rules, in this paper we consider statistical quantitative rules (SQ rules) that are quantitative rules in which the RHS can be any statistic that is computed for the segment satisfying the LHS of the rule. Building on prior work, we present a statistical approach for learning all significant SQ rules, i.e., SQ rules for which a desired statistic lies outside a confidence interval computed for this rule. In particular we show how resampling techniques can be effectively used to learn significant rules. Since our method considers the significance of a large number of rules in parallel, it is susceptible to learning a certain number of "false" rules. To address this, we present a technique that can determine the number of significant SQ rules that can be expected by chance alone, and suggest that this number can be used to determine a "false discovery rate" for the learning procedure. We apply our methods to online consumer purchase data and report the results.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Yonatan Aumann , Yehuda Lindell, A statistical theory for quantitative association rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.261-270, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312243]
• 3: Stephen D. Bay , Michael J. Pazzani, Detecting change in categorical data: mining contrast sets, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.302-306, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312263]
• 4: Benjamini, Y. and Hochberg, Y., Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing, Journal of Royal Statistical Society B, vol. 57, iss. 1, pp. 289--300, 1995.
• 5: Richard J. Bolton , Niall M. Adams, An iterative hypothesis-testing strategy for pattern discovery, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956760]
• 6: Richard J. Bolton , David J. Hand, Significance Tests for Patterns in Continuous Data, Proceedings of the 2001 IEEE International Conference on Data Mining, p.67-74, November 29-December 02, 2001
• 7: Richard J. Bolton , David J. Hand , Niall M. Adams, Determining Hit Rate in Pattern Search, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.36-48, September 16-19, 2002
• 8: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 9: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 10: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 11: Peter Clark , Tim Niblett, The CN2 Induction Algorithm, Machine Learning, v.3 n.4, p.261-283, March 1989 [doi>10.1023/A:1022641700528]
• 12: Clearwater, S. and Provost, F., Rl4: A Tool for Knowledge-Based Induction, in Procs. of the Second International IEEE Conference on Tools for Artificial Intelligence, pp. 24--30, 1990.
• 13: Efron, B. and Tibshirani, R. J., An Introduction to the Bootstrap. New York, NY: Chapman & Hall, 1993.
• 14: Eibe Frank , Ian H. Witten, Using a Permutation Test for Attribute Selection in Decision Trees, Proceedings of the Fifteenth International Conference on Machine Learning, p.152-160, July 24-27, 1998
• 15: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada
• 16: Good, P., Permutation Tests: A Practical Guide to Resampling Methods for Testing Hypotheses - 2nd Edition. New York: Springer, 2000.
• 17: Hsu, J. C., Multiple Comparisons - Theory and Methods. London, UK: Chapman & Hall, 1996.
• 18: Jensen, D., Knowledge Discovery through Induction with Randomization Testing, in Proceedings of the 1991 Knowledge Discovery in Databases Workshop, pp. 148--159, Menlo Park, 1991.
• 19: David D. Jensen , Paul R. Cohen, Multiple Comparisons in Induction Algorithms, Machine Learning, v.38 n.3, p.309-338, March 2000 [doi>10.1023/A:1007631014630]
• 20: Kohavi, R., A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection, in Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pp. 1137--1143, San Mateo, CA, 1995.
• 21: Yongwon Lee , Bruce G. Buchanan , John M. Aronis, Knowledge-Based Learning in Exploratory Science: Learning Rules to Predict Rodent Carcinogenicity, Machine Learning, v.30 n.2-3, p.217-240, Feb./ March, 1998 [doi>10.1023/A:1007404308006]
• 22: Ling, C. X. and Li, C., Data Mining for Direct Marketing: Problems and Solutions, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 73--79, New York, NY, 1998.
• 23: Bing Liu , Wynne Hsu , Yiming Ma, Identifying non-actionable association rules, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.329-334, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502560]
• 24: D. R. Mani , James Drew , Andrew Betz , Piew Datta, Statistics and data mining techniques for lifetime value modeling, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.94-103, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312205]
• 25: Megiddo, N. and Srikant, R., Discovering Predictive Association Rules, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 274--278, New York, NY, 1998.
• 26: Oates, T. and Jensen, D., Large Datasets Lead to Overly Complex Models: An Explanation and a Solution, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 294--298, Menlo Park, CA, 1998.
• 27: Padmanabhan, B. and Tuzhilin, A., A Belief-Driven Method for Discovering Unexpected Patterns, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 94--100, New York, NY, 1998.
• 28: Balaji Padmanabhan , Alexander Tuzhilin, Small is beautiful: discovering the minimal set of unexpected patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.54-63, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347103]
• 29: Gregory Piateski , William Frawley, Knowledge Discovery in Databases, MIT Press, Cambridge, MA, 1991
• 30: Sunita Sarawagi , Rakesh Agrawal , Nimrod Megiddo, Discovery-Driven Exploration of OLAP Data Cubes, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.168-182, March 23-27, 1998
• 31: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 32: Geoffrey I. Webb , Shane Butler , Douglas Newlands, On detecting differences between groups, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956781]
• 33: Geoffrey I. Webb, Discovering associations with numeric variables, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.383-388, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502569]
• 34: Westfall, P. H. and Young, S. S., Resampling-Based Multiple Testing - Examples and Methods for P-Value Adjustment. New York, NY: John Wiley & Sons, Inc, 1993.
• 35: Weng-Keen Wong , Andrew Moore , Gregory Cooper , Michael Wagner, Rule-based anomaly pattern detection for detecting disease outbreaks, Eighteenth national conference on Artificial intelligence, p.217-223, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 36: Wong, W.-K., Moore, A., Cooper, G., and Wagner, M., Bayesian Network Anomaly Pattern Detection for Disease Outbreaks, in Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington, DC, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Management

Keywords:
market share rules, nonparametric methods, resampling, rule discovery, statistical quantitative rules