# An Oversampling Method for Class Imbalance Problems on Large Datasets
## 2 Related Work  
The most successful and referenced oversampling method for class imbalance problems is SMOTE [8]. The main idea of SMOTE is to oversample the minority class by randomly generating synthetic objects between objects from the minority class and some of their \(k\)-nearest neighbors selected in random manner. In SMOTE, to generate a synthetic object, the feature difference between an object of the minority class and one of its \(k\)-nearest neighbors, selected in random manner, is computed. Then, for each feature, this difference is multiplied by a random number between 0 and 1. Finally, the multiplied differences is added to the object of the minority class in order to obtain a synthetic object that is then added to the training set. In Algorithm 1, a pseudocode of SMOTE is shown. ```
0: A minority class, \(N\) - Percent of oversampling (integer multiple of 100), \(k\) - number of nearest neighbors. 0: An oversampled minority class. \(n\gets N/100\) Number of objects to be generated for each object of the minority class for each object \(O\) in the minority class do  Compute the \(k\)-nearest neighbors of \(O\) in the minority class for\(j=1,...,n\)do \(Onn\leftarrow\) Randomly select one of the \(k\)-nearest neighbors of \(O\) \(Syn\leftarrow\) Initialize an empty object for each feature \(f\)do  Compute the feature difference between \(O_{f}\) and \(Onn_{f}\) \(r\gets Random(0,1)\) \(diff\leftarrow\) feature difference \(*r\) \(Syn_{f}\gets O_{f}+diff\) endfor  Add \(Syn\) to the minority class endfor endfor
```  
**Algorithm 1** SMOTE  
Due to the high success of SMOTE, several oversampling methods based on SMOTE (SMOTE-based methods) have been proposed in the literature [9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41; 42; 43; 44]. These methods modify SMOTE in different ways in order to improve the oversampling quality. In the next paragraphs, we will describe only some of the most widely cited and recent SMOTE-based methods. Borderline-SMOTE [9] first labels each object of the minority class as a border. An object is labeled as a border if the number of its \(k\)-nearest neighbors computed from the whole training set that belong to the majority class is greater than or equal to \(k/2\) and smaller than \(k\). Then, Borderline-SMOTE generates synthetic objects between the border objects and their \(k\)-nearest neighbors in the minority class. Safe Level SMOTE [11] computes, for each object of the minority class, a safe level (\(sl\)) value. This value depends on the number of nearest neighbors that the object has into the minority class among its \(k\)-nearest neighbors computed in the whole training set. Safe Level SMOTE generates synthetic objects between objects of the minority class with \(sl>0\) and their \(k\)-nearest neighbors in the minority class. If the safe level of the selected neighbor is 0, the object of the minority class is duplicated. Otherwise, Safe Level SMOTE computes a safe level ratio (\(slr\)) by dividing the \(sl\) value of the object in the minority class by the \(sl\) value of the selected neighbor. Then, to generate a synthetic object, as SMOTE does, the random number used for multiplying the feature difference between the object of the minority class and its selected neighbor is generated in a different interval, according to the \(slr\) value, as follows: if \(slr=1\) the random number is generated between 0 and \(1\); if \(slr>1\) the random number is generated between \(0\) and \(1/slr\); and if \(slr<1\) the random number is generated between \((1-slr)\) and \(1\). LNE [12] is based on Safe Level SMOTE (SLS) [11], but in the generation of the synthetic objects rather than computing the \(k\)-nearest neighbors in the minority class, LNE computes the \(k\)-nearest neighbors in the whole training set.