An iterative method for multi-class cost-sensitive learning

ABSTRACT

Cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. In this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. This algorithm is derived using hree key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. We establish some theoretical guarantees concerning the performance of this method. In particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. We also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
• 2: S. D. Bay. UCI KDD archive. Department of Information and Computer Sciences, University of California, Irvine, 2000. http://kdd.ics.uci.edu/.
• 3: C. L. Blake and C. J. Merz. UCI repository of machine learning databases. Department of Information and Computer Sciences, University of California, Irvine, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 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: P. Chan and S. Stolfo. Toward scalable learning with non-uniform class and cost distributions. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pages 164--168, 1998.
• 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: C. Drummond and R. C. Holte. C4.5, class imbalance, and cost-sensitivity: Why under-sampling beats over-sampling. In Workshop Notes, Workshop on Cost-Sensitive Learning, International Conference on Machine Learning, June 2000.
• 10: Charles Elkan, Magical thinking in data mining: lessons from CoIL challenge 2000, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.426-431, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502576]
• 11: Wei Fan , Salvatore J. Stolfo , Junxin Zhang , Philip K. Chan, AdaCost: Misclassification Cost-Sensitive Boosting, Proceedings of the Sixteenth International Conference on Machine Learning, p.97-105, June 27-30, 1999
• 12: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 13: G. Fumera and F. Roli. Cost-sensitive learning in support vector machines. In VIII Convegno Associazione Italiana per L'Intelligenza Artificiale, 2002.
• 14: P. Geibel and F. Wysotzki. Perceptron based learning with example dependent and noisy costs. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.
• 15: Ulrich Knoll , Gholamreza Nakhaeizadeh , Birgit Tausend, Cost-sensitive pruning of decision trees, Proceedings of the European conference on machine learning on Machine Learning, p.383-386, May 1994, Catania, Italy
• 16: Dragos Dorin Margineantu , Thomas G. Dietterich, Methods for cost-sensitive learning, 2002
• 17: L. Mason, J. Baxter, P. Barlett, and M. Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing systems 12, pages 512--158, 2000.
• 18: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 19: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]
• 20: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
boosting, cost-sensitive learning, multi-class classification