Does SVM handles imbalanced dataset? Is that any parameters (like C, or misclassification cost) handling the imbalanced dataset?
$\begingroup$
$\endgroup$
6
asked Oct 30, 2014 at 19:29
-
1$\begingroup$ What makes a dataset "imbalanced"? $\endgroup$– whuber ♦Commented Oct 30, 2014 at 19:33
-
1$\begingroup$ @whuber a classification data set with a largely varying class prevalence is often referred to as imbalanced. $\endgroup$– Marc ClaesenCommented Oct 30, 2014 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 ♦Commented Oct 30, 2014 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$– seanv507Commented Oct 30, 2014 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 ♦Commented Oct 30, 2014 at 21:07
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
4
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.
gung - Reinstate Monica
148k89 gold badges406 silver badges717 bronze badges
answered Oct 30, 2014 at 19:44
-
$\begingroup$ Cool, thanks! In addition to that, does logistic regression, navie bayes, decision tree handle such imbalance problem? $\endgroup$ Commented Oct 30, 2014 at 21:24
-
$\begingroup$ logistic regression certainly does, you just weight the likelihood for positive patterns and negative patterns differently. $\endgroup$ Commented Oct 31, 2014 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$ Commented Oct 31, 2014 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$ Commented Oct 31, 2014 at 18:52
$\begingroup$
$\endgroup$
2
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).
answered Oct 30, 2014 at 19:44
-
$\begingroup$ Dikran why is it only asymptotically equivalent...surely it is exactly equivalent to weighting the different class errors differently? $\endgroup$– seanv507Commented Oct 30, 2014 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$ Commented Oct 31, 2014 at 12:51