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

Una de las tecnicas de clasificacion mas utilizadas en reconocimiento de formas es la regla de clasificacion del vecino mas cercano, que consiste en, a partir de un conjunto de objetos etiquetados, asignar a un objeto desconocido la etiqueta de su vecino mas cercano en el conjunto, segun alguna medida de distancia. En la actualidad existen muchos algoritmos para encontrar de forma eficiente el vecino mas cercanos y, dado que normalmente se obtienen mejores resultados de clasificacion utilizando los K vecinos mas cercanos (con K mayor 1), estos algoritmos se pueden extender para encontrar los K vecinos mas cercanos, aunque el tiempo de clasificacion aumenta segun el valor de K. En esta tesis se presenta una nueva regla de clasificacion que obtiene resultados similares a los que se obtienen con los K vecinos mas cercanos sin que el tiempo aumente con el valor de K. En muchas tareas de clasificacion la busqueda exacta del vecino mas cercano es demasiado costosa y se suele optar por utilizar lo que se denomina el vecino aproximado mas cercano para clasificar la muestra. En los trabajos previos en esta cuestion se asume que los objetos son vectores, y en esta tesis se presenta una extension 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 calculo de la distancia entre objetos suele ser muy costoso y por tanto la busqueda aproximada tiene una gran utilidad.