Aceleración del algoritmo de clasificación K Vecinos más Cercanos a través de la compresión de set de entrenamiento

Abstract

El algoritmo de clasificación K vecinos más cercanos es posiblemente uno de los más antiguos y simples métodos de clasificación supervisada. Sin embargo, tiene un costo computacional muy alto ya que debe determinar la distancia Euclidiana entre la muestra a clasificar y todo el conjunto de entrenamiento. Existen tres técnicas para acelerar este algoritmo: reducción de cómputos, reducción del número de dimensión del conjunto de prueba y de entrenamiento y compresión del conjunto de entrenamiento. La última técnica presenta como ventaja un bajo uso de memoria, además de poder ser utilizado en grandes conjuntos de entrenamientos con pocas dimensiones. Se han realizado varios trabajos con el fin de realizar la compresión del conjunto de entrenamiento, unos proponen la selección de las muestras que mejor definan el conjunto de entrenamiento inicial eliminando así la redundancia, otros proponen comprimir los datos a algunos grupos centrales. En este trabajo se utiliza un enfoque estocástico de la compresión del conjunto de entrenamiento, para ello se desarrollaron los algoritmos necesarios y para evaluar su rendimiento, se probaron en cuatro bases de datos diferentes, tres de imágenes y una de audio. La técnica implementada permite obtener, dado un conjunto inicial de datos para el entrenamiento, un conjunto de entrenamiento mucho más pequeño de vectores optimizados. La compresión estocástica se basa en el método matemático del gradiente descendente, este método tiene propiedades atractivas como poder seleccionar la relación de compresión, permitiendo un conjunto de entrenamiento mucho más pequeño que aumenta la velocidad de clasificación drásticamente. De los resultados de las simulaciones realizadas con las bases de datos de prueba se obtuvo, en la mayoría de los casos, un error que está por debajo 5 % de muestras mal clasificadas, incluso para relaciones de compresión tan bajas como del 1 %. Adicionalmente, la combinación de este algoritmo junto con otros como Large Margin Nearest Neighbor para la reducción de dimensiones acelera al algoritmo por encima de los valores esperados, demostrando que el método es compatible con métodos ya diseñados.