14
$\begingroup$

I have a dataset with a few million rows and ~100 columns. I would like to detect about 1% of the examples in the dataset, which belong to a common class. I have a minimum precision constraint, but due to very asymmetric cost I am not too keen on any particular recall (as long as I am not left with 10 positive matches!)

What are some approaches that you would recommend in this setting? (links to papers welcome, links to implementations appreciated)

$\endgroup$
14
$\begingroup$

I've found He and Garcia (2009) to be a helpful review of learning in imbalanced class problems. Here are a few definitely-not-comprehensive things to consider:

Data-based approaches:

One can undersample the majority class or oversample the minority class. (Breiman pointed out that this is formally the equivalent to assigning non-uniform misclassification costs.) This can cause problems: Undersampling can cause the learner to miss aspects of the majority class; oversampling increases risk of overfitting.

There are "informed undersampling" methods that reduce these issues. One of them is EasyEnsemble, which independently samples several subsets from the majority class and makes multiple classifiers by combining each subset with all the minority class data.

SMOTE (Synthetic Minority Oversampling Technique) or SMOTEBoost, (combining SMOTE with boosting) create synthetic instances of the minority class by making nearest neighbors in the feature space. SMOTE is implemented in R in the DMwR package (which accompanies Luis Torgo's book “Data Mining with R, learning with case studies” CRC Press 2010).

Model fitting approaches

Apply class-specific weights in your loss function (larger weights for minority cases).

For tree-based approaches, you can use Hellinger distance as a node impurity function, as advocated in Cieslak et al. "Hellinger distance decision trees are robust and skew-insensitive" (Weka code here.)

Use a one class classifier, learning either (depending on the model) a probability density or boundary for one class and treating the other class as outliers.

Of course, don't use accuracy as a metric for model building. Cohen's kappa is a reasonable alternative.

Model evaluation approaches

If your model returns predicted probabilities or other scores, chose a decision cutoff that makes an appropriate tradeoff in errors (using a dataset independent from training and testing). In R, the package OptimalCutpoints implements a number of algorithms, including cost-sensitive ones, for deciding a cutoff.

$\endgroup$
  • $\begingroup$ Thanks for the detailed reply. I have attempted to undersample and failed miserably. The models show excellent in-sample performance, but the imbalance is still present in the test set (and the real world data I will eventually use) so the models' OOS precision is horrible. I have also tried class-specific weights, but my application involves an easily quantifiable higher cost for false positive than for false negatives. As for one class classifiers, I tried to fit a linear svm (non-linear ones are too slow) and that has 0 precision even in sample... $\endgroup$ – em70 May 17 '14 at 6:26
  • 1
    $\begingroup$ I feel for you. High precision is hard if the vast majority of your cases are negative. I would use class-specific weights (such as inversely proportional to the fraction of cases in the class) for learning and save the error-type-specific weights for determining decision threshold. Hopefully you're using cross-validation with Cohen's kappa not accuracy for model selection. I would visualize the density of probabilities for the classes in calibration data along side precision and enrichment (precision / proportion of positive cases) at all cutoffs to really understand available tradeoffs. $\endgroup$ – MattBagg May 17 '14 at 16:55
5
$\begingroup$

My understanding is that this is an active area of research in the machine learning community and there are no great answers, but rather a large and growing number of potential solutions. You're likely going to get better answers if you specify the specific algorithms you're considering.

If you're using a parametric model (logistic regression) this should be less of an issue and you can just vary the threshold based on your loss function (cost of false negatives to false positives)

If you're using machine learning algorithms this might be trickier. Max Kuhn does a fair attempt at summarizing the issue in Chapter 16 of "Applied Predictive Modeling". But challenging topic to summarize. If you don't want to buy the book, R code is available in the AppliedPredictiveModeling package for this chapter and may be sufficient depending on your familiarity with R and the algorithms used.

Usually the discussing revolves around undersampling/oversampling +/- cost-sensitive algorithms. With variations like jous-boost also possible.
An example of this sort of discussion: Chen et al "Using Random Forest to Learn Imbalanced Data" http://statistics.berkeley.edu/sites/default/files/tech-reports/666.pdf

$\endgroup$
  • $\begingroup$ The issue with varying the threshold is that it is like changing the intercept of a regression model. In reality, I may well want to change the weight vector to keep cost into consideration. But if I do that, given the already severe imbalance, I end up with 0 precision! I haven't settled on any algorithm and have resources to implement cutting edge research ideas, if they are promising. I will take a look at the book you suggested. $\endgroup$ – em70 May 16 '14 at 4:07
  • $\begingroup$ The chapter is so-so. Solid effort, but hard topic to summarize. Lots of unsupported claims published on various methods. I do think stratified undersampling in random forests is a good start from a machine learning perspective. Code is in the book's package. $\endgroup$ – charles May 16 '14 at 13:38
0
$\begingroup$

You can take a look at scikit-learn's implementation. pay attention to the class_ weight argument which can have values of a dictionary of class weights or 'auto':

class sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma=0.0, coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, random_state=None)

You can play with the value of class_weight argument which can be a class weight dictionary or 'auto'. In 'auto' mode the learning algorithm will automatically assign weights to each class based on the number of samples within each of them.

scikit-learn has several other classification algorithms, some of which accept class weights.

$\endgroup$
  • $\begingroup$ Can you say more about how the class weights can be used to achieve the OP's goals? I think that is implicit in your post, but this isn't quite yet an answer. $\endgroup$ – gung Oct 6 '14 at 1:56
  • $\begingroup$ Yes, the class_weight argument can have a value 'auto' if some looks into the documentation or it can have a dictionary value which has the class weights. In case of 'auto' the learning algorithm itself finds the weight of each class according to the number of samples in each. $\endgroup$ – Ash Oct 6 '14 at 2:54

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.