What are the implications for training a Tree Ensemble with highly biased datasets?

Question

I have a highly biased binary dataset - I have 1000x more examples of the negative class than the positive class. I would like to train a Tree Ensemble (like Extra Random Trees or a Random Forest) on this data but it's difficult to create training datasets that contain enough examples of the positive class.

What would be the implications of doing a stratified sampling approach to normalize the number of positive and negative examples? In other words, is it a bad idea to, for instance, artificially inflate (by resampling) the number of positive class examples in the training set?

Answer 1

Yes, it's problematic. If you oversample the minority, you risk overfitting. If you undersample the majority, you risk missing aspects of the majority class. Stratified sampling, btw, is the equivalent to assigning non-uniform misclassification costs.

Alternatives:

(1) Independently sampling several subsets from the majority class and making multiple classifiers by combining each subset with all the minority class data, as suggested in the answer from @Debasis and described in this EasyEnsemble paper,

(2) SMOTE (Synthetic Minority Oversampling Technique) or SMOTEBoost, (combining SMOTE with boosting) to create synthetic instances of the minority class by making nearest neighbors in the feature space. SMOTE is implemented in R in the DMwR package.

Answer 2

I would recommend training on more balanced subsets of your data. Training random forest on sets of randomly selected positive example with a similar number of negative samples. In particular if the discriminative features exhibit a lot of variance this will be fairly effective and avoid over-fitting. However in stratification it is important to find balance as over-fitting can become a problem regardless. I would suggest seeing how the model does with the whole data set then progressively increasing the ratio of positive to negative samples approaching an even ratio, and selecting for the one that maximizes your performance metric on some representative hold out data.

This paper seems fairly relevant http://statistics.berkeley.edu/sites/default/files/tech-reports/666.pdf it talks about a weighted Random Forest which more heavily penalizes misclassification of the minority class.

Answer 3

A fast, easy an often effective way to approach this imbalance would be to randomly subsample the bigger class (which in your case is the negative class), run the classification N number of times with members from the two classes (one full and the other subsampled) and report the average metric values, the average being computed over N (say 1000) iterations.

A more methodical approach would be to execute the Mapping Convergence (MC) algorithm, which involves identifying a subset of strong negative samples with the help of a one-class classifier, such as OSVM or SVDD, and then iteratively execute binary classification on the set of strong negative and positive samples. More details of the MC algorithm can be found in this paper.

Answer 4

As mentioned above, the best way is to repeatedly sample the majority class N times(sampling without replacement) and for each time, the size of negative class should be equal to the size of positive class. Now, N different classifiers can be trained and the average can be used to evaluate it.

Another way is to use the technique of bootstrapping. This might introduce overfitting, but worth trying and then if neeeded can regularize the model to avoid overfitting.