Prototype Generation Using Multiobjective Particle Swarm Optimization for Nearest Neighbor Classification

The nearest neighbor (NN) classifier suffers from high time complexity when classifying a test instance since the need of searching the whole training set. Prototype generation is a widely used approach to reduce the classification time, which generates a small set of prototypes to classify a test instance instead of using the whole training set. In this paper, particle swarm optimization is applied to prototype generation and two novel methods for improving the classification performance are presented: 1) a fitness function named error rank and 2) the multiobjective (MO) optimization strategy. Error rank is proposed to enhance the generation ability of the NN classifier, which takes the ranks of misclassified instances into consideration when designing the fitness function. The MO optimization strategy pursues the performance on multiple subsets of data simultaneously, in order to keep the classifier from overfitting the training set. Experimental results over 31 UCI data sets and 59 additional data sets show that the proposed algorithm outperforms nearly 30 existing prototype generation algorithms.Natural Science Foundation of China [61375119, 61170057, 60875080]; National Key Basic Research Development Plan (973 Plan) Project of China [2015CB352302]SCI(E)EIARTICLEweiwei.hu@pku.edu.cn; ytan@pku.edu.cn122719-27314