# A New Under-Sampling Method to Face Class Overlap and Imbalance
## 3 The DBMIST-US Algorithm
### Differences between DBMIST-US and Related Works  
The algorithm proposed in this work differs from other related methods in several aspects. First, most developments focus on handling either class imbalance or class overlap separately, while DBMIST-US faces both intrinsic data complexities together. Although one can find a few works addressing both problems, in general, they consist of the application of different techniques in a sequential manner. For instance, [PERSON] et al. designed a methodology based on the use of the NCL algorithm to remove the overlapping majority class instances followed by an ensemble to randomly under-sample the majority class [49]. Similarly, [PERSON] and [PERSON] proposed an energy-based approach to clean the neighborhoods of minority class instances combined with an over-sampling procedure [50]. Other methods have been also proposed to handle imbalanced data sets with noisy and borderline instances together, but they are mostly based on modifying some previous resampling algorithm; in this line, for instance, [PERSON] et al. proposed an extension of the well-known SMOTE over-sampling algorithm through the inclusion of an iterative ensemble-based noise filter [8].  
Regarding the differences between DBMIST-US and the existing clustering-based methods, it is worth pointing out that most under-sampling techniques rely upon the \(K\)-means and the fuzzy \(K\)-means algorithms [16; 26; 36; 37; 38; 40; 41; 43; 51]. However, it is well-known that \(K\)-means may not be sufficiently effective when applied to imbalanced data because it always generates clusters with similar sizes [52]. Another weakness of these clustering algorithms is that they assume some prior knowledge of the number of clusters to face the imbalance problem. To overcome these shortcomings, our proposal employs the DBSCAN algorithm in the filtering stage. Some of the advantages of using DBSCAN are: (i) it can identify arbitrarily shaped clusters and detect noise, and (ii) the number of clusters is not a user-specified parameter. In addition, an MST-based approach is used to under-sample the majority class, which, to the best of our knowledge, this is the first development using the MST to face the imbalance problem. A related approach employs the Gabriel graph and the relative neighborhood graph to search for neighbors in SMOTE [53], which are supergraphs of the Euclidean MST.  
Finally, differences between DBMIST-US and other resampling methods that use DBSCAN can also be remarked. [PERSON] and [PERSON] proposed the hybrid DBSM algorithm, which employs DBSCAN for under-sampling and the SMOTE technique for over-sampling[54]; here, DBSCAN is used to create clusters from the whole training set, and then 50% of the majority class instances are eliminated from each cluster. Another approach is the DBSMOTE algorithm [55], which integrates DBSCAN and SMOTE; DBSCAN is applied to discover arbitrarily shaped clusters and SMOTE generates more synthetic positive instances around the core of the minority class rather than at the border. The main difference between our proposal and both these methods is that, unlike DBMIST-US, these are for over-sampling. On the other hand, the DBMUTE technique combines DBSCAN with the under-sampling MUTE algorithm [56] to discover and remove majority class instances from the overlapping region [57], but this is not intended to identify and remove noisy instances.