# Learning When Training Data Are Costly: The Effect Of Class Distribution On Tree Induction

Gary M. Weiss GMWEISS@ATT.COM
AT&T Labs, 30 Knightsbridge Road Piscataway, NJ 08854 USA
Foster Provost FPROVOST@STERN.NYU.EDU
New York University, Stern School of Business 44 W. 4th St., New York, NY 10012 USA

## Abstract

For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. 

We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a "budget-sensitive" progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance. 

## 1. Introduction

In many real-world situations the number of training examples must be limited because obtaining examples in a form suitable for learning may be costly and/or learning from these examples may be costly. These costs include the cost of obtaining the raw data, cleaning the data, storing the data, and transforming the data into a representation suitable for learning, as well as the cost of computer hardware, the cost associated with the time it takes to learn from the data, and the "opportunity cost" associated with suboptimal learning from extremely large data sets due to limited computational resources (Turney, 2000). When these costs make it necessary to limit the amount of training data, an important question is: in what proportion should the classes be represented in the training data? In answering this question, this article makes two main contributions. It addresses (for classification-tree induction) the practical problem of how to select the class distribution of the training data when the amount of training data must be limited, and, by providing a detailed empirical study of the effect of class distribution on classifier performance, it provides a better understanding of the role of class distribution in learning. 

©2003 AI Access Foundation and Morgan Kaufmann Publishers. All Rights Reserved. 