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.

Applying SPEA2 to prototype selection for nearest neighbor classification

Acampora, Giovanni;Tortora, Genoveffa;Vitiello, Autilia
2016

Abstract

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.
9781509018970
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4705359
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact