Selecting the right interestingness measure for association patterns

ABSTRACT

Many techniques for association rule mining and feature selection require a suitable metric to capture the dependencies among variables in a data set. For example, metrics such as support, confidence, lift, correlation, and collective strength are often used to determine the interestingness of association patterns. However, many such measures provide conflicting information about the interestingness of a pattern, and the best metric to use for a given application domain is rarely known. In this paper, we present an overview of various measures proposed in the statistics, machine learning and data mining literature. We describe several key properties one should examine in order to select the right measure for a given application domain. A comparative study of these properties is made using twenty one of the existing measures. We show that each measure has different properties which make them useful for some application domains, but not for others. We also present two scenarios in which most of the existing measures agree with each other, namely, support-based pruning and table standardization. Finally, we present an algorithm to select a small set of tables such that an expert can select a desirable measure by looking at just this small set of tables.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, A new framework for itemset generation, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.18-24, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275490]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: A. Agresti. Categorical Data Analysis. John Wiley & Sons, 1990.
• 4: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 5: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 6: Robert J. Hilderman , Howard J. Hamilton, Evaluation of Interestingness Measures for Ranking Discovered Knowledge, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.247-259, April 16-18, 2001
• 7: Robert J. Hilderman , Howard J. Hamilton , Brock Barber, Ranking the Interestingness of Summaries from Data Mining Systems, Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference, p.100-106, May 01-05, 1999
• 8: M. Kamber and R. Shinghal. Evaluating the interestingness of characteristic rules. In Proc. of the Second Int'l Conference on Knowledge Discovery and Data Mining, pages 263--266, Portland, Oregon, 1996.
• 9: Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191314]
• 10: I. Kononenko. On biases in estimating multi-valued attributes. In Proc. of the Fourteenth Int'l Joint Conf. on Artificial Intelligence (IJCAI'95), pages 1034--1040, Montreal, Canada, 1995.
• 11: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 12: F. Mosteller. Association and estimation in contingency tables. Journal of the American Statistical Association, 63:1--28, 1968.
• 13: Gregory Piateski , William Frawley, Knowledge Discovery in Databases, MIT Press, Cambridge, MA, 1991
• 14: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 15: Craig Silverstein , Sergey Brin , Rajeev Motwani, Beyond Market Baskets: Generalizing Association Rules to Dependence Rules, Data Mining and Knowledge Discovery, v.2 n.1, p.39-68, January 1998 [doi>10.1023/A:1009713703947]
• 16: P. Tan, V. Kumar, and J. Srivastava. Selecting the right interestingness measure for association patterns. Technical Report 2002--112, Army High Performance Computing Research Center, 2002.

INDEX TERMS

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

Keywords:
associations, contingency tables, interestingness measure