Bagging with oversampling for rare event predictive models

Question

Does anyone know if the following has been described and (either way) if it sounds like a plausible method for learning a predictive model with a very unbalanced target variable?

Often in CRM applications of data mining, we will seek a model where the positive event (success) is very rare relative to the majority (negative class). For example, I may have 500,000 instances where only 0.1% are of the positive class of interest (e.g. the customer bought). So, in order to create a predictive model, one method is to sample the data whereby you keep all positive class instances and only a sample of the negative class instances so that the ratio of positive to negative class is closer to 1 (maybe 25% to 75% positive to negative). Over sampling, undersampling, SMOTE etc are all methods in the literature.

What I am curious about is combining the basic sampling strategy above but with bagging of the negative class.Something simply like:

• Keep all positive class instances (e.g. 1,000)
• Sample the negative classe instances in order to create a balanced sample (e.g. 1,000).
• Fit the model
• Repeat

Anyone hear of doing this before? The trouble it seems without bagging is that sampling only 1,000 instances of the negative class when there are 500,000 is that the predictor space will be sparse and you may well not have a representation of possible predictor values/patterns. Bagging seems to help this.

I looked at rpart and nothing "breaks" when one of the samples does not have all the values for a predictor (does not break when then predicting instances with those predictor values:

library(rpart)
tree<-rpart(skips ~ PadType,data=solder[solder$PadType !='D6',], method="anova")
predict(tree,newdata=subset(solder,PadType =='D6'))

Any thoughts?

UPDATE: I took a real world data set (marketing direct mail response data) and randomly partitioned it into training and validation. There are 618 predictors and 1 binary target (very rare).

Training:
Total Cases: 167,923
Cases with Y=1: 521

Validation:
Total Cases: 141,755
Cases with Y=1: 410

I took all positive examples (521) from the training set and a random sample of negative examples of the same size for a balanced sample. I fit an rpart tree:

models[[length(models)+1]]<-rpart(Y~.,data=trainSample,method="class")

I repeated this process 100 times. Then predicted the probability of Y=1 on the cases of the validation sample for each of these 100 models. I simply averaged the 100 probabilities for a final estimate. I deciled the probabilities on the validation set and in each decile calculated the percentage of cases where Y=1 (the traditional method for estimating the ranking ability of the model).

Result$decile<-as.numeric(cut(Result[,"Score"],breaks=10,labels=1:10)) 

Here is the performance:

To see how this compared to no bagging, I predicted the validation sample with the first sample only (all positive cases and a random sample of the same size). Clearly, the data sampled was too sparse or overfit to be effective on the hold out validation sample.

Suggesting the efficacy of the bagging routine when there is a rare event and large n and p.

Answer 1

Except for the inclusion of the same positive class examples in each bag this is S^3Bagging as described in S^3Bagging: Fast Classifier Induction Method with Subsampling and Bagging. (I haven't reviewed this paper in depth, just skimmed it.)

I see nothing theoretically wrong with your approach, although I've much more frequently seen subsampling combined with boosting than bagging.

This may not exactly address your question, but an excellent paper on different ways of dealing with imbalanced data is Learning From Imbalanced Data. It seams like cost sensitive learning may be more appropriate in your case. Since you're using Decision Forests, Section 3.2.3 Cost-Sensitive Decision Trees would probably be helpful. It states,

In regards to decision trees, cost-sensitive fitting can take three forms: first, cost-sensitive adjustments can be applied to the decision threshold; second, cost-sensitive considerations can be given to the split criteria at each node; and lastly, cost-sensitive pruning schemes can be applied to the tree

Cost sensitive adjustments to the decision threshold basically means picking your decision threshold based on the ROC or Precision-Recall Curve performance. The PRC performance in particular is robust to imbalanced data.

Cost sensitive split criteria comes down to changing your impurity function to deal with imbalanced data. The above mentioned paper states,

In [63], three specific impurity functions, Gini, Entropy, and DKM, were shown to have improved cost insensitivity compared with the accuracy/error rate baseline. Moreover, these empirical experiments also showed that using the DKM function generally produced smaller unpruned decision trees that at worse provided accuracies comparable to Gini and Entropy. A detailed theoretical basis explaining the conclusions of these empirical results was later established in [49], which generalizes the effects of decision tree growth for any choice of spit criteria.

As to pruning,

However, in the presence of imbalanced data, pruning procedures tend to remove leaves describing the minority concept. It has been shown that though pruning trees induced from imbalanced data can hinder performance, using unpruned trees in such cases does not improve performance [23]. As a result, attention has been given to improving the class probability estimate at each node to develop more representative decision tree structures such that pruning can be applied with positive effects. Some representative works include the Laplace smoothing method of the probability estimate and the Laplace pruning technique [49].

[23] N. Japkowicz and S. Stephen, “The Class Imbalance Problem: A Systematic Study,” Intelligent Data Analysis, vol. 6, no. 5, pp. 429- 449, 2002.

[49] C. Elkan, “The Foundations of Cost-Sensitive Learning,” Proc. Int’l Joint Conf. Artificial Intelligence, pp. 973-978, 2001.

[63] C. Drummond and R.C. Holte, “Exploiting the Cost (In)Sensitivity of Decision Tree Splitting Criteria,” Proc. Int’l Conf. Machine Learning, pp. 239-246, 2000.

Answer 2

This is very interesting. I recently have a project that has similar situation where the validation on rare events performs well while the validation of non-events in the lowest predicted range (such as 0.0 - 0.1) performed unstably month over month. The reasons behind, as you mentioned, due to the large population of non-events, it's better to include more samples into the training sets so that there are enough samples to cover various combinations of variables.