Imbalanced instance selection based on Laplacian matrix decomposition with weighted k-nearest-neighbor graph

Data are an essential component for building machine learning models. Linearly separable high-quality data are conducive to building efficient classification models. However, the collected dataset is not of high quality, and the number of instances for difference class is not absolutely consistent. Therefore, models built on these datasets are vulnerable to problems such as class-imbalance, class-overlap, and other problems. Traditional instance selection algorithms mainly determine whether there is redundancy or overlap in instances based on the degree of similarity between instances. Therefore, these methods only focus on the local information of the dataset and ignore the global approximate relationship of the instances in the dataset. In this paper, an instance selection method based on the global relationship of instances in the dataset is proposed, called instance selection based on Laplacian matrix decomposition with weighted k-nearest-neighbor graph (LMD-WNG). First, this method tries to construct a new distance-weighted Laplacian matrix using the weighted k-nearest-neighbor graph. Then, the distance-weighted Laplacian matrix is decomposed using a Schur decomposition method. Finally, according to the eigenvalues of the decomposed real matrix, a training dataset suitable for model learning is selected, and a classifier is constructed on the new training data. The experimental results show that as the imbalance ratio increases, LMD-WNG becomes more sensitive to parameter k. When the significance level is \(p = 0.05\) $p=0.05$ , the analysis results using Friedman ranking and the Holm’s post hoc test show that LMD-WNG is significantly better than or similar to other state-of-the-art algorithms on 30 datasets.