A Nearest Prototype Selection Algorithm Using Multi-objective Optimization and Partition

Prototype selection aims at reducing the scale of datasets to improve prediction accuracy and operation efficiency by removing noisy or redundant patterns via the nearest neighbor classification algorithms. Genetic algorithms have been used recently for prototype selection and showed good performance, however, they have some drawbacks such as the deteriorated running effect, slow convergence for the large datasets. The goal of designing good prototype selection algorithm is to maximize prediction classification accuracy and minimize the reduction ratio simultaneously. According to this goal, a two objective optimization model is set up for prototype selection problem. To make the model easier to be solved, the model is transformed to a single objective optimization model by the division of the two objectives. To solve the problem efficiently, a new prototype selection algorithm based on genetic algorithm and the divide-and-conquer partition is presented. The divide-and-conquer partition can divide the whole dataset into some random subsets, and thus make the problems more easier. Then, the genetic algorithm is specifically designed on these divided random subsets. The simulation results indicate that the proposed algorithm can obtain smaller reduction ratio and higher classification efficiency, or at least comparable to those of some existing compared algorithms. This illustrates that the proposed algorithm is an expedient method in design nearest neighbor classifiers.