Binary classification with strongly unbalanced classes

Question

I have a data set in the form of (features, binary output 0 or 1), but 1 happens pretty rarely, so just by always predicting 0, I get accuracy between 70% and 90% (depending on the particular data I look at). The ML methods give me about the same accuracy, and I feel, there should be some standard methods to apply in this situation, that would improve the accuracy over the obvious prediction rule.

Answer 1

Both hxd1011 and Frank are right (+1). Essentially resampling and/or cost-sensitive learning are the two main ways of getting around the problem of imbalanced data; third is to use kernel methods that sometimes might be less effected by the class imbalance. Let me stress that there is no silver-bullet solution. By definition you have one class that is represented inadequately in your samples.

Having said the above I believe that you will find the algorithms SMOTE and ROSE very helpful. SMOTE effectively uses a $k$-nearest neighbours approach to exclude members of the majority class while in a similar way creating synthetic examples of a minority class. ROSE tries to create estimates of the underlying distributions of the two classes using a smoothed bootstrap approach and sample them for synthetic examples. Both are readily available in R, SMOTE in the package DMwR and ROSE in the package with the same name. Both SMOTE and ROSE result in a training dataset that is smaller than the original one.

I would probably argue that a better (or less bad) metric for the case of imbalanced data is using Cohen's $k$ and/or Receiver operating characteristic's Area under the curve. Cohen's kappa directly controls for the expected accuracy, AUC as it is a function of sensitivity and specificity, the curve is insensitive to disparities in the class proportions. Again, notice that these are just metrics that should be used with a large grain of salt. You should ideally adapt them to your specific problem taking account of the gains and costs correct and wrong classifications convey in your case. I have found that looking at lift-curves is actually rather informative for this matter. Irrespective of your metric you should try to use a separate test to assess the performance of your algorithm; exactly because of the class imbalanced over-fitting is even more likely so out-of-sample testing is crucial.

Probably the most popular recent paper on the matter is Learning from Imbalanced Data by He and Garcia. It gives a very nice overview of the points raised by myself and in other answers. In addition I believe that the walk-through on Subsampling For Class Imbalances, presented by Max Kuhn as part of the caret package is an excellent resource to get a structure example of how under-/over-sampling as well as synthetic data creation can measure against each other.

Answer 2

First, the evaluation metric for imbalanced data would not be accuracy. Suppose you are doing fraud detection, that 99.9% of your data is not fraud. We can easy make a dummy model that have 99.9% accuracy. (just predict all data non-fraud).

You want to change your evaluation metric from accuracy to something else, such as F1 score or precision and recall. In the second link I provided. there are details and intuitions on why precision recall will work.

For highly imbalanced data, building a model can be very challenging. You may play with weighted loss function or modeling one class only. such as one class SVM or fit a multi-variate Gaussian (As the link I provided before.)

Answer 3

Class imbalance issues can be addressed with either cost-sensitive learning or resampling. See advantages and disadvantages of cost-sensitive learning vs. sampling, copypasted below:

---

{1} gives a list of advantages and disadvantages of cost-sensitive learning vs. sampling:

2.2 Sampling

Oversampling and undersampling can be used to alter the class distribution of the training data and both methods have been used to deal with class imbalance [1, 2, 3, 6, 10, 11]. The reason that altering the class distribution of the training data aids learning with highly-skewed data sets is that it effectively imposes non-uniform misclassification costs. For example, if one alters the class distribution of the training set so that the ratio of positive to negative examples goes from 1:1 to 2:1, then one has effectively assigned a misclassification cost ratio of 2:1. This equivalency between altering the class distribution of the training data and altering the misclassification cost ratio is well known and was formally described by Elkan [9].

There are known disadvantages associated with the use of sampling to implement cost-sensitive learning. The disadvantage with undersampling is that it discards potentially useful data. The main disadvantage with oversampling, from our perspective, is that by making exact copies of existing examples, it makes overfitting likely. In fact, with oversampling it is quite common for a learner to generate a classification rule to cover a single, replicated, example. A second disadvantage of oversampling is that it increases the number of training examples, thus increasing the learning time.

2.3 Why Use Sampling?

Given the disadvantages with sampling, it is worth asking why anyone would use it rather than a cost-sensitive learning algorithm for dealing with data with a skewed class distribution and non-uniform misclassification costs. There are several reasons for this. The most obvious reason is there are not cost-sensitive implementations of all learning algorithms and therefore a wrapper-based approach using sampling is the only option. While this is certainly less true today than in the past, many learning algorithms (e.g., C4.5) still do not directly handle costs in the learning process.

A second reason for using sampling is that many highly skewed data sets are enormous and the size of the training set must be reduced in order for learning to be feasible. In this case, undersampling seems to be a reasonable, and valid, strategy. In this paper we do not consider the need to reduce the training set size. We would point out, however, that if one needs to discard some training data, it still might be beneficial to discard some of the majority class examples in order to reduce the training set size to the required size, and then also employ a cost-sensitive learning algorithm, so that the amount of discarded training data is minimized.

A final reason that may have contributed to the use of sampling rather than a cost-sensitive learning algorithm is that misclassification costs are often unknown. However, this is not a valid reason for using sampling over a costsensitive learning algorithm, since the analogous issue arises with sampling—what should the class distribution of the final training data be? If this cost information is not known, a measure such as the area under the ROC curve could be used to measure classifier performance and both approaches could then empirically determine the proper cost ratio/class distribution.

They also did a series of experiments, which was inconclusive:

Based on the results from all of the data sets, there is no definitive winner between cost-sensitive learning, oversampling and undersampling

They then try to understand which criteria in the datasets may hint at which technique is better fitted.

They also remark that SMOTE may bring some enhancements:

There are a variety of enhancements that people have made to improve the effectiveness of sampling. Some of these enhancements include introducing new “synthetic” examples when oversampling [5 -> SMOTE], deleting less useful majority- class examples when undersampling [11] and using multiple sub-samples when undersampling such than each example is used in at least one sub-sample [3]. While these techniques have been compared to oversampling and undersampling, they generally have not been compared to cost-sensitive learning algorithms. This would be worth studying in the future.

---

{1} Weiss, Gary M., Kate McCarthy, and Bibi Zabar. "Cost-sensitive learning vs. sampling: Which is best for handling unbalanced classes with unequal error costs?." DMIN 7 (2007): 35-41. https://scholar.google.com/scholar?cluster=10779872536070567255&hl=en&as_sdt=0,22 ; https://pdfs.semanticscholar.org/9908/404807bf6b63e05e5345f02bcb23cc739ebd.pdf

Answer 4

Several answers to this query have already provided several different approaches, all valid. This suggestion is from a paper and associated software by Gary King, eminent political scientist at Harvard. He has co-authored a paper titled Logistic Regression in Rare Events Data which provides some fairly cogent solutions.

Here's the abstract:

We study rare events data, binary dependent variables with dozens to thousands of times fewer ones (events, such as wars, vetoes, cases of political activism, or epidemiological infections) than zeros ("nonevents"). In many literatures, these variables have proven difficult to explain and predict, a problem that seems to have at least two sources. First, popular statistical procedures, such as logistic regression, can sharply underestimate the probability of rare events. We recommend corrections that outperform existing methods and change the estimates of absolute and relative risks by as much as some estimated effects reported in the literature. Second, commonly used data collection strategies are grossly inefficient for rare events data. The fear of collecting data with too few events has led to data collections with huge numbers of observations but relatively few, and poorly measured, explanatory variables, such as in international conflict data with more than a quarter-million dyads, only a few of which are at war. As it turns out, more efficient sampling designs exist for making valid inferences, such as sampling all variable events (e.g., wars) and a tiny fraction of nonevents (peace). This enables scholars to save as much as 99% of their (nonfixed) data collection costs or to collect much more meaningful explanatory variables. We provide methods that link these two results, enabling both types of corrections to work simultaneously, and software that implements the methods developed.

Here's a link to the paper ... http://gking.harvard.edu/files/abs/0s-abs.shtml

Answer 5

I have to disagree with all of the answers. The original problem is not appropriate for classification at all but calls for an analysis of tendencies. See http://fharrell.com/post/classification

Miscasting the task as a classification task is what has caused so much work for everyone, and has caused invalid statistical methods that discard valuable data to be considered.

Answer 6

Development of classifiers for datasets with imbalanced classes is a common problem in machine learning. Density-based methods can have significant merits over "traditional classifers" in such situation.

A density-based method estimates the unknown density $\hat{p}(x|y \in C)$, where $C$ is the most dominant class (In your example, $C = \{x: y_i = 0\}$).

Once a density estimate is trained, you can predict the probability that an unseen test record $x^*$ belongs to this density estimate or not. If the probability is sufficiently small, less than a specified threshold (usually obtained through a validation phase), then $\hat{y}(x^*) \notin C$, otherwise $\hat{y}(x^*) \in C$

You can refer to the following paper:

"A computable Plug-in estimator of Minimum Volume Sets for Novelty Detection," C. Park, J. Huang and Y. Ding, Operations Research, 58(5), 2013.

Answer 7

This is the sort of problem where Anomaly Detection is a useful approach. This is basically what rodrigo described in his answer, in which you determine the statistical profile of your training class, and set a probability threshold beyond which future measurements are determined not to belong to that class. Here is a video tutorial, which should get you started. Once you have absorbed that, I would recommend looking up Kernel Density Estimation.