Binary classifier - dividing dataset into training and evaluation sets

I have a Hidden Markov Model for binary classification and two datasets:

• positive instances
• negative instances (way more data than the positive ones)

In order to evaluate the performance of the model I did the following:

1. Do leave one out cross validation over the positive instances. Basically remove an instance from the positive set, train over the rest, then evaluate the instance I removed and saved the result; Repeat for each instance.
2. Train over all the positive instances and then evaluate each negative instance. Save results
3. Plot ROC curve with the data from 1 and 2.

This approach is pretty time intensive as I have to train my model N+1 times where N equals the number of positive instances.

Someone suggested that I combine both data sets and then divide them:

• 2/3 training set
• 1/3 evaluation set

and maintain in both sets the same percentage of positive/negative instances.

Maybe I understood something wrong but I am a bit confused as to how this helps exactly when I have negative instances in the training data!?

Wouldn't that negatively bias my classifier when evaluating over the remaining 1/3 instances? Moreover, I would also get less data points for the ROC curve?

Can anybody help clarify the approach or suggest a better one?

• I don't think with the imbalance you have in positive versus negative instances that you should throw out information on negative cases bycutting them down to be the same as much lower total of positive instances. – Michael R. Chernick Jul 7 '12 at 3:46
• I don't understand how you are training the model to correctly identify negative instances. If you are doing some training in step 2 when you say "evaluate," it still sounds like you are training $N$ or $N+1$ times on each positive for each negative. This can be a bad thing to do. The trivial classifier which decides everything is positive may perform quite well compared with classifiers which are right on over $90\%$ of both positive and negative points. It can be ok to oversample the positive instances, but the weight on positive points should depend on #positive/#negative, not #positive. – Douglas Zare Jul 7 '12 at 9:35
• Regarding the training: for the positive instances I trained on N-1 instances and evaluated the Nth (repeat N times for each positive instance). For the negatives instances: train once on all the positive instances and evaluate the negative instances one by one(here I only train the model once). When I say evaluate I use the Forward Algorithm to get the P(instance | Model), that is, the probability of an instance/sequence given the model. – Morat Jul 7 '12 at 11:11

1 Answer

Classifiers usually try to find the best fit for all the data. In the case of imbalance where you have much more negative than positive samples the classifier will pay more attention to the negative class in order to obtain a small overall error. Imbalance can be intrinsic or extrinsic, i.e. intrinsic imbalances are a direct result caused by the nature of the data space (e.g. rare diseases) and extrinsic imbalances are a result of certain limitations (time, space, money, etc.) where the data space is in reality not imbalanced. In addition, it might happen that only either the training or the testing data set are imbalanced. Personally, I would start with stratified cross-validation where it is ensured that the ratio between positive and negative class is the same in each fold and the same as in the overall data set.

To address the imbalance itself there are several methods that do this. A simple way would be to increase the weight of samples from the positive class compared to the negative class, this makes the classifier kind of cost-sensitive. An introduction to all the available methods can be found in

• Thank you for your reply. Unfortunately I can't seem to find the articles freely available anywhere so that I can take a look at the methods. Regarding your suggestion for the cross-validation: my goal is to speed things up a bit right now; would selecting in a k-fold cross validation a very small k still be OK? Take into account the fact that I have 74 positive instances and 496 negative instances. – Morat Jul 7 '12 at 12:01
• You mentioned that you are currently have to train your model 75 times, so yes, even a 10-fold cross-validation should considerably lower the time for testing. – sebp Jul 7 '12 at 15:17
• Thank you for your time. In my previous comment I was more curious about how switching from leave one out towards let's say 5-fold or 10-fold would impact quality. – Morat Jul 7 '12 at 16:42