Generación de prototipos para la clasificación de patrones usando programación genética

Abstract

k-Nearest Neighbor (kNN) is one of the most popular and successful pattern classification techniques. Despite its high classification accuracy, it is known that kNN has some disadvantages; most notably, the requirement to store all the instances in the training set, T . On the other hand, when a new pattern must be classified by kNN, it is compared to all of the instances in T . Obviously, this is a crucial aspect when one has a large set T and wants to classify many objects. In this work, it proposes a Genetic Programming (GP) approach to the problem of Prototype Generation (PG) for NN based classification. The idea of PG is to represent all the elements in T with a number of generated instances, with the goal of reducing the storage requirements and the computational cost inherent in NN classifiers. To generate artificial instances, an iterative GP technique is proposed, which uses a non-linear combination of instances available in T . Experiments are reported in a suite of benchmark for evaluation of PG methods. Experimental results show that the proposed approach is very competitive with state of the art techniques, obtaining the best accuracy reported so far for this benchmark. The proposed method is very competitive in terms of reduction performance as well.

La regla de k-vecinos más cercanos (kNN, k-Nearest Neighbors) es una de las técnicas de clasificación de patrones m as populares y exitosas. A pesar de su alta precisión de clasificación, se sabe que kNN tiene algunas desventajas; principalmente, los requerimientos para almacenar todas las instancias en el conjunto de entrenamiento, T . Por otro lado, cuando un nuevo patrón debe ser clasificado por kNN, se compara con todas las instancias en T . Evidentemente, este es un aspecto crucial cuando se tiene un conjunto T grande y se quiere clasificar a muchos objetos. En este trabajo, se propone un enfoque de Programación Genética (GP, Genetic Programming) al problema de la Generación de Prototipos (PG, Prototype Generation) para una clasificación basada en la regla NN. La idea de PG es representar a todos los elementos en T con un número de instancias generadas, con el objetivo de reducir los requerimientos de almacenamiento y el coste computacional inherente en clasificadores NN. Para generar las instancias artificiales, se propone una técnica de GP iterativo, la cual usa una combinación no lineal de las muestras disponibles en T . Los experimentos son presentados en un conjunto de bases de datos de referencia para la evaluación de métodos PG. Los resultados experimentales muestran que el enfoque propuesto es muy competitivo con técnicas del estado del arte, obteniendo la mejor precisión reportada hasta el momento para este conjunto de bases. También el método propuesto es muy competitivo en términos de rendimiento de reducción.