k-NN is one of the most popular and effective classifiers nowadays. However, it has some limitations that overcome its applicability in large scale scenarios: basically, it requires storing the whole training set, and it computes distances of a test sample with the training data set. These limitations have been traditionally alleviated with data reduction techniques. This paper introduces a multi-objective evolutionary approach for data reduction. Our method simultaneously generates prototypes and selects features for k-NN classifiers. Contrary to most of the existing approaches, our method treats the problem with multi-objective evolutionary optimizers. We show the effectiveness of our proposal in benchmark data and compare its performance with state of the art techniques.
CervantesA., GalvanI.M. and IsasiP., AMPSO: A new particle swarm method for nearest neighborhood classification, IEEE Trans Sys Man Cy B39(5) (2009), 1082-1091.
2.
Coello CoelloC.A., LamontG.B. and Van VeldhuizenD.A., Evolutionary Algorithms for Solving Multi-objective Problems, second edition, Springer, US, 2007.
3.
DebK., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 2001.
4.
DebK., PratapA., AgarwalS. and MeyarivanT., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation6(2) (2002), 182-197.
5.
DemšarJ., Statistical comparisons of classifiers over multiple data sets, J Mach Learn Res7 (2006), 1-30.
6.
EscalanteH.J., GraffM. and Morales-ReyesA., Pggp: Prototype generation via genetic programming, Applied Soft Computing40 (2016), 569-580.
7.
EscalanteH.J., Marín-CastroM., Morales-ReyesA., GraffM., Rosales-PérezA., Montes-y GómezM., Reyes-GarciaC.A. and GonzalezJ.A., MOPG: A multi-objective evolutionary algorithm for prototype generation, Pattern Analysis and Applications, 2015.
8.
FernandezF. and IsasiP., Evolutionary design of nearest prototype classifiers, J Heuristics10 (2004), 431-454.
9.
GarainU., Prototype reduction using an artificial immune system, Pattern Anal Appl11(3-4) (2008), 353-363.
10.
GarcíaS., DerracJ., CanoJ.R. and HerreraF., Prototype selection for nearest neighbor classification: Taxonomy and empirical study, IEEE Trans Pattern Anal Mach Intell34(3) (2012), 417-435.
11.
KnowlesJ. and CorneD., Approximating the nondominated front using the pareto archived evolution strategy, Evol Comput8(2) (2000), 149-172.
12.
NanniL. and LuminiA., Particle swarm optimization for prototype reduction, Neurocomputing72(4-6) (2008), 1092-1097.
13.
Olvera-LopezJ.A., Carrasco-OchoaJ.A. and Martinez-TrinidadJ.F., Prototype selection methods, Computación y Sistemas13(4) (2010), 449-462.
14.
Rosales-PérezA., GonzalezJ., Coello-CoelloC., Reyes-GarciaC. and EscalanteH., Evolutionary multi-objective approach for prototype generation and feature selection, in: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Bayro-CorrochanoE. and HancockE., eds, volume 8827 of Lecture Notes in Computer Science, Springer International Publishing, 2014, pp. 424-431, http://dx.doi.org/10.1007/978-3-319-12568-8_52.
15.
SchafferJ.D., Multiple objective optimization with vector evaluated genetic algorithms, in: Proceedings of the 1st International Conference on Genetic Algorithms, L. Erlbaum Associates Inc., Hillsdale, NJ, USA (1985), 93-100.
16.
TrigueroI., DerracJ., GarciaS. and HerreraF., A taxonomy and experimental study on prototype generation for nearest neighbor classification, IEEE Trans Syst Man Cy C42(1) (2012), 86-100.
17.
TrigueroI., GarciaS. and HerreraF., Differential evolution for optimizing the positioning of prototypes in nearest neighbor classification, Pattern Recogn44 (2011), 901-916.
18.
WilsonD.R. and MartinezT.R., Reduction techniques for instance-based learning algorithms, Mach Learn38 (2000), 257-286.
19.
WuX., KumarV., Ross QuinlanJ., GhoshJ., YangQ., MotodaH., McLachlanG.J., NgA., LiuB., YuP.S., ZhouZ.-H., SteinbachM., HandD.J. and SteinbergD., Top 10 algorithms in data mining, Knowl Inf Sys14(1) (2007), 1-37.
20.
YuX. and GenM., Introduction to Evolutionary Algorithms, Springer, 2010.
21.
ZhangQ. and LiH., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions OnEvolutionary Computation11(6) (2007), 712-731.
22.
ZitzlerE., LaumannsM. and ThieleL., SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, in: Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, GiannakoglouK.C., TsahalisD.T., PériauxJ., PapailiouK.D. and FogartyT., eds, International Center for Numerical Methods in Engineering, 2001, pp. 95-100.
