# An Undersampling Method Approaching the Ideal Classification Boundary for Imbalance Problems
## 3 Proposed Method
### Undersampling That Enables Close-Fitting Data Distribution at the Ideal Classification Boundary
According to its performance, we present the following assumptions. **Hypothesis 1**. : _There is an \(m\) classifier that obtains the best result in a cycle of ensemble learning under \(\phi(x,f(x_{1}))\) distribution sampling._  
According to Hypothesis 1, there exists an optimal number of classifiers that need to be integrated within a cycle, and we apply Algorithm 2 to determine this number. We set a stop threshold \(\theta\) and record the result of this ensemble learning. Initially, the number of classifiers in ensemble learning ranges from 1 to a very large number. Then, we increase the number of classifiers and obtain their classification results \(r_{i}\). When multiple \(\theta\) consecutive \(r_{i}\) values that are less than the current best result \(r\) are observed, the optimal number of classifiers \(m\) is output. ```
0: imbalanced data set \(D\)  stop threshold \(\theta\)  Number of ensemble learning iterations \(n\)  Evaluation result \(r=0\)  The mode of classification with undersampling \(M\)
```
0: Optimal times of ensemble learning \(m\) \(Num=0,label=0\) for\(i=1\) to \(n\)do \(r_{i}\) = Adaboost(\(M\),\(i\)) // \(i\) is the time of ensemble learning if\(r_{i}>r\)then \(r=r_{i}\) \(ilabel=i\) \(Num=0\)  Save the result of \(ilabel\) else \(Num++\) endif if\(Num>\theta\)then \(m=ilabel\)  Output the result of \(m\)  break endif endfor
```

**Algorithm 2** DNC: Determine the number of classifiers in ensemble learning and output the best result

### Our Method FDUS and Its Time Complexity

As mentioned previously, the noise reduction achieved by kNN during imbalanced classification can improve the results; we therefore utilized it to perform our preprocessing. By taking the foregoing description of this section into consideration, we named our method FDUS (Fitting data **D**istribution with **U**nder**S**ampling). This is shown in Algorithm 3. ```
0: imbalanced data set \(D\)  Space compression factor \(\alpha\)  Classification model \(f\) \(D^{\prime}\) = \(kNN(D)\) //Data preprocessing and denoising  Obtain \(\hat{H}\) by choosing the right linear classifier  Use _Kmeans_ to divide majority class  Perform WUC  Use DNC to output result
```

**Algorithm 3** FDUS

The time complexity of kNN is \(O(N*N)\). We use linear SVM, linear regression, and logistic regression to optimize rough linear classification. The time complexity at this time is \(3*O(N*N)\). The time complexity of _Kmeans_ is \(O(n*k*t)\). Since both \(k\) and \(t\) are deterministic values and \(k,t\ll N\), the time complexity of _Kmeans_ approaches \(O(N)\). The time complexity of assigning weights to majority-class samples is \(O(N)\), and the time complexity of determining the number of classifiers in ensemble learning and outputting the optimal results is \(m*O(N*N)\). Since there is no nesting between processes, the time complexity of the overall sampling algorithm is \(O(N*N)\). ## 4 Experiments and Results

In this section, we first show the experimental details of the proposed method; these include the data sets, the comparison method, and the evaluation index. Then, we verify the aforementioned hypothesis. Finally, we analyze and compare each method based on the experimental results. ### Experimental Setup

**Data sets** We conducted experiments on 20 imbalanced data sets obtained from **keel** ([[https://sci2s.ugr.es/keel/imbalanced.php](https://sci2s.ugr.es/keel/imbalanced.php)]([https://sci2s.ugr.es/keel/imbalanced.php](https://sci2s.ugr.es/keel/imbalanced.php)) (Visits since 5 November 2005)). Table 1 shows that the range in the imbalance rate (\(ir\)) (\(ir=\frac{|majority-classsamples|}{|minority-classsamples|}\)) of the data sets is \((1.86,40.5)\), that the range in the examples of the data sets is \((184,5472)\), and that the range in the dimension of the data sets is \((4,19)\). It is evident that these data sets include both low-dimensional data and high-dimensional data, with both a low imbalance rate and a high imbalance rate; this enables us to perform a comprehensive evaluation of the proposed method.