Learning decision trees for loss minimization in multi-class problems

Abstract

Many machine learning applications require classifiers that minimize an asymmetric loss function rather than the raw misclassification rate. We study methods for modifying C4.5 to incorporate arbitrary loss matrices. One way to incorporate loss information into C4.5 is to manipulate the weights assigned to the examples from different classes. For 2-class problems, this works for any loss matrix, but for k ? 2 classes, it is not sufficient. Nonetheless, we ask what is the set of class weights that best approximates an arbitrary k \\Theta k loss matrix, and we test and compare several methods: a wrapper method and some simple heuristics. The best method is a wrapper method that directly optimizes the loss using a hold-out data set. We define complexity measure for loss matrices and show that this measure can predict when more efficient methods will suffice and when the wrapper method must be applied. 1 Introduction For most of the history of machine learning research, a central goal has ...