Skip to main content
Erschienen in: Pattern Analysis and Applications 1/2017

06.02.2015 | Theoretical Advances

MOPG: a multi-objective evolutionary algorithm for prototype generation

verfasst von: Hugo Jair Escalante, Maribel Marin-Castro, Alicia Morales-Reyes, Mario Graff, Alejandro Rosales-Pérez, Manuel Montes-y-Gómez, Carlos A. Reyes, Jesus A. Gonzalez

Erschienen in: Pattern Analysis and Applications | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Prototype generation deals with the problem of generating a small set of instances, from a large data set, to be used by KNN for classification. The two key aspects to consider when developing a prototype generation method are: (1) the generalization performance of a KNN classifier when using the prototypes; and (2) the amount of data set reduction, as given by the number of prototypes. Both factors are in conflict because, in general, maximizing data set reduction implies decreasing accuracy and viceversa. Therefore, this problem can be naturally approached with multi-objective optimization techniques. This paper introduces a novel multi-objective evolutionary algorithm for prototype generation where the objectives are precisely the amount of reduction and an estimate of generalization performance achieved by the selected prototypes. Through a comprehensive experimental study we show that the proposed approach outperforms most of the prototype generation methods that have been proposed so far. Specifically, the proposed approach obtains prototypes that offer a better tradeoff between accuracy and reduction than alternative methodologies.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
One should note there are works comparing a few PS and PG methods over a small number of data sets [19, 22].
 
2
One should note that among the considered data sets numeric and nominal attributes are included. For simplicity we have deliberatively transformed nominal attributes into integers and applied MOPG without any modification.
 
3
Please note that, in general, in evolutionary algorithms large populations do not necessarily mean better performance. This behavior is observed when the search space has not been explored extensively, which is beneficial for avoiding overfitting.
 
4
Please note that the 25 methods have been evaluated on small data sets, but only 20 out of the 25 were evaluated in large data sets [28]. Five methods were not considered for large data sets because they were too computational expensive, see [28] for details.
 
6
This is the statistical test recommended by Demsar for comparing classification methods over multiple data sets [11].
 
Literatur
1.
Zurück zum Zitat Aler R, Handl J, Knowles JD (2013) Comparing multi-objective and threshold-moving roc curve generation for a prototype-based classifier. In: Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, pp 1029–1036 Aler R, Handl J, Knowles JD (2013) Comparing multi-objective and threshold-moving roc curve generation for a prototype-based classifier. In: Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, pp 1029–1036
2.
Zurück zum Zitat Cervantes A, Galvan IM, Isasi P (2009) AMPSO: a new particle swarm method for nearest neighborhood classification. IEEE Trans. Sys. Man Cybern. B 39(5):1082–1091CrossRef Cervantes A, Galvan IM, Isasi P (2009) AMPSO: a new particle swarm method for nearest neighborhood classification. IEEE Trans. Sys. Man Cybern. B 39(5):1082–1091CrossRef
3.
Zurück zum Zitat Chatelain Clément, Adam Sébastien, Lecourtier Yves, Heutte Laurent, Paquet Thierry (2010) A multi-model selection framework for unknown and/or evolutive misclassification cost problems. Pattern Recogn. 43(3):815–823CrossRefMATH Chatelain Clément, Adam Sébastien, Lecourtier Yves, Heutte Laurent, Paquet Thierry (2010) A multi-model selection framework for unknown and/or evolutive misclassification cost problems. Pattern Recogn. 43(3):815–823CrossRefMATH
4.
Zurück zum Zitat Chen JH, Chen HM, Ho SY (2005) Design of nearest neighbor classifiers: multi-objective approach. Int. J. Approx. Reason. 40:3–22CrossRefMATH Chen JH, Chen HM, Ho SY (2005) Design of nearest neighbor classifiers: multi-objective approach. Int. J. Approx. Reason. 40:3–22CrossRefMATH
5.
Zurück zum Zitat Coello Coello CA, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems. Genetic and evolutionary computation, 2nd edn. Springer, USA Coello Coello CA, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems. Genetic and evolutionary computation, 2nd edn. Springer, USA
6.
Zurück zum Zitat Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13(1):21–27CrossRefMATH Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans. Inform. Theory 13(1):21–27CrossRefMATH
7.
Zurück zum Zitat Cruz-Vega I, Garcia-Limon M, Escalante HJ (2014) Adaptive surrogates with a neuro-fuzzy network and granular computing. In: Proceedings of GECCO 2014. ACM Press, pp 761–768 Cruz-Vega I, Garcia-Limon M, Escalante HJ (2014) Adaptive surrogates with a neuro-fuzzy network and granular computing. In: Proceedings of GECCO 2014. ACM Press, pp 761–768
8.
Zurück zum Zitat Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley
9.
Zurück zum Zitat Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2):182–197CrossRef Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2):182–197CrossRef
10.
Zurück zum Zitat Decaestecker C (1997) Finding prototypes for nearest neighbour classification by means of gradient descent and deterministic annealing. Pattern Recogn. 30(2):281–288CrossRef Decaestecker C (1997) Finding prototypes for nearest neighbour classification by means of gradient descent and deterministic annealing. Pattern Recogn. 30(2):281–288CrossRef
11.
Zurück zum Zitat Demsar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH Demsar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH
12.
Zurück zum Zitat Dos-Santos EM, Sabourina R, Maupinb P (2008) A dynamic overproduce-and-choose strategy for the selection of classifier ensembles. Pattern Recogn. 41:2993–3009CrossRefMATH Dos-Santos EM, Sabourina R, Maupinb P (2008) A dynamic overproduce-and-choose strategy for the selection of classifier ensembles. Pattern Recogn. 41:2993–3009CrossRefMATH
13.
Zurück zum Zitat Eiben AE, Smith JE (2010) Introduction to evolutionary computing. Natural computing. Springer Eiben AE, Smith JE (2010) Introduction to evolutionary computing. Natural computing. Springer
14.
Zurück zum Zitat Escalante HJ, Mendoza KM, Graff M, Morales-Reyes A (2013) Genetic programming of prototypes for pattern classification. In: Proceedings of IbPRIA 2013, vol. 7887 of LNCS. Springer, pp 100–107 Escalante HJ, Mendoza KM, Graff M, Morales-Reyes A (2013) Genetic programming of prototypes for pattern classification. In: Proceedings of IbPRIA 2013, vol. 7887 of LNCS. Springer, pp 100–107
15.
Zurück zum Zitat Fernandez F, Isasi P (2004) Evolutionary design of nearest prototype classifiers. J. Heuristics 10:431–454CrossRef Fernandez F, Isasi P (2004) Evolutionary design of nearest prototype classifiers. J. Heuristics 10:431–454CrossRef
16.
Zurück zum Zitat Garain U (2008) Prototype reduction using an artificial immune system. Pattern Anal. Appl. 11(3–4):353–363MathSciNetCrossRef Garain U (2008) Prototype reduction using an artificial immune system. Pattern Anal. Appl. 11(3–4):353–363MathSciNetCrossRef
17.
Zurück zum Zitat García S, Derrac J, Cano JR, Herrera F (2012) Prototype selection for nearest neighbor classification: Taxonomy and empirical study. IEEE Trans. Pattern Anal. Mach. Intell. 34(3):417–435CrossRef García S, Derrac J, Cano JR, Herrera F (2012) Prototype selection for nearest neighbor classification: Taxonomy and empirical study. IEEE Trans. Pattern Anal. Mach. Intell. 34(3):417–435CrossRef
18.
Zurück zum Zitat Hastie T, Tibshirani R, Friedman J (2001) The elements of statistical learning. Springer, New YorkCrossRefMATH Hastie T, Tibshirani R, Friedman J (2001) The elements of statistical learning. Springer, New YorkCrossRefMATH
19.
Zurück zum Zitat Kim SW, Oommen BJ (2003) A brief taxonomy and ranking of creative prototype reduction schemes. Pattern Anal. Appl. 6:232–244MathSciNetCrossRef Kim SW, Oommen BJ (2003) A brief taxonomy and ranking of creative prototype reduction schemes. Pattern Anal. Appl. 6:232–244MathSciNetCrossRef
20.
Zurück zum Zitat Koplowitz J, Brown T (1981) On the relation of performance to editing in nearest neighbor rules. Pattern Recogn. 13(3):251–255CrossRef Koplowitz J, Brown T (1981) On the relation of performance to editing in nearest neighbor rules. Pattern Recogn. 13(3):251–255CrossRef
21.
Zurück zum Zitat Li J, Wang Y (2013) A nearest prototype selection algorithm using multi-objective optimization and partition. In: Proceedings of the 9th International Conference on Computational Intelligence and Security. IEEE, pp. 264–268 Li J, Wang Y (2013) A nearest prototype selection algorithm using multi-objective optimization and partition. In: Proceedings of the 9th International Conference on Computational Intelligence and Security. IEEE, pp. 264–268
22.
Zurück zum Zitat Lozano M, Sotoca JM, Sánchez JS, Pla F, Pkalska E, Duin RPW (2006) Experimental study on prototype optimisation algorithms for prototype-based classification in vector spaces. Pattern Recogn. 39(10):1827–1838CrossRefMATH Lozano M, Sotoca JM, Sánchez JS, Pla F, Pkalska E, Duin RPW (2006) Experimental study on prototype optimisation algorithms for prototype-based classification in vector spaces. Pattern Recogn. 39(10):1827–1838CrossRefMATH
23.
Zurück zum Zitat Nanni L, Lumini A (2008) Particle swarm optimization for prototype reduction. Neurocomputing 72(4–6):1092–1097 Nanni L, Lumini A (2008) Particle swarm optimization for prototype reduction. Neurocomputing 72(4–6):1092–1097
24.
Zurück zum Zitat Olvera A, Carrasco-Ochoa JA, Martinez-Trinidad JF, Kittler J (2010) A review of instance selection methods. Artif. Intell. Rev. 34:133–143CrossRef Olvera A, Carrasco-Ochoa JA, Martinez-Trinidad JF, Kittler J (2010) A review of instance selection methods. Artif. Intell. Rev. 34:133–143CrossRef
25.
Zurück zum Zitat Storn R, Price KV (1997) Differential evolution a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(10):341–359MathSciNetCrossRefMATH Storn R, Price KV (1997) Differential evolution a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(10):341–359MathSciNetCrossRefMATH
26.
Zurück zum Zitat Rosales A, Coello CA, Gonzalez J, Reyes CA, Escalante HJ (2013) A hybrid surrogate-based approach for evolutionary multi-objective optimization. In: Proceedings of Congress on Evolutionary Computation 2013. IEEE, pp 2548–2555 Rosales A, Coello CA, Gonzalez J, Reyes CA, Escalante HJ (2013) A hybrid surrogate-based approach for evolutionary multi-objective optimization. In: Proceedings of Congress on Evolutionary Computation 2013. IEEE, pp 2548–2555
27.
Zurück zum Zitat Rosales A, Gonzalez J, Coello CA, Escalante HJ, Reyes CA (2014) Surrogate-assisted multi-objective model selection for support vector machines. Neurocomputing (in press) Rosales A, Gonzalez J, Coello CA, Escalante HJ, Reyes CA (2014) Surrogate-assisted multi-objective model selection for support vector machines. Neurocomputing (in press)
28.
Zurück zum Zitat Triguero I, Derrac J, García S, Herrera F (2012) A taxonomy and experimental study on prototype generation for nearest neighbor classification. IEEE Trans. Sys. Man Cybern. C 42(1):86–100CrossRef Triguero I, Derrac J, García S, Herrera F (2012) A taxonomy and experimental study on prototype generation for nearest neighbor classification. IEEE Trans. Sys. Man Cybern. C 42(1):86–100CrossRef
29.
Zurück zum Zitat Triguero I, Peralta D, Bacardit J, Garcia S, Herrera F (2014) MRPR: a mapreduce solution for prototype reduction in big data classification. Neurocomputing (in press) Triguero I, Peralta D, Bacardit J, Garcia S, Herrera F (2014) MRPR: a mapreduce solution for prototype reduction in big data classification. Neurocomputing (in press)
30.
Zurück zum Zitat Triguero I, Garcia S, Herrera F (2011) Differential evolution for optimizing the positioning of prototypes in nearest neighbor classification. Pattern Recogn. 44:901–916CrossRef Triguero I, Garcia S, Herrera F (2011) Differential evolution for optimizing the positioning of prototypes in nearest neighbor classification. Pattern Recogn. 44:901–916CrossRef
31.
Zurück zum Zitat Wu X, Kumar V, Quinlan JR, Ghosh J, Yang Q, Motoda H, McLachlan GJ, Ng A, Liu B, Yu Ps, Zhou ZH, Steinbach M, Hand DJ, Steinberg D (2007) Top 10 algorithms in data mining. Knowl Inf Syst 14(1):1–37 Wu X, Kumar V, Quinlan JR, Ghosh J, Yang Q, Motoda H, McLachlan GJ, Ng A, Liu B, Yu Ps, Zhou ZH, Steinbach M, Hand DJ, Steinberg D (2007) Top 10 algorithms in data mining. Knowl Inf Syst 14(1):1–37
32.
Zurück zum Zitat Xia H, Zhuang J, Yu D (2013) Novel soft subspace clustering with multi-objective evolutionary approach for high-dimensional data. Pattern Recogn. 46:2562–2575CrossRefMATH Xia H, Zhuang J, Yu D (2013) Novel soft subspace clustering with multi-objective evolutionary approach for high-dimensional data. Pattern Recogn. 46:2562–2575CrossRefMATH
Metadaten
Titel
MOPG: a multi-objective evolutionary algorithm for prototype generation
verfasst von
Hugo Jair Escalante
Maribel Marin-Castro
Alicia Morales-Reyes
Mario Graff
Alejandro Rosales-Pérez
Manuel Montes-y-Gómez
Carlos A. Reyes
Jesus A. Gonzalez
Publikationsdatum
06.02.2015
Verlag
Springer London
Erschienen in
Pattern Analysis and Applications / Ausgabe 1/2017
Print ISSN: 1433-7541
Elektronische ISSN: 1433-755X
DOI
https://doi.org/10.1007/s10044-015-0454-6

Weitere Artikel der Ausgabe 1/2017

Pattern Analysis and Applications 1/2017 Zur Ausgabe