# Training a decision tree against unbalanced data

I'm new to data mining and I'm trying to train a decision tree against a data set which is highly unbalanced. However, I'm having problems with poor predictive accuracy.

The data consists of students studying courses, and the class variable is the course status which has two values - Withdrawn or Current.

• Age
• Ethnicity
• Gender
• Course
...
• Course Status

In the data set there are many more instances which are Current than Withdrawn. Withdrawn instances only accounting for 2% of the total instances.

I want to be able to build a model which can predict the probability that a person will withdraw in the future. However when testing the model against the training data, the accuracy of the model is terrible.

I've had similar issues with decision trees where the data is dominated by one or two classes.

What approach can I use to solve this problem and build a more accurate classifier?

This is an interesting and very frequent problem in classification - not just in decision trees but in virtually all classification algorithms.

As you found empirically, a training set consisting of different numbers of representatives from either class may result in a classifier that is biased towards the majority class. When applied to a test set that is similarly imbalanced, this classifier yields an optimistic accuracy estimate. In an extreme case, the classifier might assign every single test case to the majority class, thereby achieving an accuracy equal to the proportion of test cases belonging to the majority class. This is a well-known phenomenon in binary classification (and it extends naturally to multi-class settings).

This is an important issue, because an imbalanced dataset may lead to inflated performance estimates. This in turn may lead to false conclusions about the significance with which the algorithm has performed better than chance.

The machine-learning literature on this topic has essentially developed three solution strategies.

1. You can restore balance on the training set by undersampling the large class or by oversampling the small class, to prevent bias from arising in the first place.

2. Alternatively, you can modify the costs of misclassification, as noted in a previous response, again to prevent bias.

3. An additional safeguard is to replace the accuracy by the so-called balanced accuracy. It is defined as the arithmetic mean of the class-specific accuracies, $\phi := \frac{1}{2}\left(\pi^+ + \pi^-\right),$ where $\pi^+$ and $\pi^-$ represent the accuracy obtained on positive and negative examples, respectively. If the classifier performs equally well on either class, this term reduces to the conventional accuracy (i.e., the number of correct predictions divided by the total number of predictions). In contrast, if the conventional accuracy is above chance only because the classifier takes advantage of an imbalanced test set, then the balanced accuracy, as appropriate, will drop to chance (see sketch below).

I would recommend to consider at least two of the above approaches in conjunction. For example, you could oversample your minority class to prevent your classifier from acquiring a bias in favour the majority class. Following this, when evaluating the performance of your classifier, you could replace the accuracy by the balanced accuracy. The two approaches are complementary. When applied together, they should help you both prevent your original problem and avoid false conclusions following from it.

I would be happy to post some additional references to the literature if you would like to follow up on this.

• Broder - thanks for the detailed info. That has been really helpful! I initially tried using the data mining functionality in SQL Server, however, following your advice I switched to using R. I used the SMOTE algorithm to rebalance the data set and tried using both decision trees and SVM. DTs give a balanced accuracy of 81%, and even better with SVM. One question though - should I test the model against a data set which also contains rebalancd data? Or should it be tested against data more like the original? May 10, 2012 at 10:47
• This is great to hear. Regarding your question: you do not want to balance your test data. This would bias your performance evaluation, since you would be testing some examples twice (in the case of oversampling) or omit some examples from testing (in the case of undersampling). In summary, you want to balance your training set (separately within each cross-validation fold), but then test on the unmodified (potentially imbalanced) test data. May 11, 2012 at 8:25
• Thanks Broder. Doing that puts a different picture on things. The balanced accuracy drops to about 56%. The sensitivity drops to 17% on my best model (corresponding to the class I need to obtain better predictions). I suppose this makes sense because the oversampled class is that class so those examples will be counted multiple times. I'll try increasing the balancing of the training data set to see if this makes any difference. May 15, 2012 at 10:43
• Having now tested it with different proportions of balanced data, best balanced accuracy I can get is with Ada Boost with 60%. I'm struggling though to determine what's "good". My main aim is to predict students who may Withdraw from their course. With Withdraw being my positive class, I have been trying to maximise my number of true positives (i.e. increase sensitivity). Rebalancing the data does this to the detriment of the number of false negatives. 60% doesn't seem much better than random to me - but I have no baseline to what is "good" in this case. May 15, 2012 at 14:54
• @chrisb, This is a slightly(!) late comment. On a tangent, you can try Cox Proportional Hazards regression (cran.r-project.org/doc/contrib/Fox-Companion/…) to model the survival of your students. You may not need down or over-sampling. Jan 8, 2015 at 12:06

1. Select an appropriate performance measure and then fine tune the hyperparameters of your model --e.g. regularization-- to attain satisfactory results on the Cross-Validation dataset and once satisfied, test your model on the testing dataset. For these purposes, set apart 15% of your data to be used for cross validation and 15% to be used for final testing. An established measure in Machine Learning, advocated by Andrews Ng is the F1 statistics defined as $2 * Precision * \frac{Recall}{Precision + Recall}$. Try to maximize this figure on the Cross-Validation dataset and make sure that the performance is stable on the testing dataset as well.

2. Use the 'prior' parameter in the Decision Trees to inform the algorithm of the prior frequency of the classes in the dataset, i.e. if there are 1,000 positives in a 1,000,0000 dataset set prior = c(0.001, 0.999) (in R).

3. Use the 'weights' argument in the classification function you use to penalize severely the algorithm for misclassifications of the rare positive cases

4. Use the 'cost' argument in some classification algorithms -- e.g. rpart in R-- to define relative costs for misclassifications of true positives and true negatives. You naturally should set a high cost for the misclassification of the rare class.

I am not in favor of oversampling, since it introduces dependent observations in the dataset and this violates assumptions of independence made both in Statistics and Machine Learning.

Adding to @Kay 's answer 1st solution strategy : Synthetic Minority Oversampling (SMOTE) usually does better than under or over sampling from my experience as I think it kind of creates a compromise between both. It creates synthetic samples of the minority class using the data points plotted on the multivariate predictor space and it more or less takes midpoints between adjacent points on that space to create new synthetic points and hence balances both class sizes. (not sure of the midpoints, details of the algorithm here

I gave an answer in recent topic:

What we do is pick a sample with different proportions. In aforementioned example, that would be 1000 cases of "YES" and, for instance, 9000 of "NO" cases. This approach gives more stable models. However, it have to be tested on a real sample (that with 1,000,000 rows).

Not only gives that more stable approach, but models are generally better, as far as measures as lift are concerned.

You can search it as "oversampling in statistics", the first result is pretty good: http://www.statssa.gov.za/isi2009/ScientificProgramme/IPMS/1621.pdf

My follow up with the the 3 approaches @Kay mentioned above is that to deal with unbalanced data, no matter you use undersampling/oversampling or weighted cost function, it is shifting your fit in the original feature space v.s. original data. So "undersampling/oversampling" and "weighted cost" are essentially the same in term of result.

(I do not know how to pin @Kay) I think what @Kay mean by "balanced accuracy" is only trying to evaluate a model from measurement, it has nothing to do with the model itself. However, in order to count 𝜋+ and 𝜋− , you will have to decide a threshold value of the classification. I HOPE THERE IS MORE DETAIL PROVIDED ON HOW TO GET THE CONFUSION MATRIX {40, 8, 5,2 }.

In real life, most of cases I met are unbalanced data, so I choose the cutoff by myself instead of using the default 0.5 in balanced data. I find it's more realistic to use F1 score mentioned in the other author to determine the threshold and use as evaluating model.