Theory of dependence values

ABSTRACT

A new model to evaluate dependencies in data mining problems is presented and discussed. The well-known concept of the association rule is replaced by the new definition of dependence value, which is a single real number uniquely associated with a given itemset. Knowledge of dependence values is sufficient to describe all the dependencies characterizing a given data mining problem. The dependence value of an itemset is the difference between the occurrence probability of the itemset and a corresponding “maximum independence estimate.” This can be determined as a function of joint probabilities of the subsets of the itemset being considered by maximizing a suitable entropy function. So it is possible to separate in an itemset of cardinaltiy k the dependence inherited from its subsets of cardinality (k − 1) and the specific inherent dependence of that itemset. The absolute value of the difference between the probability p(i) of the event i that indicates the prescence of the itemset {a,b,... } and its maximum independence estimate is constant for any combination of values of Q &angl0; a,b,... &angr0; Q. In1p addition, the Boolean function specifying the combination of values for which the dependence is positive is a parity function. So the determination of such combinations is immediate. The model appears to be simple and powerful.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Online Generation of Association Rules, Proceedings of the Fourteenth International Conference on Data Engineering, p.402-411, February 23-27, 1998
• 2: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 3: 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
• 4: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 5: 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
• 6: 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
• 7: Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995
• 8: Jiawei Han , Yandong Cai , Nick Cercone, Knowledge Discovery in Databases: An Attribute-Oriented Approach, Proceedings of the 18th International Conference on Very Large Data Bases, p.547-559, August 23-27, 1992
• 9: Maurice A. W. Houtsma , Arun N. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.25-33, March 06-10, 1995
• 10: IMIELINSKI, T. 1997. From file mining to database mining. In Proceedings of the ACM SIGMOD International Workshop on Data Mining and Knowledge Discovery (SIGMOD-96, Aug.), R. Ng, Ed. ACM Press, New York, NY, 35-39.
• 11: IV, J. F. E. AND PREGIBON, D. 1995. A statistical perspective on kdd. Tech. Rep. KDD-95-93.
• 12: Gomer Thomas , K. Kawagoe , R. Krishnamurthy , T. Imielinski , D. Reiner , A. Wolski, Practitioner problems in need of database research, ACM SIGMOD Record, v.20 n.3, p.73-84, Sept. 1991 [doi>10.1145/126482.126491]
• 13: Dao-I Lin , Zvi M. Kedem, Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.105-119, March 23-27, 1998
• 14: Rosa Meo, A New Approach for the Discovery of Frequent Itemsets, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.193-202, September 01, 1999
• 15: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 16: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 17: 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]
• 18: 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
• 19: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 20: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Experimentation, Theory

Keywords:
association rules, dependence rules, entropy, variables independence