# An Undersampling Method Approaching the Ideal Classification Boundary for Imbalance Problems
## 3 Proposed Method
### A Cluster-Based Sampling Area Fitting the Classification Boundary Morphology and Its Undersampling  
The method proposed in this paper requires performing rough division on the linear separation hyperplane prior to executing the other steps. It is therefore unclear whether any random linear method will work. Figure 4 shows that, by using \(f(x_{1})\)-based division, the samples drawn in areas \(A\), \(B\), and \(C\) will most likely fall to their left; it also shows that \(f(x_{2})\)-based division will be more uniform in the above-mentioned area. In other words, different linear division methods will have different sampling results. Therefore, it is necessary to find a more reasonable linear division method in order to determine rough boundaries. Figure 3: Method of sampling near the linear boundary with partitions. Figure 2: Method of sampling near the nonlinear boundary. We therefore suggest that the mean error can be used to roughly determine the appropriate linear division \(f(x_{i})\) in order to obtain the initial linear separation hyperplane. \[f(x_{i})=\underset{f(x_{1}),f(x_{2}),\cdots,f(x_{n})}{\operatorname{argmin}} \Sigma_{k=1}^{|D|}(f(x^{(k)})-y^{(k)})^{2}. \tag{1}\]  
Herein, \(n\) is the number of the linear model \(f(x_{i})\), and \(y^{(k)}\) is the label of sample \(k\) of \(D\). Once the initial partition \(f(x_{i})\) has been determined, the undersampling is initiated. Firstly, Kmeans clustering is performed in the majority class \(D_{b}\), and the various clusters \(C_{i}\) are obtained. Then, according to the number of samples for \(D_{b}\), \(N_{s}\) (\(N_{s}=1.5*|D_{s}|\), here, \(D_{s}\) is the minority class), the number of samples for \(C_{i}\) is obtained, as follows:  
\[N_{s,C_{i}}=\frac{|C_{i}|}{|D_{b}|}N_{s}. \tag{2}\]  
**Definition 1**. : \(L_{i,f(x)}\) _is the diameter of the cluster facing the separating hyperplane. As shown in Figure 5, we calculate the distance \(L_{j}\) between each element \(j\) in \(C_{i}\) and \(f(x_{1})\); then, \(L_{i,f(x)}\) is_  
\[L_{i,f(x)}=L_{C_{i},max}-L_{C_{i},min}. \tag{3}\]  
_where, \(L_{C_{i},max}\) is the maximum distance from the samples in \(C_{i}\), which is perpendicular to \(f(x)\). Similarly, \(L_{C_{i},min}\) is the minimum distance._  
If \(\alpha<1\) is the spatial compression coefficient, then the sampling space in \(C_{i}\) is enclosed by a hyperplane with a distance \(f(x_{i})\) of \(L_{(C_{i},min)}\) and \(\alpha L_{(i,f(x))}\). The samples are obtained from a new undersampled majority class sample, namely set \(D_{bs}\); this can then form a balanced data set with the minority class \(D_{s}\) for classification. In order to minimize the distance between the sampled data objects and the boundary, we adopted a weighted method to update the samples in the majority class. That is, the closer the point is to the hyperplane, the greater the weight and the higher the probability that it will be sampled. In contrast, the farther the data object is from the hyperplane, the smaller the weight and the smaller the probability of it being sampled. Suppose \(f(x_{i})=\omega x_{i}+b\), then the weight formula is as follows:  
\[k_{i}=(Random(0,1))^{\frac{||\omega||}{\omega x_{i}+b}} \tag{4}\]  
Figure 4: The influence of different linear classification boundaries. In summary, the basic principle of our undersampling is as follows. Firstly, various clusters that can reflect the distribution of the majority-class samples are obtained via Kmeans clustering. Then, the spatial compression coefficient \(\alpha\) is applied in each cluster to obtain sub-sampling spaces that are closer to the boundaries. A greater weight \(k_{i}\) is assigned to samples that are closer to the boundary in order to ensure that these samples are more likely to be selected. Via this approach, a relatively balanced majority class sample set \(D_{bu}\) that better reflects the shape of the classification boundary after undersampling can be obtained. The sampling method is shown in Algorithm 1.