Fast discovery of unexpected patterns in data, relative to a Bayesian network

ABSTRACT

We consider a model in which background knowledge on a given domain of interest is available in terms of a Bayesian network, in addition to a large database. The mining problem is to discover unexpected patterns: our goal is to find the strongest discrepancies between network and database. This problem is intrinsically difficult because it requires inference in a Bayesian network and processing the entire, potentially very large, database. A sampling-based method that we introduce is efficient and yet provably finds the approximately most interesting unexpected patterns. We give a rigorous proof of the method's correctness. Experiments shed light on its efficiency and practicality for large-scale Bayesian networks and databases.

REFERENCES

• 1: Rakesh Agrawal , Hiekki 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
• 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: H. Dodge and H. Romig. A method of sampling inspection. The Bell System Technical Journal, 8:613--631, 1929.
• 4: Carlos Domingo , Ricard Gavaldà , Osamu Watanabe, Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms, Data Mining and Knowledge Discovery, v.6 n.2, p.131-152, April 2002 [doi>10.1023/A:1014091514039]
• 5: U. Fayyad, G. Piatetski-Shapiro, and P. Smyth. Knowledge discovery and data mining: Towards a unifying framework. In KDD-96, 1996.
• 6: W. Gilks, S. Richardson, and D. Spiegelhalter, editors. Markov Chain Monte Carlo in Practice. Chapman & Hall, 1995.
• 7: Russell Greiner, PALO: a probabilistic hill-climbing algorithm, Artificial Intelligence, v.84 n.1-2, p.177-208, July 1996 [doi>10.1016/0004-3702(95)00040-2]
• 8: Geoff Hulten , Pedro Domingos, Mining complex models from arbitrarily large databases in constant time, 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.775124]
• 9: 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
• 10: Szymon Jaroszewicz , Dan A. Simovici, Interestingness of frequent itemsets using Bayesian networks as background knowledge, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014074]
• 11: Finn V. Jensen, Bayesian Networks and Decision Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 12: W. Klösgen. Assistant for knowledge discovery in data. In P. Hoschka, editor, Assisting Computer: A New Generation of Support Systems, 1995.
• 13: R. Kruse. Knowledge-based operations on graphical models. In Proceedings of the Dagstuhl Seminar on Probabilistic, Logical, and Relational Learning, 2005. In print.
• 14: O. Maron and A. Moore. Hoeffding races: Accelerating model selection search for classification and function approximating. In Advances in Neural Information Processing Systems, pages 59--66, 1994.
• 15: Balaji Padmanabhan , Alexander Tuzhilin, Unexpectedness as a measure of interestingness in knowledge discovery, Decision Support Systems, v.27 n.3, p.303-318, Dec.1999 [doi>10.1016/S0167-9236(99)00053-6]
• 16: 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]
• 17: 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.
• 18: Tobias Scheffer, Finding Association Rules That Trade Support Optimally against Confidence, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.424-435, September 03-05, 2001
• 19: Tobias Scheffer , Stefan Wrobel, Finding the most interesting patterns in a database quickly by using sequential sampling, The Journal of Machine Learning Research, 3, 3/1/2003
• 20: A. Silberschatz and A. Tuzhilin. On subjective measures of interestingness in knowledge discovery. In Proceedings of the SIGKDD Conference on Knowledge Discovery and Data Mining, 1995.
• 21: 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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Bayesian networks, association rules, sampling