Observe that different training distributions perform better in different areas of ROC space. 

Specifically note that the classifier trained with 90% minority-class examples performs substantially better than the classifier trained with the natural distribution for high true-positive rates and that the classifier training with 2% minority-class examples performs fairly well for low truepositive rates. Why? With only a small sample of minority-class examples (2%) a classifier can identify only a few minority-labeled "rules" with high confidence. However, with a much larger sample of minority-class examples (90%) it can identify many more such minority-labeled rules. 

However, for this data set a balanced distribution has the largest AUC and performs best overall. 

Note that the curve generated using the balanced class distribution almost always outperforms the curve associated with the natural distribution (for low false-positive rates the natural distribution performs slightly better). 

## 7. Forming A Good Class Distribution With Sensitivity To Procurement Costs

The results from the previous section demonstrate that some marginal class distributions yield classifiers that perform substantially better than the classifiers produced by other training distributions. Unfortunately, in order to determine the best class distribution for training, forming all thirteen training sets of size n, each with a different class distribution, requires nearly 2n examples. When it is costly to obtain training examples in a form suitable for learning, then this approach is self-defeating. Ideally, given a budget that allows for n training examples, one would select a total of n training examples all of which would be used in the final training set—and the associated class distribution would yield classifiers that perform better than those generated from any other class distribution (given n training examples). In this section we describe and evaluate a heuristic, budget-sensitive, progressive sampling algorithm that approximates this ideal. 

In order to evaluate this progressive sampling algorithm, it is necessary to measure how class distribution affects classifier performance for a variety of different training-set sizes. These measurements are summarized in Section 7.1 (the detailed results are included in Appendix B). 

The algorithm for selecting training data is then described in Section 7.2 and its performance evaluated in Section 7.3, using the measurements included in Appendix B. 

## 7.1 The Effect Of Class Distribution And Training-Set Size On Classifier Performance

Experiments were run to establish the relationship between class distribution, training-set size and classifier performance. In order to ensure that the training sets contain a sufficient number of training examples to provide meaningful results when the training-set size is dramatically reduced, only the data sets that yield relatively large training sets are used (this is determined based on the size of the data set and the fraction of minority-class examples in the data set). Based on this criterion, the following seven data sets were selected for analysis: phone, adult, covertype, blackjack, kr-vs-kp, letter-a, and weather. The detailed results associated with these experiments are contained in Appendix B. 

The results for one of these data sets, the adult data set, are shown graphically in Figure 4 and Figure 5, which show classifier performance using error rate and AUC, respectively. Each of the nine performance curves in these figures is associated with a specific training-set size, which contains between 1/128 and all of the training data available for learning (using the methodology described in Section 4.1). Because the performance curves always improve with increasing dataset size, only the curves corresponding to the smallest and largest training-set sizes are explicitly labeled. 