KNN

k-Nearest Neighbor

1. Introducción

El algoritmo k-NN es un método de clasificación no paramétrico que es muy simple y a la vez efectivo [8], el algoritmo es del tipo perezoso debido a que requiere una petición para comenzar a utilizar la información almacenada para poder tomar una decisión. El algoritmo posee dos etapas, la primera etapa es la del entrenamiento donde se requiere informacióncorrectamente clasificada y lo más cercano posible a la realidad debido a que si se tiene información errónea y muy lejana entre cada clase a clasificar, se puede obtener resultados inesperados y muy lejanos a la predicción que se requiere. La segunda etapa es la petición de clasificación de un nuevo elemento a partir de lo almacenado en la primera etapa, procesada la petición y realizados loscálculos el algoritmo devuelve una predicción de la posible pertenencia de ese nuevo elemento a una clase.
Para hacer las clasificaciones, el algoritmo se basa en la idea de votaciones a partir de proximidades, es decir, que a partir del parámetro “k” que se le indique elige los “k” elementos más próximos al dato ingresado. Se realiza un conteo de cada tipo de elemento que lo rodea para finalmenteasignarle el valor del mayor número de elementos de una clase. En esencia este es el funcionamiento normal del algoritmo, pero una variación que se utiliza y que es más fiable que el algoritmo concebido inicialmente, es que a partir de los “k” vecinos elegidos se le asigna un peso a cada uno de ellos que varía de acuerdo a la distancia entre el nuevo elemento y cada uno de los “k” vecinos elegidos,para datos discretos se utiliza la distancia de Hamming y para datos continuos se utiliza la distancia euclidiana.
Si bien este algoritmo simple y muy fácil de implementar es eficaz para resolver problemas estadísticos que requieren predicción por asociamiento, tiene algunos problemas muy críticos como por ejemplo, el costo elevado para poder clasificar nuevos elementos. Esto se debe a que elalgoritmo requiere comparar toda la información almacenada en la etapa de entrenamiento con el nuevo elemento a clasificar, es decir, mientras más información se tiene almacenada, mayor será el esfuerzo en procesamiento para clasificar un nuevo elemento. Otro de los problemas que posee el presente algoritmo es que no existe un valor de “k” teórico, además se debe tener en cuenta que si el valor de“k” es demasiado pequeño o demasiado grande, cabe la posibilidad de realizar una predicción errónea. De acuerdo a lo descrito en el artículo científico “Choice of neighbor order in Nearest-Neighbor Classification” [5] se puede utilizar dos modelos para estimar un valor adecuado para “k”, estos modelos son el modelo de Binomial y el modelo Poisson. El modelo Binomial básicamente se encarga derealizar “n” ensayos y realizar un conteo de los casos exitosos y el modelo de Poisson obtiene el valor a partir de la frecuencia media de los casos exitosos de los “n” ensayos.
El algoritmo k-NN es utilizado en la minería de datos debido a que se encuentra dentro de los 10 mejores algoritmos para este tema en específico [4], escalamiento de gráficos evitando la menor pérdida de píxeles, utilizado parareconocimiento de rostros, entre otras aplicaciones.



2. Sustentación teórica

El algoritmo propuesto por Fix y Hodges en 1951 en un reporte no publicado para la fuerza aérea de los US de Norteamérica para clasificar patrones cuando no existe conocimiento previo de la información almacenada es uno de los métodos más utilizados para realizar predicciones y clasificaciones. El algoritmo fueconcebido debido a la necesidad de clasificar información extensa y difícil de clasificar para determinar una posible respuesta ante la evaluación de un nuevo dato. Para que el algoritmo se consolide le tomó cerca de 16 años a partir de que establecieron todas las reglas y propiedades necesarias para que el algoritmo funcione correctamente.
El algoritmo se basa en una teoría de proximidad de los...