# An Oversampling Method for Class Imbalance Problems on Large Datasets
## 3 Proposed Method
Consequently, we obtain an oversampling method that is faster than SMOTE and the SMOTE-based methods. The first step of our method computes, for each feature the minimum, maximum and mode values in the minority class. Then, the absolute differences between the mode and the minimum and maximum values are computed. Then, a random number is generated for each feature. This random number is multiplied by one of the differences and subtracted or added to the corresponding feature mode. To decide if a difference is subtracted or added, we generate a random number between 0.0 and 1.0; then, if the generated random number is lower than 0.5, the difference is subtracted. Otherwise, the difference is added. Thus, the generated synthetic object's feature values will be clustered around the mode and in the region defined by each feature's difference values. In the proposed method, we use a random number between 0 and 1; this allows the generation of objects as far as the differences allow, but not too far so as to avoid the generation of feature value outside the observed feature value range. We want to point out that if the random number that is multiplied by the difference is closer to 0, the synthetic objects are generated closer to the mode of the class on the corresponding feature, or, in the opposite case, if the random number is close to 1, the feature values of the synthetic object is generated farther from the mode of the class and closer to the minimum or maximum values. Finally, the above-described procedure is repeated as many times as the number of synthetic objects to be generated \(N\) (an input parameter of our method). A pseudo-code of the proposed method is shown in Algorithm 2. To determine the computational complexity of Fast SMOTE, we ill analyze each one of its steps (see Algorithm 2). Steps 1-3 of Fast-SMOTE are \(\mathcal{O}(nf)\) (where \(n\) is the number of objects in the minority class and \(f\) is the number of features of the dataset), because as it is well-known, computing the minimum and maximum and the mode from grouped data of \(n\) values is \(\mathcal{O}(n)\), and this must be done for each feature. Steps 4 and 5 are \(\mathcal{O}(f)\), because they involves just a difference for each one of the \(f\) features. The FOR loop of step 6 is repeated \(n\) times, and inside of this loop, we have a nested FOR loop that is repeated \(f\) times. In the inner loop, the steps 9-15 are \(\mathcal{O}(1)\). Therefore the complexity of the FOR loop of step 6 is \(\mathcal{O}(nf)\), and hence the complexity of Fast-SMOTE is \(\mathcal{O}(nf)\). This complexity is smaller than the complexity of SMOTE and SMOTE-based methods, which is at least \(\mathcal{O}(n^{2}f)\)[22; 53] due to the \(k\)-nearest neighbors search. Moreover, this complexity is similar to the complexity of NDO, which is the only oversampling method reported in the literature that is not based on computing the \(k\)-nearest neighbors and therefore that can be applied to large datasets. ```
0: A minority class, \(N\) - number of synthetic objects to be generated. 0: An oversampled minority class. \(MIN\leftarrow\) Minimum value for each feature into the minority class. \(MAX\leftarrow\) Maximum value for each feature into the minority class. \(MODE\leftarrow\) Mode value for each feature into the minority class. \(MinDif\gets MODE-MIN\) Absolute difference between the mode and the minimum value for each feature into the minority class. \(MaxDir\gets MAX-MODE\) Absolute difference between the mode and the maximum value for each feature into the minority class. for\(j=1,...,N\)do \(Sym\leftarrow\) Initialize an empty object foreach feature \(f\)do \(r\gets Random(0,1)\) \(r2\gets Random(0,1)\) ifr2\(<0.5\)then \(gap\gets MinDif\ast r\) else \(gap\gets MaxDiff_{f}\ast r\) endif \(Syn_{f}\gets MODE_{f}+gap\) endfor  Add \(Syn\) to the minority class. endfor
```  
**Algorithm 2** Fast-SMOTE