14
$\begingroup$

Does SVM handles imbalanced dataset? Is that any parameters (like C, or misclassification cost) handling the imbalanced dataset?

$\endgroup$
  • 1
    $\begingroup$ What makes a dataset "imbalanced"? $\endgroup$ – whuber Oct 30 '14 at 19:33
  • 1
    $\begingroup$ @whuber a classification data set with a largely varying class prevalence is often referred to as imbalanced. $\endgroup$ – Marc Claesen Oct 30 '14 at 19:48
  • 1
    $\begingroup$ @Marc That may be true in general but it's a vague concept. How much is "largely varying"? Why should it even matter except in certain special circumstances? I believe it is important for us to learn what the proposer of this question means by "imbalanced" rather than accepting anyone's intelligent guess concerning the intended meaning. $\endgroup$ – whuber Oct 30 '14 at 20:26
  • $\begingroup$ @whuber imbalanced datasets is a common concept in machine learning. In terms of applications because of eg spam detection etc. Perhaps because of the preponderance of algorithms targetting misclassification error instead of probability. This in turn makes the weighting of the error problematic. $\endgroup$ – seanv507 Oct 30 '14 at 20:59
  • 2
    $\begingroup$ Thank you, @seanv, for the clarification. The terminological problem really seems to be that "handles" does not refer to "can be applied to," but rather implies a setting in which (1) there is a class that is in such a minority its prediction performance might be heavily affected by the presence of the other classes, while (2) accurate prediction for the minority class is of interest. In that sense "imbalanced dataset" is a rather incomplete description of the problem, but since the term appears to have acquired some currency it seems pointless to complain. $\endgroup$ – whuber Oct 30 '14 at 21:07
17
$\begingroup$

For imbalanced data sets we typically change the misclassification penalty per class. This is called class-weighted SVM, which minimizes the following:

$$ \begin{align} \min_{\mathbf{w},b,\xi} &\quad \sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j) + C_{pos}\sum_{i\in \mathcal{P}} \xi_i + C_{neg}\sum_{i\in \mathcal{N}}\xi_i, \\ s.t. &\quad y_i\big(\sum_{j=1}^N \alpha_j y_j \kappa(\mathbf{x}_i, \mathbf{x}_j) + b\big) \geq 1-\xi_i,& i=1\ldots N \\ &\quad \xi_i \geq 0, & i=1\ldots N \end{align}$$

where $\mathcal{P}$ and $\mathcal{N}$ represent the positive/negative training instances. In standard SVM we only have a single $C$ value, whereas now we have 2. The misclassification penalty for the minority class is chosen to be larger than that of the majority class.

This approach was introduced quite early, it is mentioned for instance in a 1997 paper:

Edgar Osuna, Robert Freund, and Federico Girosi. Support Vector Machines: Training and Applications. Technical Report AIM-1602, 1997. (pdf)

Essentially this is equivalent to oversampling the minority class: for instance if $C_{pos} = 2 C_{neg}$ this is entirely equivalent to training a standard SVM with $C=C_{neg}$ after including every positive twice in the training set.

$\endgroup$
  • $\begingroup$ Cool, thanks! In addition to that, does logistic regression, navie bayes, decision tree handle such imbalance problem? $\endgroup$ – RockTheStar Oct 30 '14 at 21:24
  • $\begingroup$ logistic regression certainly does, you just weight the likelihood for positive patterns and negative patterns differently. $\endgroup$ – Dikran Marsupial Oct 31 '14 at 12:52
  • $\begingroup$ Logistic regression and SVM provide intrinsic ways. I don't know by heart for all these other methods, but oversampling the minority class works for pretty much every method (though it's not exactly mathematically elegant). $\endgroup$ – Marc Claesen Oct 31 '14 at 13:02
  • 1
    $\begingroup$ Cool, thanks @Dikran. Marc: yes, simple oversampling works in general. However, this depends on the situation. What happen is that you are adding "weights" to the minority data when you are oversampling the minority (replicating minority points again and again on the same locations). This essentially helps improving the "consideration" of minority example. However, the decision boundary of the classification will then become pretty tense (not general enough), that is, over-fitting may occurs). Therefore, we may have to consider some probablistic sampling techniques, like SMOTE. $\endgroup$ – RockTheStar Oct 31 '14 at 18:52
10
$\begingroup$

SVMs are able to deal with datasets with imbalanced class frequencies. Many implementations allow you to have a different value for the slack penalty (C) for positive and negative classes (which is asymptotically equivalent to changing the class frequencies). I would recommend setting the values of these parameters in order maximize generalization performance on a test set where the class frequencies are those you expect to see in operational use.

I was one of many people who wrote papers on this, here is mine, I'll see if I can find something more recent/better. Try Veropoulos, Campbell and Cristianini (1999).

$\endgroup$
  • $\begingroup$ Dikran why is it only asymptotically equivalent...surely it is exactly equivalent to weighting the different class errors differently? $\endgroup$ – seanv507 Oct 30 '14 at 21:16
  • $\begingroup$ It is exactly equivalent to weighting the class errors, but that is not the same thing as resampling the data (for a start the weights are continuously variable, but the data are discrete). It is one of asymptotic expectation results (that don't seem particularly useful in most circumstances). $\endgroup$ – Dikran Marsupial Oct 31 '14 at 12:51

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.