Clasificadores eficaces basados en algoritmos rápidos de búsqueda del vecino más cercano

Abstract

Una de las técnicas de clasificación más utilizadas en reconocimiento de formas es la regla de clasificación del vecino más cercano, que consiste en, a partir de un conjunto de objetos etiquetados, asignar a un objeto desconocido la etiqueta de su vecino más cercano en el conjunto, según alguna medida de distancia. En la actualidad existen muchos algoritmos para encontrar de forma eficiente el vecino más cercanos y, dado que normalmente se obtienen mejores resultados de clasificación utilizando los K vecinos más cercanos (con K mayor 1), estos algoritmos se pueden extender para encontrar los K vecinos más cercanos, aunque el tiempo de clasificación aumenta según el valor de K. En esta tesis se presenta una nueva regla de clasificación que obtiene resultados similares a los que se obtienen con los K vecinos más cercanos sin que el tiempo aumente con el valor de K. En muchas tareas de clasificación la búsqueda exacta del vecino más cercano es demasiado costosa y se suele optar por utilizar lo que se denomina el vecino aproximado más cercano para clasificar la muestra. En los trabajos previos en esta cuestión se asume que los objetos son vectores, y en esta tesis se presenta una extensión de estos trabajos en la que no se requiere que el objeto se represente como un vector, algo frecuente en muchas tareas de reconocimiento de formas, y en dichos casos el cálculo de la distancia entre objetos suele ser muy costoso y por tanto la búsqueda aproximada tiene una gran utilidad.