关键词: 非平衡类, k近邻, 划分, 过抽样, 聚类算法

Abstract: K-Nearest Neighbor (kNN) is an extremely simple but surprisingly effective supervised learning method which can efficiently discover local characteristics of the data. This paper applies kNN to class-imbalanced data and proposes a novel kNN classification algorithm for imbalanced problem. Unlike traditional kNN, for the learning process, the proposed method firstly partitions the majority set into several clusters using partition algorithm(such as K-Means), merges each cluster with the minority set as a new training set to train a kNN model, and therefore the algorithm constructs a classifier library consisting of kNN models. For the prediction, the proposed method uses partition algorithm (such as K-Means) to select a model from the library to predict the class label of an instance. In this way, the proposed algorithm guarantees that the kNN model can efficiently discover local characteristics of the data, and also fully consider the effect of imbalance of the data on the performance of the classifier. Besides, the algorithm effectively promotes the efficiency of kNN. To further enhance the performance of the proposed algorithm, oversampling technique (SMOTE) is applied to the proposed method. Experimental results on KEEL data sets show that even employing the strategy of random partition to partition the majority set, the proposed method can effectively enhance the generalization performance of kNN method on evaluation measures of recall, g-mean, f-measure and AUC.

Key words: class-imbalanced problem, kNN, partition, oversampling, clustering