Bayes optimal classification for decision trees

ABSTRACT

We present an algorithm for exact Bayes optimal classification from a hypothesis space of decision trees satisfying leaf constraints. Our contribution is that we reduce this classification problem to the problem of finding a rule-based classifier with appropriate weights. We show that these rules and weights can be computed in linear time from the output of a modified frequent itemset mining algorithm, which means that we can compute the classifier in practice, despite the exponential worst-case complexity. In experiments we compare the Bayes optimal predictions with those of the maximum a posteriori hypothesis.

REFERENCES

• 1: 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
• 2: Angelopoulos, N., & Cussens, J. (2005). Exploiting informative priors for Bayesian classification and regression trees. Proceedings of IJCAI (pp. 641--646).
• 3: Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Statistics/Probability Series. Belmont, California, U.S.A.
• 4: Buntine, W. (1990). A theory of learning classification rules. Doctoral dissertation, Sydney.
• 5: Buntine, W. (1992). Learning classification trees. Statistics and Computing 2 (pp. 63--73).
• 6: Chipman, H. A., George, E. I., & McCulloch, R. E. (1998). Bayesian CART model search. Journal of the American Statistical Association, 93, 935--947.
• 7: Cleary, J. G., & Trigg, L. E. (1998). Experiences with OB1, an optimal Bayes decision tree learner (Technical Report). University of Waikato.
• 8: Pedro Domingos, Bayesian Averaging of Classifiers and the Overfitting Problem, Proceedings of the Seventeenth International Conference on Machine Learning, p.223-230, June 29-July 02, 2000
• 9: Goethals, B., & Zaki, M. J. (Eds.). (2003). Proceedings of the ICDM 2003 FIMI workshop, vol. 90 of CEUR Workshop Proceedings. CEUR-WS.org.
• 10: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 11: Siegfried Nijssen , Elisa Fromont, Mining optimal decision trees from itemset lattices, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281250]
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: Oliver, J. J., & Hand, D. J. (1995). On pruning and averaging decision trees. Proceedings of ICML (pp. 430--437).
• 14: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory