DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> Direct marketing is a process of identifying likely buyers of certain products and promoting the products accordingly. It is increasingly used by banks, insurance companies, and the retail industry. Data mining can provide an effective tool for direct marketing. During data mining, several specific problems arise. For example, the class distribution is extremely unbalanced (the response rate is about 1%), the predictive accuracy is no longer suitable for evaluating learning methods, and the number of examples can be too large. In this paper, we discuss methods of coping with these problems based on our experience on direct-marketing projects using data mining. <s> BIB001 </s> DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> Imbalanced data sets are becoming ubiquitous, as many applications have very few instances of the \interesting" or \abnormal" class. Traditional machine learning algorithms can be biased towards majority class due to over-prevalence. It is desired that the interesting (minority) class prediction be improved, even if at the cost of additional majority class errors. In this paper, we study three issues, usually considered separately, concerning decision trees and imbalanced data sets | quality of probabilistic estimates, pruning, and eect of preprocessing the imbalanced data set by over or undersampling methods such that a fairly balanced training set is provided to the decision trees. We consider each issue independently and in conjunction with each other, highlighting the scenarios where one method might be preferred over another for learning decision trees from imbalanced data sets. <s> BIB002 </s> DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> The problem of learning from imbalanced data sets, while not the same problem as learning when misclassication costs are unequal and unknown, can be handled in a similar manner. That is, in both contexts, we can use techniques from roc analysis to help with classier design. We present results from two studies in which we dealt with skewed data sets and unequal, but unknown costs of error. We also compare for one domain these results to those obtained by over-sampling and under-sampling the data set. The operations of sampling, moving the decision threshold, and adjusting the cost matrix produced sets of classiers that fell on the same roc curve. <s> BIB003 </s> DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> There are several aspects that might influence the performance achieved by existing learning systems. It has been reported that one of these aspects is related to class imbalance in which examples in training data belonging to one class heavily outnumber the examples in the other class. In this situation, which is found in real world data describing an infrequent but important event, the learning system may have difficulties to learn the concept related to the minority class. In this work we perform a broad experimental evaluation involving ten methods, three of them proposed by the authors, to deal with the class imbalance problem in thirteen UCI data sets. Our experiments provide evidence that class imbalance does not systematically hinder the performance of learning systems. In fact, the problem seems to be related to learning with too few minority class examples in the presence of other complicating factors, such as class overlapping. Two of our proposed methods deal with these conditions directly, allying a known over-sampling method with data cleaning methods in order to produce better-defined class clusters. Our comparative experiments show that, in general, over-sampling methods provide more accurate results than under-sampling methods considering the area under the ROC curve (AUC). This result seems to contradict results previously published in the literature. Two of our proposed methods, Smote + Tomek and Smote + ENN, presented very good results for data sets with a small number of positive examples. Moreover, Random over-sampling, a very simple over-sampling method, is very competitive to more complex over-sampling methods. Since the over-sampling methods provided very good performance results, we also measured the syntactic complexity of the decision trees induced from over-sampled data. Our results show that these trees are usually more complex then the ones induced from original data. Random over-sampling usually produced the smallest increase in the mean number of induced rules and Smote + ENN the smallest increase in the mean number of conditions per rule, when compared among the investigated over-sampling methods. <s> BIB004 </s> DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> This paper proposes an innovative fraud detection method, built upon existing fraud detection research and Minority Report, to deal with the data mining problem of skewed data distributions. This method uses backpropagation (BP), together with naive Bayesian (NB) and C4.5 algorithms, on data partitions derived from minority oversampling with replacement. Its originality lies in the use of a single meta-classifier (stacking) to choose the best base classifiers, and then combine these base classifiers' predictions (bagging) to improve cost savings (stacking-bagging). Results from a publicly available automobile insurance fraud detection data set demonstrate that stacking-bagging performs slightly better than the best performing bagged algorithm, C4.5, and its best classifier, C4.5 (2), in terms of cost savings. Stacking-bagging also outperforms the common technique used in industry (BP without both sampling and partitioning). Subsequently, this paper compares the new fraud detection method (meta-learning approach) against C4.5 trained using undersampling, oversampling, and SMOTEing without partitioning (sampling approach). Results show that, given a fixed decision threshold and cost matrix, the partitioning and multiple algorithms approach achieves marginally higher cost savings than varying the entire training data set with different class distributions. The most interesting find is confirming that the combination of classifiers to produce the best cost savings has its contributions from all three algorithms. <s> BIB005 </s> DATA MINING FOR IMBALANCED DATASETS: AN OVERVIEW <s> Sampling Strategies <s> For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a "budget-sensitive" progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance. <s> BIB006
Over and under-sampling methodologies have received significant attention to counter the effect of imbalanced data sets    BIB006   BIB004 BIB005  BIB001 . Various studies in imbalanced datasets have used different variants of over and under sampling, and have presented (sometimes conflicting) viewpoints on usefulness of oversampling versus undersampling BIB002 BIB003 Drurnmond and Holte, 2003; BIB004 . The random under and over sampling methods have their various short-comings. The random undersampling method can potentially remove certain important examples, and random oversampling can lead to overfitting. However, there has been progression in both the under and over sampling methods.  used one-sided selection to selectively undersample the original population. They used Tomek Links  to identify the noisy and borderline examples. They also used the Condensed Nearest Neighbor (CNN) rule  to remove examples from the majority class that are far away from the decision border.  proposed Neighborhood Cleaning Rule (NCL) to remove the majority class examples. The author computes three nearest neighbors for each of the (Ei) examples in the training set. If Ei belongs to the majority class, and it is misclassified by its three nearest neighbors, then Ei is removed. If Ei belongs to the minority class, and it is misclassified by its three nearest neighbors then the majority class examples among the three nearest neighbors are removed. This approach can reach a computational bottleneck for very large datasets, with a large majority class.  discussed the effect of imbalance in a dataset. She evaluated three strategies: under-sampling, resampling and a recognition-based induction scheme. She considered two sampling methods for both over and undersampling. Random resampling consisted of oversampling the smaller class at random until it consisted of as many samples as the majority class and "focused resampling" consisted of oversampling only those minority examples that occurred on the boundary between the minority and majority classes. Random under-sampling involved under-sampling the majority class samples at random until their numbers matched the number of minority class samples; focused under-sampling involved under-sampling the majority class samples lying further away. She noted that both the sampling approaches were effective, and she also observed that using the sophisticated sampling techniques did not give any clear advantage in the domain considered. However, her oversampling methodologies did not construct any new examples. (Ling and Li, 1998) also combined over-sampling of the minority class with under-sampling of the majority class. They used lift analysis instead of accuracy to measure a classifier's performance. They proposed that the test examples be ranked by a confidence measure and then lift be used as the evaluation criteria. In one experiment, they under-sampled the majority class and noted that the best lift index is obtained when the classes are equally represented. In another experiment, they over-sampled the positive (minority) examples with replacement to match the number of negative (majority) examples to the number of positive examples. The over-sampling and under-sampling combination did not provide significant improvement in the lift index. We developed a novel oversampling technique called SMOTE (Synthetic Minority Oversampling TEchnique). It can be essential to provide new related information on the positive class to the learning algorithm, in addition to undersampling the majority class. This was the first attempt to introduce new examples in the training data to enrich the data space and counter the sparsity in the distribution. We will discuss SMOTE in more detail in the subsequent section. We combined SMOTE with undersampling. We used ROC analyses to present the results of our findings. Batista et al. BIB004 ) evaluated various sampling methodologies on a variety of datasets with different class distributions. They included various methods in both oversampling and undersampling. They conclude that SMOTE+Tomek and SMOTE+ENN are more applicable and give very good results for datasets with a small number of positive class examples. They also noted that the decision trees constructed from the oversampled datasets are usually very large and complex. This is similar to the observation by  .