Suppose you get to observe "matches" between buyers and sellers in a market. You also get to observe characteristics of both buyers and sellers which you would like to use to predict future matches & make recommendations to both sides of the market.

For simplicity, assume there are N buyers and N sellers and that each finds a match. There are N matches and (N-1)(N-1) non-matches. The all-inclusive training dataset has N + (N-1)*(N-1) observations, which can be prohibitively large. It would seem that randomly sampling from the (N-1)(N-1) non-matches and training an algorithm on that reduced data could be more efficient. My questions are:

(1) Is sampling from the non-matches to build a training dataset a reasonable way to deal with this problem?

(2) If (1) is true, is there is a rigorous way to decide how big of a chunk of (N-1)(N-1) to include?


migrated from stackoverflow.com Apr 10 '11 at 0:28

This question came from our site for professional and enthusiast programmers.


If I understand correctly, you have a two class classification problem, where the positive class (matches) is rare. Many classifiers struggle with such a class imbalance, and it is common practice to sub-sample the majority class in order to obtain better performance, so the answer to the first question is "yes". However, if you sub-sample too much, you will end up with a classifier that over-predicts the minority positive class, so the best thing to do is to choose the sub-sampling ration to maximise performance, perhaps by minimising the cross-validation error where the test data has not been sub-sampled so you get a good indication of operational performance.

If you have a probabilistic classifier, that gives an estimate of the probabiility of class memebership, you can go one better and post-process the output to compensate for the difference between class frequencies in the training set and in operation. I suspect that for some classifiers, the optimal approach is to optimise both the sub-sampling ratio and the correction to the output by optimising the cross-validation error.

Rather than sub-sampling, for some classifiers (e.g. SVMs) you can give different weights to positive and negative patterns. I prefer this to sub-sampling as it means there is no variability in the results due to the particular sub-sample used. Where this is not possible, use bootstrapping to make a bagged classifier, where a different sub-sample of the majority class is used in each iteration.

The one other thing I would say is that commonly where there is a large class imbalance, false negative errors and false positive error are not equally bad, and it is a good idea to build this into the classifier design (which can be accomplished by sub-sampling or weighting patterns belonging to each class).

  • 3
    $\begingroup$ (+1), however I think one has to dinguish between the goal of ranking (measure:AUC) and separating the two classes (measure: Accuracy). In the former case, given a probabilistic classfier like Naive Bayes, imbalance playes a lesser role, I suppose. Or should one be worried in this case, too ? Another question: What do you mean by "post-process the output" ? Converting scores to actual probabilities ? $\endgroup$ – steffen Apr 11 '11 at 8:01
  • $\begingroup$ @Steffen My intuition is that the class imbalance problem is less of an issue for ranking, but that it won't go away completely (I am working on a paper on this problem, so that is something worth resolving). By post-processing, I meant multiplyng the outputs by the ratio of the operational and training set class frequencies and then re-normalising so the probabilities of all possible outcomes sum to one. However in practice the actual optimal scaling factor is likely to be somewhat different - hence optimise with XVAL (but still re-normalise). $\endgroup$ – Dikran Marsupial Apr 11 '11 at 8:26

Concerning (1). You need to keep positive and negative observations if you want meaningful results.
(2) There is no wiser method of subsampling than uniform distribution if you don't have any a priori on your data.

  • $\begingroup$ Thanks Ugo - agreed, there definitely needs be both matches and non-matches in the training data. The question is about how many of the (N-1)(N-1) non-matches are needed. For part (2), I would definitely sample w/ equal weight over all observations. $\endgroup$ – John Horton Apr 10 '11 at 0:52
  • $\begingroup$ Well if you don't have apriori on your data there no reasonable way to sample the data. So you have to do uniform sampling, and in this case, the more you take, the better it is. You could however estimate the error introduced by the sampling, but we are missing information here to help you on this point. $\endgroup$ – Ugo Apr 10 '11 at 0:58
  • $\begingroup$ It seems to me that the error will depend on the type of classifier used. Anyway you can always try to predict at different sample rate and fix a threshold where you think the error introduced is satisfactory. $\endgroup$ – Ugo Apr 10 '11 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.