Interestingness of frequent itemsets using Bayesian networks as background knowledge

ABSTRACT

The paper presents a method for pruning frequent itemsets based on background knowledge represented by a Bayesian network. The interestingness of an itemset is defined as the absolute difference between its support estimated from data and from the Bayesian network. Efficient algorithms are presented for finding interestingness of a collection of frequent itemsets, and for finding all attribute sets with a given minimum interestingness. Practical usefulness of the algorithms and their efficiency have been verified experimentally.

REFERENCES

• 1: 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
• 2: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 3: Susanne G. Bottcher and Claus Dethlefsen. Deal: A package for learning bayesian networks. www.math.auc.dk/novo/Publications/ bottcher:dethlefsen:03.ps, 2003.
• 4: Rina Dechter, Bucket elimination: a unifying framework for reasoning, Artificial Intelligence, v.113 n.1-2, p.41-85, Sept. 1999 [doi>10.1016/S0004-3702(99)00059-4]
• 5: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 6: William DuMouchel , Daryl Pregibon, Empirical bayes screening for multi-item associations, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.67-76, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502526]
• 7: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 8: David Heckerman. A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Research, Redmond, WA, 1995.
• 9: Robert J. Hilderman , Howard J. Hamilton, Knowledge Discovery and Measures of Interest, Kluwer Academic Publishers, Norwell, MA, 2001
• 10: C. Huang and A. Darwiche. Inference in belief networks: A procedural guide. Intl. Journal of Approximate Reasoning, 15(3):225--263, 1996.
• 11: Szymon Jaroszewicz , Dan A. Simovici, A General Measure of Rule Interestingness, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.253-265, September 03-05, 2001
• 12: Szymon Jaroszewicz , Dan A. Simovici, Pruning Redundant Association Rules Using Maximum Entropy Principle, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.135-147, May 06-08, 2002
• 13: Finn V. Jensen, Bayesian Networks and Decision Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 14: Bing Liu, Wynne Hsu, and Shu Chen. Using general impressions to analyze discovered classification rules. In David Heckerman, Heikki Mannila, Daryl Pregibon, and Ramasamy Uthurusamy, editors, Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), page 31. AAAI Press, 1997.
• 15: Bing Liu , Wynne Hsu , Yiming Ma , Shu Chen, Mining interesting knowledge using DM-II, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.430-434, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312311]
• 16: Heikki Mannila, Local and Global Methods in Data Mining: Basic Techniques and Open Problems, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.57-68, July 08-13, 2002
• 17: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 18: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 19: Kevin Murphy. A brief introduction to graphical models and bayesian networks. http://www.ai.mit.edu/~murphyk/Bayes/bnintro.html, 1998.
• 20: 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]
• 21: Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: P. Myllymäki, T. Silander, H. Tirri, and P.Uronen. B-course: A web-based tool for bayesian and causal data analysis. International Journal on Artificial Intelligence Tools, 11(3):369--387, 2002.
• 23: D. Poole and N. L. Zhang. Exploiting contextual independence in probablisitic inference. Journal of Artificial Intelligence Research, 18:263--313, 2003.
• 24: D. Shah, L. V. S. Lakshmanan, K. Ramamritham, and S. Sudarshan. Interestingness and pruning of mined patterns. In 1999 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1999.
• 25: Abraham Silberschatz and Alexander Tuzhilin. On subjective measures of interestingness in knowledge discovery. In Knowledge Discovery and Data Mining, pages 275--281, 1995.
• 26: E. Suzuki. Autonomous discovery of reliable exception rules. In David Heckerman, Heikki Mannila, Daryl Pregibon, and Ramasamy Uthurusamy, editors, Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), page 259. AAAI Press, 1997.
• 27: Einoshin Suzuki , Yves Kodratoff, Discovery of Surprising Exception Rules Based on Intensity of Implication, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.10-18, September 23-26, 1998
• 28: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775053]
• 29: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
Bayesian network, association rule, background, frequent itemset, interestingness, knowledge