algoritmo de k vecinos más cercanos

En estadística y aprendizaje automático , el algoritmo de k vecinos más cercanos ( k -NN ) es un método de aprendizaje supervisado no paramétrico que asigna ponderación únicamente a los k vecinos más cercanos de una entidad al tomar una decisión sobre ella. Se utiliza tanto en clasificación, donde a un nuevo ejemplo se le asigna una etiqueta basada en las etiquetas de sus k ejemplos de entrenamiento más cercanos, como en regresión, donde la predicción se calcula a partir de los valores de esos vecinos. ^{[ 1 ] [ 2 ]} Su uso más frecuente es en clasificación , como el clasificador k -NN , cuya salida es una pertenencia a una clase decidida por votación mayoritaria de sus vecinos. k , un número entero, suele ser pequeño; si k = 1, el objeto simplemente se asigna a la clase de ese único vecino más cercano. Fue desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951, ^{[ 1 ]} y posteriormente ampliado por Thomas Cover . ^{[ 2 ]}  

El algoritmo k -NN también se puede generalizar para regresión . En la regresión k -NN , también conocida como suavizado del vecino más cercano , la salida es el valor de la propiedad del objeto. Este valor es el promedio de los valores de los k vecinos más cercanos. Si k  = 1, la salida se asigna simplemente al valor de ese único vecino más cercano, lo que se conoce como interpolación del vecino más cercano .

Tanto para la clasificación como para la regresión, una técnica útil consiste en asignar ponderaciones a las contribuciones de los vecinos, de modo que los vecinos más cercanos contribuyan más al promedio que los más distantes. Por ejemplo, un esquema de ponderación común consiste en asignar a cada vecino una ponderación de 1/ d , donde d es la distancia al vecino. ^{[ 3 ]}

La entrada consiste en los k ejemplos de entrenamiento más cercanos de un conjunto de datos . Los vecinos se toman de un conjunto de objetos para los que se conoce la clase (para la clasificación k -NN) o el valor de la propiedad del objeto (para la regresión k -NN). Esto puede considerarse como el conjunto de entrenamiento para el algoritmo, aunque no se requiere ningún paso de entrenamiento explícito.

Una peculiaridad (a veces incluso una desventaja) del algoritmo k -NN es su sensibilidad a la estructura local de los datos. En la clasificación k -NN, la función solo se aproxima localmente y todo el cálculo se pospone hasta la evaluación de la función. Dado que este algoritmo se basa en la distancia, si las características representan diferentes unidades físicas o se presentan en escalas muy diferentes, la normalización de los datos de entrenamiento por características puede mejorar considerablemente su precisión. ^{[ 4 ]}

Supongamos que tenemos pares${\ Displaystyle (X_ {1}, Y_ {1}), (X_ {2}, Y_ {2}), \ dots, (X_ {n}, Y_ {n})}$tomando valores en${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$, donde Y es la etiqueta de clase de X , de modo que${\displaystyle X|Y=r\sim P_{r}}$para${\displaystyle r=1,2}$(y distribuciones de probabilidad)${\displaystyle P_{r}}$). Dado algún estándar${\displaystyle \|\cdot \|}$en${\displaystyle \mathbb {R} ^{d}}$y un punto${\displaystyle x\in \mathbb {R} ^{d}}$, dejar${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$ser una reordenación de los datos de entrenamiento de tal manera que${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$.

Los ejemplos de entrenamiento son vectores en un espacio de características multidimensional, cada uno con una etiqueta de clase. La fase de entrenamiento del algoritmo consiste únicamente en almacenar los vectores de características y las etiquetas de clase de las muestras de entrenamiento.

En la fase de clasificación, k es una constante definida por el usuario, y un vector sin etiquetar (un punto de consulta o de prueba) se clasifica asignándole la etiqueta que sea más frecuente entre las k muestras de entrenamiento más cercanas a ese punto de consulta.

Una métrica de distancia comúnmente utilizada para variables continuas es la distancia euclidiana . Para variables discretas, como en la clasificación de texto, se puede utilizar otra métrica, como la métrica de superposición (o distancia de Hamming ). En el contexto de datos de microarrays de expresión génica , por ejemplo, se ha empleado k -NN con coeficientes de correlación, como Pearson y Spearman, como métrica. ^{[ 5 ]} A menudo, la precisión de clasificación de k -NN puede mejorarse significativamente si la métrica de distancia se aprende con algoritmos especializados como el vecino más cercano de margen amplio o el análisis de componentes de vecindario .

Una desventaja de la clasificación básica de "votación mayoritaria" ocurre cuando la distribución de clases está sesgada. Es decir, los ejemplos de una clase más frecuente tienden a dominar la predicción del nuevo ejemplo, porque tienden a ser comunes entre los k vecinos más cercanos debido a su gran número. ^{[ 7 ]} Una forma de superar este problema es ponderar la clasificación, teniendo en cuenta la distancia del punto de prueba a cada uno de sus k vecinos más cercanos. La clase (o valor, en problemas de regresión) de cada uno de los k puntos más cercanos se multiplica por un peso proporcional al inverso de la distancia de ese punto al punto de prueba. Otra forma de superar el sesgo es mediante la abstracción en la representación de datos. Por ejemplo, en un mapa autoorganizado (SOM), cada nodo es un representante (un centro) de un grupo de puntos similares, independientemente de su densidad en los datos de entrenamiento originales. Luego se puede aplicar k -NN al SOM.

La mejor elección de k depende de los datos; generalmente, valores mayores de k reducen el efecto del ruido en la clasificación ^{[ 8 ]} , pero hacen que los límites entre clases sean menos definidos. Se puede seleccionar un buen valor de k mediante diversas técnicas heurísticas (véase la optimización de hiperparámetros ). El caso especial en el que se predice que la clase es la de la muestra de entrenamiento más cercana (es decir, cuando k = 1) se denomina algoritmo del vecino más cercano.

La precisión del algoritmo k -NN puede verse gravemente afectada por la presencia de características ruidosas o irrelevantes, o si las escalas de las características no son coherentes con su importancia. Se han realizado numerosos esfuerzos de investigación para seleccionar o escalar características con el fin de mejorar la clasificación. Un enfoque particularmente popular es el uso de algoritmos evolutivos para optimizar el escalado de características. ^{[ 9 ]} Otro enfoque popular consiste en escalar las características mediante la información mutua de los datos de entrenamiento con las clases de entrenamiento.

En problemas de clasificación binaria (dos clases), es útil elegir k como un número impar, ya que esto evita empates. Una forma popular de elegir el valor óptimo empírico de k en este contexto es mediante el método bootstrap. ^{[ 10 ]}

El clasificador de tipo vecino más intuitivo es el clasificador de vecino más cercano que asigna un punto x a la clase de su vecino más cercano en el espacio de características, es decir${\displaystyle C_{n}^{1nn}(x)=Y_{(1)}}$.

A medida que el tamaño del conjunto de datos de entrenamiento tiende al infinito, el clasificador de un vecino más cercano garantiza una tasa de error no peor que el doble de la tasa de error de Bayes (la tasa de error mínima alcanzable dada la distribución de los datos).

El clasificador de k vecinos más cercanos puede verse como la asignación de un peso a los k vecinos más cercanos.${\displaystyle 1/k}$y todos los demás con peso 0. Esto se puede generalizar a clasificadores de vecinos más cercanos ponderados. Es decir, donde al i -ésimo vecino más cercano se le asigna un peso${\displaystyle w_{ni}}$, con${\textstyle \sum _ {i=1}^{n}w_ {ni}=1}$. Un resultado análogo sobre la consistencia fuerte de los clasificadores de vecinos más cercanos ponderados también es válido. ^{[ 11 ]}

Dejar${\displaystyle C_{n}^{wnn}}$denota el clasificador más cercano ponderado con pesos${\displaystyle \{w_{ni}\}_{i=1}^{n}}$Sujeto a condiciones de regularidad, que en teoría asintótica son variables condicionales que requieren supuestos para diferenciar entre parámetros con algún criterio. En las distribuciones de clase, el riesgo excesivo tiene la siguiente expansión asintótica ^{[ 12 ].}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$$ para constantes${\displaystyle B_{1}}$y${\displaystyle B_{2}}$dónde${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$y${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$.

Esquema de ponderación óptimo${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$, que equilibra los dos términos en la pantalla anterior, se da de la siguiente manera: conjunto${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$, $${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$$para${\displaystyle i=1,2,\dots ,k^{*}}$y $${\displaystyle w_{ni}^{*}=0}$$para${\displaystyle i=k^{*}+1,\dots ,n}$.

Con ponderaciones óptimas, el término dominante en la expansión asintótica del riesgo excesivo es${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$Se obtienen resultados similares al utilizar un clasificador de vecinos más cercanos con agregación de datos .

Una variación del enfoque del vecino más cercano utiliza los k vecinos más lejanos en lugar de los más cercanos. En este contexto, los vecinos se seleccionan en función de la máxima disimilitud en lugar de la similitud. Este enfoque se ha propuesto en sistemas de recomendación como un modelo de "vecindario invertido", donde se identifican los usuarios más disímiles y sus preferencias se utilizan de forma inversa para generar recomendaciones. ^{[ 13 ]} El objetivo suele ser aumentar la diversidad o la novedad en los elementos recomendados, ya que los métodos tradicionales del vecino más cercano pueden favorecer los elementos populares u obvios. Las evaluaciones empíricas han encontrado que los enfoques del vecino más lejano generalmente logran una precisión predictiva menor que los métodos estándar del k vecino más cercano, aunque la utilidad percibida por el usuario puede ser similar o mayor en algunos casos.

k -NN es un caso especial de un estimador de "globo" de densidad de núcleo de ancho de banda variable con un núcleo uniforme . ^{[ 14 ] [ 15 ]}

La versión ingenua del algoritmo es fácil de implementar calculando las distancias desde el ejemplo de prueba a todos los ejemplos almacenados, pero requiere mucha capacidad de cálculo para conjuntos de entrenamiento grandes. El uso de un algoritmo de búsqueda del vecino más cercano aproximado hace que k- NN sea computacionalmente viable incluso para conjuntos de datos grandes. A lo largo de los años se han propuesto muchos algoritmos de búsqueda del vecino más cercano; estos generalmente buscan reducir el número de evaluaciones de distancia que se realizan.

k- NN presenta resultados de consistencia sólida . A medida que la cantidad de datos tiende a infinito, el algoritmo k- NN de dos clases garantiza una tasa de error no peor que el doble de la tasa de error de Bayes (la tasa de error mínima alcanzable dada la distribución de los datos). ^{[ 2 ]} Es posible realizar diversas mejoras en la velocidad de k -NN mediante el uso de grafos de proximidad. ^{[ 16 ]}

Para la clasificación k -NN multiclase , Cover y Hart (1967) demuestran una tasa de error de límite superior de $${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$ dónde${\displaystyle R^{*}}$es la tasa de error de Bayes (que es la tasa de error mínima posible),${\displaystyle R_{kNN}}$es la tasa de error asintótica k- NN, y M es el número de clases en el problema. Esta cota es ajustada en el sentido de que tanto la cota inferior como la superior son alcanzables por alguna distribución. ^{[ 17 ]} Para${\displaystyle M=2}$y como la tasa de error bayesiana${\displaystyle R^{*}}$Cuando se aproxima a cero, este límite se reduce a "no más del doble de la tasa de error bayesiana".

Existen muchos resultados sobre la tasa de error de los clasificadores de k vecinos más cercanos. ^{[ 18 ]} El clasificador de k vecinos más cercanos es fuertemente (es decir, para cualquier distribución conjunta en${\displaystyle (X,Y)}$) consistente proporcionado${\displaystyle k:=k_{n}}$diverge y${\displaystyle k_{n}/n}$converge a cero cuando${\displaystyle n\to \infty }$.

Dejar${\displaystyle C_{n}^{knn}}$denotamos el clasificador de k vecinos más cercanos basado en un conjunto de entrenamiento de tamaño n . Bajo ciertas condiciones de regularidad, el riesgo excesivo produce la siguiente expansión asintótica ^{[ 12 ].}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},}$$ para algunas constantes${\displaystyle B_{1}}$y${\displaystyle B_{2}}$.

La elección${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$ofrece una compensación entre los dos términos en la pantalla anterior, para la cual el${\displaystyle k^{*}}$El error del vecino más cercano converge al error de Bayes a la tasa óptima ( minimax ).${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$.

El rendimiento de la clasificación de k vecinos más cercanos a menudo puede mejorarse significativamente mediante el aprendizaje métrico ( supervisado ). Los algoritmos más populares son el análisis de componentes de vecindario y el vecino más cercano de margen amplio . Los algoritmos de aprendizaje métrico supervisado utilizan la información de las etiquetas para aprender una nueva métrica o pseudométrica .

Cuando los datos de entrada de un algoritmo son demasiado grandes para ser procesados ​​y se sospecha que son redundantes (por ejemplo, la misma medida en pies y metros), se transforman en un conjunto de características de representación reducida (también llamado vector de características). Esta transformación se denomina extracción de características . Si las características extraídas se eligen cuidadosamente, se espera que el conjunto de características extraiga la información relevante de los datos de entrada para realizar la tarea deseada utilizando esta representación reducida en lugar de la entrada completa. La extracción de características se realiza sobre los datos sin procesar antes de aplicar el algoritmo k -NN a los datos transformados en el espacio de características .

Un ejemplo de una típica canalización de cálculo de visión artificial para el reconocimiento facial utilizando k -NN que incluye pasos de preprocesamiento de extracción de características y reducción de dimensionalidad (generalmente implementados con OpenCV ):

1. Detección facial Haar
2. Análisis de seguimiento del cambio medio
3. Proyección de PCA o LDA de Fisher en el espacio de características, seguida de clasificación k -NN.

Para datos de alta dimensión (por ejemplo, con más de 10 dimensiones), la reducción de dimensión se suele realizar antes de aplicar el algoritmo k -NN para evitar los efectos de la maldición de la dimensionalidad . ^{[ 19 ]}

La maldición de la dimensionalidad en el contexto k -NN básicamente significa que la distancia euclidiana no es útil en dimensiones altas porque todos los vectores son casi equidistantes del vector de consulta de búsqueda (imagínese múltiples puntos que se encuentran más o menos en un círculo con el punto de consulta en el centro; la distancia desde la consulta a todos los puntos de datos en el espacio de búsqueda es casi la misma).

La extracción de características y la reducción de dimensionalidad se pueden combinar en un solo paso utilizando técnicas de análisis de componentes principales (PCA), análisis discriminante lineal (LDA) o análisis de correlación canónica (CCA) como paso de preprocesamiento, seguido de la agrupación mediante k -NN en vectores de características en el espacio de dimensión reducida. Este proceso también se denomina incrustación de baja dimensión . ^{[ 20 ]}

Para conjuntos de datos de dimensiones muy altas (por ejemplo, al realizar una búsqueda de similitud en transmisiones de video en vivo, datos de ADN o series temporales de alta dimensión ), ejecutar una búsqueda rápida aproximada de k -NN utilizando hash sensible a la localidad , "proyecciones aleatorias" ^{[ 21 ]} , "bocetos" ^{[ 22 ]} u otras técnicas de búsqueda de similitud de alta dimensión de la caja de herramientas VLDB podría ser la única opción factible.

Las reglas del vecino más cercano calculan implícitamente el límite de decisión . También es posible calcular el límite de decisión de forma explícita y eficiente, de modo que la complejidad computacional sea una función de la complejidad del límite. ^{[ 23 ]}

La reducción de datos es uno de los problemas más importantes al trabajar con conjuntos de datos enormes. Por lo general, solo se necesitan algunos de los puntos de datos para una clasificación precisa. Estos datos se denominan prototipos y se pueden encontrar de la siguiente manera:

1. Seleccione los valores atípicos de la clase , es decir, los datos de entrenamiento que son clasificados incorrectamente por k -NN (para un k dado ).
2. Separe el resto de los datos en dos conjuntos: (i) los prototipos que se utilizan para las decisiones de clasificación y (ii) los puntos absorbidos que pueden ser clasificados correctamente por k -NN utilizando prototipos. Los puntos absorbidos pueden eliminarse del conjunto de entrenamiento.

Vecino más cercano condensado para la reducción de datos

El vecino más cercano condensado (CNN, el algoritmo de Hart ) es un algoritmo diseñado para reducir el conjunto de datos para la clasificación k -NN. ^{[ 24 ]} Selecciona el conjunto de prototipos U de los datos de entrenamiento, de modo que 1NN con U puede clasificar los ejemplos casi con la misma precisión que 1NN con el conjunto de datos completo.

Dado un conjunto de entrenamiento X , la CNN funciona de forma iterativa:

1. Escanee todos los elementos de X , buscando un elemento x cuyo prototipo más cercano de U tenga una etiqueta diferente a x .
2. Retira x de X y añádelo a U.
3. Repita el escaneo hasta que no se agreguen más prototipos a U.

Utilice U en lugar de X para la clasificación. Los ejemplos que no son prototipos se denominan puntos "absorbidos".

Es eficiente escanear los ejemplos de entrenamiento en orden decreciente de relación de borde. ^{[ 25 ]} La relación de borde de un ejemplo de entrenamiento x se define como

a ( x ) = ‖ x' -y ‖ / ‖ xy ‖ ⁠

donde ‖ xy ‖ es la distancia al ejemplo más cercano y que tiene un color diferente al de x , y ‖ x'-y ‖ es la distancia de y a su ejemplo más cercano x' con la misma etiqueta que x .

La razón de borde está en el intervalo [0,1] porque ‖ x'-y ‖ nunca excede ‖ xy ‖ . Este ordenamiento da preferencia a los bordes de las clases para su inclusión en el conjunto de prototipos U . Un punto con una etiqueta diferente a x se llama externo a x . El cálculo de la razón de borde se ilustra en la figura de la derecha. Los puntos de datos están etiquetados con colores: el punto inicial es x y su etiqueta es rojo. Los puntos externos son azul y verde. El punto externo más cercano a x es y . El punto rojo más cercano a y es x' . La razón de borde a ( x ) = ‖ x'-y ‖ / ‖ xy ‖ es el atributo del punto inicial x .

A continuación se muestra una ilustración de CNN en una serie de figuras. Hay tres clases (rojo, verde y azul). Fig. 1: inicialmente hay 60 puntos en cada clase. Fig. 2 muestra el mapa de clasificación 1NN: cada píxel es clasificado por 1NN usando todos los datos. Fig. 3 muestra el mapa de clasificación 5NN. Las áreas blancas corresponden a las regiones no clasificadas, donde la votación 5NN está empatada (por ejemplo, si hay dos puntos verdes, dos rojos y uno azul entre los 5 vecinos más cercanos). Fig. 4 muestra el conjunto de datos reducido. Las cruces son los valores atípicos de clase seleccionados por la regla (3,2)NN (los tres vecinos más cercanos de estas instancias pertenecen a otras clases); los cuadrados son los prototipos, y los círculos vacíos son los puntos absorbidos. La esquina inferior izquierda muestra el número de valores atípicos de clase, prototipos y puntos absorbidos para las tres clases. El número de prototipos varía del 15% al ​​20% para las diferentes clases en este ejemplo. La figura 5 muestra que el mapa de clasificación 1NN con los prototipos es muy similar al que se obtuvo con el conjunto de datos inicial. Las figuras se generaron utilizando el applet de Mirkes. ^{[ 25 ]}

• Reducción de modelos CNN para clasificadores k-NN
• 
  Figura 1. El conjunto de datos.
• 
  Figura 2. Mapa de clasificación 1NN.
• 
  Figura 3. Mapa de clasificación 5NN.
• 
  Figura 4. El conjunto de datos reducido mediante CNN.
• 
  Figura 5. Mapa de clasificación 1NN basado en los prototipos extraídos por la CNN.

En la regresión k -NN, también conocida como suavizado k -NN, el algoritmo k -NN se utiliza para estimar variables continuas . Uno de estos algoritmos utiliza un promedio ponderado de los k vecinos más cercanos, ponderado por el inverso de su distancia. Este algoritmo funciona de la siguiente manera:

1. Calcula la distancia euclidiana o de Mahalanobis desde el ejemplo de consulta hasta los ejemplos etiquetados.
2. Ordena los ejemplos etiquetados por distancia creciente.
3. Encuentra heurísticamente un número óptimo k de vecinos más cercanos, basado en el RMSE . Esto se hace mediante validación cruzada.
4. Calcula un promedio ponderado por distancia inversa con los k vecinos multivariados más cercanos.

La distancia al k -ésimo vecino más cercano también puede considerarse una estimación de la densidad local y, por lo tanto, es una puntuación de valores atípicos popular en la detección de anomalías . Cuanto mayor sea la distancia al k -NN, menor será la densidad local y mayor será la probabilidad de que el punto de consulta sea un valor atípico. ^{[ 26 ]} Aunque bastante simple, este modelo de valores atípicos, junto con otro método clásico de minería de datos , el factor de valores atípicos locales , funciona bastante bien incluso en comparación con enfoques más recientes y complejos, según un análisis experimental a gran escala. ^{[ 27 ]}

Una matriz de confusión o "matriz de coincidencia" se utiliza a menudo como herramienta para validar la precisión de la clasificación k -NN. También se pueden aplicar métodos estadísticos más robustos, como la prueba de razón de verosimilitud .

• Clasificador de centroide más cercano
• Problema del par de puntos más cercanos
• Grafo del vecino más cercano
• Categorización de objetos basada en la segmentación

• Dasarathy, Belur V. , ed. (1991). Normas del vecino más cercano (NN): Técnicas de clasificación de patrones NN . IEEE Computer Society Press. ISBN 978-0818689307.
• Shakhnarovich, Gregory; Darrell, Trevor; Indyk, Piotr, eds. (2005). Métodos del vecino más cercano en el aprendizaje y la visión . MIT Press . ISBN 978-0262195478.