A new locally adaptive k-nearest neighbor algorithm based on discrimination class

摘要

The k-nearest neighbor (kNN) rule is a classical non-parametric classification algorithm in pattern recognition, and has been widely used in many fields due to its simplicity, effectiveness and intuitiveness. However, the classification performance of the kNN algorithm suffers from the choice of a fixed and single value of k for all queries in the search stage and the use of simple majority voting rule in the decision stage.In this paper, we propose a new kNN-based algorithm, called locally adaptive k-nearest neighbor algorithm based on discrimination class (DC-LAKNN). In our method, the role of the second majority class in classification is for the first time considered. Firstly, the discrimination classes at different values of k are selected from the majority class and the second majority class in the k-neighborhood of the query. Then, the adaptive k value and the final classification result are obtained according to the quantity and distribution information on the neighbors in the discrimination classes at each value of k.Extensive experiments on eighteen real-world datasets from UCI (University of California, Irvine) Machine Learning Repository and KEEL (Knowledge Extraction based on Evolutionary Learning) Repository show that the DC-LAKNN algorithm achieves better classification performance compared to standard kNN algorithm and nine other state-of-the-art kNN-based algorithms.