Applying SPEA2 to prototype selection for nearest neighbor classification

The k-nearest neighbor (k-NN) algorithm is one of the most well-known supervised classifiers due to its ease of use and good performance. However, in spite of its popularity, k-NN suffers from some drawbacks such as high computational complexity, high storage requirements, and low noise tolerance. Prototype selection is a successful technique aimed at addressing aforementioned issues by reducing the size of training datasets without deprecating, but improving, the classification accuracy. Recently, evolutionary algorithms have been successfully applied to the optimisation of accuracy and size of reduction of prototype selection because of their innate exploration and exploitation capabilities in visiting the space of solutions of a problem. However, so far, all the evolutionary approaches for prototype selection are based on a so-called multi-objective 'a priori' technique, where multiple objectives are aggregated together into a single objective through a weighted combination. This paper proposes to apply, for the first time, an 'a posteriori' algorithm, namely SPEA2, to prototype selection problem in order to explicitly deal with both objectives and offer a better trade-off between classification and reduction performance. As shown in the experimental section, the application of SPEA2 allows to hold high accuracy in nearest neighbour classification with a significant reduction of training data thanks to the discovery of higher quality solutions than those detected by a conventional 'a priori' approach.