# A New Under-Sampling Method to Face Class Overlap and Imbalance
## 2 Resampling Algorithms to Face Class Imbalance
### Clustering-Based Algorithms  
Clustering-based under-sampling methods have become a well-grounded alternative to neighborhood-based algorithms for handling class imbalance because they can mitigate the problem of information loss caused by the removal of negative instances [16]. [PERSON] and [PERSON] introduced a cluster-based under-sampling algorithm named SBC (under-sampling based on clustering) [17], which rests upon the idea that there may exist various clusters in a data set and each cluster \(i\) may have a different ratio of majority class instances to minority class instances in the cluster \(i\). Thus, all instances are initially grouped into \(K\) clusters; then, a number of negative instances will be randomly selected from each cluster according to the ratio of majority class instances to minority class instances. Finally, it combines the selected negative instances from the \(K\) clusters with all the instances in the minority class. A similar under-sampling method corresponds to the algorithm proposed by [PERSON] et al. [36], which firstly clusters the majority class instances into \(K\) groups using the \(K\)-means algorithm and then selects \(|C^{+}|\times IR_{i}\) majority class instances from each cluster \(i\), where \(IR_{i}\) denotes the imbalance ratio in the cluster \(i\). Note that the aim of this method is not to obtain a perfectly balanced class distribution, but to reduce the disproportion between the size of the majority and minority classes. The ClusterOSS algorithm introduced by [PERSON] et al. [37] is an improvement of the OSS method. It starts by using the \(K\)-means algorithm to cluster the majority class instances. Then, the closest instances to the center of each cluster are used to start the application of OSS, removing borderline and noisy negative instances using the Tomek links. Unlike OSS, this technique does not start the under-sampling process at random, but defines how many and which instances should be chosen by applying the \(K\)-means clustering. [PERSON] et al. proposed an under-sampling technique named CUST [38] whose main objective is to remove redundant and noisy instances along with outliers from the majority class. In a first stage, the algorithm removes noisy negative instances using a techniques based on Tomek links. In a second stage, outliers and redundant negative instances are eliminated by using the \(K\)-means algorithm to cluster the remaining majority class instances. [PERSON] et al. introduced the ClusBUS algorithm [39], which aims at discarding negative instances that lie in class overlapping regions. First, it clusters the entire data set into \(K\) clusters using the DBSCAN algorithm. Then, for those clusters that contain both positive and negative instances, the algorithm removes a number of majority class instances necessary to create a vacuum around the minority class instances. [PERSON] et al. presented the CBIS technique [40] based on clustering analysis and instance selection: the affinity propagation algorithm groups similar negative instances into \(K\) clusters, and then an instance selection process filters out instances in each cluster. Finally, all reduced \(K\) clusters together with the instances of minority class form a balanced data set. [PERSON] et al. proposed the diversified sensitivity-based under-sampling (DSUS) method [41]. It selects useful instances yielding high stochastic sensitivity with respect to the currently trained classifier. To guarantee that only instances close to the decision boundary are selected and preserve the data distribution, negative instances are clustered and only a representative instance of each cluster participates in the selection process  
[PERSON] et al. developed two under-sampling strategies in which the \(K\)-means clustering technique is used [26]. Unlike the algorithms described previously, the number of clusters with negative instances is here defined to be equal to the size of the minority class.