# A Density-Based Random Forest for Imbalanced Data Classification
## 2 Related Work
### Data-Level Imbalanced Data Processing  
At the data level, oversampling and undersampling are the main categories of methods used to process imbalanced data [5]. Oversampling balances the number of classes by duplicating the minority class samples, but this may lead to overfitting. Undersampling involves balancing the training sets by deleting some majority class samples. However, some useful information may be lost in this process, leading to underfitting.  
The synthetic minority oversampling technique (SMOTE) [6] is common in practical applications. It is designed to use the nearest neighbor algorithm to select randomly \(N\) samples from the \(k\) nearest neighbors for linear interpolation, which can balance the categories in the original dataset by adding new minority class samples. Many novel methods have been proposed to further improve on this idea [7; 8; 9].  
In classification, boundary samples are typically more likely to be misclassified. Therefore, the borderline SMOTE algorithm [10] was proposed based on the SMOTE algorithm. In contrast to other oversampling methods, the algorithm uses only relatively few class samples from the boundary samples to construct new samples.  
The ADASYN algorithm [11] extends each minority class sample according to the density distribution of the training set with different weights to balance the training set. In contrast, DBRF uses the density method to find all the samples at the boundary without re-synthesizing new data points.  
The compressed nearest neighbor rule (CNNR) [12] was developed to remove redundant information by undersampling the majority samples using the one-nearest neighbor algorithm and removing the majority samples far from the decision boundary. Then, a reduced dataset \(E\) is obtained from the original dataset \(D(E\subseteq D)\). Because the _CNNR_ method selects samples randomly, it causes unnecessary samples, such as noise, to remain in \(E\).  
The TomekLinks algorithm [13] is an undersampling algorithm for removing noise and boundary samples. Given two samples \(x_{i}\) and \(x_{j}\) from different classes, \(dist(x_{i},x_{j})\) represents the distance between the two samples. If no sample \(x\) meets the conditions that \(dist(x_{i},x)<dist(x_{i},x_{j})\) or \(dist(x_{j},x)<dist(x_{i},x_{j})\), the sample pair \((x_{i},x_{j})\) constitutes a TomekLink. Either one of the two samples in TomekLink is noise or both are on the boundary of the two types. Using this property, the method can delete the noise and redundant samples by constituting the TomekLinks.  
The one-sided selection algorithm (OSS) [14] attempts intelligent undersampling of most classes by removing redundant data or artificial noise.  
The edited nearest neighbor (ENN) algorithm [15] reduces majority samples through a 3 NN method. First, the ENN finds three samples that have the nearest distances to a certain sample \(x\). Then, if two or more of them have a different class than the sample \(x\), the sample \(x\) is deleted. Because most samples are often surrounded by majority classes, relatively few majority samples are deleted by the ENN algorithm. Therefore, the neighborhood cleaning rule [16] was modified from the ENN. If the sample is a majority sample, it will do the same as the ENN. Majority samples are removed if the sample is a minority sample and more than two of three samples chosen by the 3 NN are majority samples.