Learning and making decisions when costs and probabilities are both unknown

ABSTRACT

In many data mining domains, misclassification costs are different for different examples, in the same way that class membership probabilities are example-dependent. In these domains, both costs and probabilities are unknown for test examples, so both cost estimators and probability estimators must be learned. After discussing how to make optimal decisions given cost and probability estimates, we present decision tree and naive Bayesian learning methods for obtaining well-calibrated probability estimates. We then explain how to obtain unbiased estimators for example-dependent costs, taking into account the difficulty that in general, probabilities and costs are not independent random variables, and the training examples for which costs are known are not representative of all examples. The latter problem is called sample selection bias in econometrics. Our solution to it is based on Nobel prize-winning work due to the economist James Heckman. We show that the methods we propose perform better than MetaCost and all other known methods, in a comprehensive experimental comparison that uses the well-known, large, and challenging dataset from the KDD'98 data mining contest.

REFERENCES

• 1: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 2: S. D. Bay. UCI KDD archive. Department of Information and Computer Sciences, University of California, Irvine, 2000. http://kdd, its.uci.edu/.
• 3: P. N. Bennett. Assessing the calibration of naive Bayes' posterior estimates. Technical Report CMU-CS-00-155, School of Computer Science, Carnegie Mellon University, 2000.
• 4: Jeffrey P. Bradford , Clayton Kunz , Ron Kohavi , Clifford Brunk , Carla E. Brodley, Pruning Decision Trees with Misclassification Costs, Proceedings of the 10th European Conference on Machine Learning, p.131-136, April 21-23, 1998
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: L. Breiman, J. H. Friedman, R. A. Olsen, and C. J. Stone. Classification and Regression Trees. Wadsworth International Group, 1984.
• 7: James Cussens, Bayes and Pseudo-Bayes Estimates of Conditional Probabilities and Their Reliability, Proceedings of the European Conference on Machine Learning, p.136-152, April 05-07, 1993
• 8: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 9: P. Domingos and M. Pazzani. Beyond independence: Conditions for the optimality of the simple Bayesian classifier. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 105-112. Morgan Kanfmann Publishers, Inc., 1996.
• 10: C. Elkan. Cost-sensitive learning and decision-making when costs are unknown. In Workshop Notes, Workshop on Cost-Sensitive Learning at the Seventeenth International Conference on Machine Learning, 2000.
• 11: C. Elkan. The foundations of cost-sensitive learning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, Aug. 2001.
• 12: Floriana Esposito , Donato Malerba , Giovanni Semeraro, A Comparative Analysis of Methods for Pruning Decision Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.5, p.476-491, May 1997 [doi>10.1109/34.589207]
• 13: J. Heckman. Sample selection bias as a specification error. Econometrica, 47:153-161, 1979.
• 14: E. C. Malthouse. Assessing the performance of direct marketing scoring models. Journal of Interactive Marketing, 15(1):49-62, 2001.
• 15: Dragos D. Margineantu , Thomas G. Dietterich, Bootstrap Methods for the Cost-Sensitive Evaluation of Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.583-590, June 29-July 02, 2000
• 16: F. Provost and P. Domingos. Well-trained PETs: Improving probability estimation trees. CDER Working Paper 2000-04-1S, Stern School of Business, New York University, NY, NY 10012, 2000.
• 17: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 18: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 19: P. Smyth, A. Gray, and U. Fayyad. Retrofitting decision tree classifiers using kernel density estimation. In Proceedings of the Twelfth International Conference on Machine Learning, pages 506-514. Morgan Kaufmann Publishers, Inc., 1995.
• 20: J. R. Sobehart, R. M. Stein, V. Mikityanskaya, and L. Li. Moody's public firm risk model: A hybrid approach to modeling short term default risk. Technical report, Moody's Investors Service, Global Credit Research, 2000. Available at http://www, moodysqra, com} research/crm/53853, asp.
• 21: K. Turner and J. Ghosh. Theoretical foundations linear and order statistics combiners for neural pattern classifiers. Technical Report TR-95-02-98, Computer and Vision Research Center, The University of Texas at Austin, 1995.
• 22: P. Turney. Cost-sensitive learning bibliography. Institute for Information Technology, National Research Council, Ottawa, Canada, 2000. http ://extractor.iit.nrc.ca/ bibliographies/cost -sensit ive. html.
• 23: Bianca Zadrozny , Charles Elkan, Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers, Proceedings of the Eighteenth International Conference on Machine Learning, p.609-616, June 28-July 01, 2001

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

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

General Terms:
Algorithms, Economics, Performance