Algoritmo de K vecinos más cercanos

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Método de clasificación no paramétrica

En estadística, el algoritmo k-vecinos más cercanos (k-NN) es un algoritmo no paramétrico. Método de aprendizaje supervisado desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951, y posteriormente ampliado por Thomas Cover. Se utiliza para clasificación y regresión. En ambos casos, la entrada consta de los k ejemplos de entrenamiento más cercanos en un conjunto de datos. El resultado depende de si k-NN se utiliza para clasificación o regresión:

In k-NN category, la salida es una membresía de clase. Un objeto es clasificado por un voto plural de sus vecinos, con el objeto que se asigna a la clase más común entre sus vecinos k vecinos más cercanos (k es un entero positivo, típicamente pequeño). Si k = 1, entonces el objeto se asigna simplemente a la clase de ese único vecino más cercano.
In k-NN regression, la salida es el valor de propiedad para el objeto. Este valor es el promedio de los valores k vecinos más cercanos. Si k = 1, entonces la salida se asigna simplemente al valor de ese único vecino más cercano.

k-NN es un tipo de clasificación en la que la función solo se aproxima localmente y todos los cálculos se difieren hasta la evaluación de la función. Dado que este algoritmo se basa en la distancia para la clasificación, si las características representan diferentes unidades físicas o vienen en escalas muy diferentes, la normalización de los datos de entrenamiento puede mejorar drásticamente su precisión.

Tanto para la clasificación como para la regresión, una técnica útil puede ser 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 dar a cada vecino un peso de 1/d, donde d es la distancia al vecino.

Los vecinos se toman de un conjunto de objetos para los cuales la clase (para la clasificación k-NN) o el valor de la propiedad del objeto (para la regresión k-NN) es conocido. Esto puede considerarse como el conjunto de entrenamiento para el algoritmo, aunque no se requiere ningún paso de entrenamiento explícito.

Una peculiaridad del algoritmo k-NN es que es sensible a la estructura local de los datos.

Configuración estadística

Supongamos que tenemos pares ${displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),dots(X_{n},Y_{n})}$ tomar valores en ${displaystyle mathbb {R} ^{d}times {1,2}}$ , donde $Y$ es la etiqueta de clase $X$ Así que ${displaystyle X|Y=rsim P_{r}}$ para ${displaystyle r=1,2}$ (y distribuciones de probabilidad ${displaystyle P_{r}}$ ). Dada alguna norma ${displaystyle |cdot |}$ on ${displaystyle mathbb {R} ^{d}}$ y un punto ${displaystyle xin mathbb {R} ^{d}}$ , vamos ${displaystyle (X_{(1)},Y_{(1)}),dots(X_{(n)},Y_{(n)})}$ ser una reordenación de los datos de capacitación de tal manera que ${displaystyle |X_{(1)}-x|leq dots leq |X_{(n)}-x|}$ .

Algoritmo

Ejemplo k- Clasificación NN. La muestra de prueba (punto verde) debe ser clasificada ya sea a cuadrados azules o a triángulos rojos. Si *k = 3* (círculo de línea sólida) se asigna a los triángulos rojos porque hay 2 triángulos y sólo 1 cuadrado dentro del círculo interior. Si *k = 5* (círculo de línea roto) se asigna a los cuadrados azules (3 cuadrados vs. 2 triángulos dentro del círculo exterior).

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 (una consulta o punto de prueba) se clasifica asignando la etiqueta que es más frecuente entre los 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 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 los datos de microarrays de expresión genética, por ejemplo, se ha empleado k-NN con coeficientes de correlación, como los de Pearson y Spearman, como métrica. A menudo, la precisión de la clasificación de k-NN se puede mejorar significativamente si la métrica de distancia se aprende con algoritmos especializados como el análisis de componentes de vecindario o vecino más cercano de margen grande.

Un inconveniente del sistema básico de "voto mayoritario" La clasificación 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. Una forma de superar este problema es ponderar la clasificación, teniendo en cuenta la distancia desde el 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 a la inversa de la distancia desde ese punto hasta el 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.

Selección de parámetros

La mejor elección de k depende de los datos; generalmente, valores mayores de k reducen el efecto del ruido en la clasificación, pero hacen que los límites entre clases sean menos distintos. Se puede seleccionar una buena k mediante varias técnicas heurísticas (consulte optimización de hiperparámetros). El caso especial en el que se predice que la clase será la clase de la muestra de entrenamiento más cercana (es decir, cuando k = 1) se denomina algoritmo vecino más cercano.

La precisión del algoritmo k-NN puede verse gravemente degradada por la presencia de características ruidosas o irrelevantes, o si las escalas de características no son consistentes con su importancia. Se han realizado muchos esfuerzos de investigación para seleccionar o escalar características para mejorar la clasificación. Un enfoque particularmente popular es el uso de algoritmos evolutivos para optimizar el escalado de funciones. Otro enfoque popular es escalar 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 votos empatados. Una forma popular de elegir el k empíricamente óptimo en esta configuración es mediante el método bootstrap.

El clasificador de 1 vecino más cercano

El clasificador más intuitivo de tipo vecino más cercano es el clasificador 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 se acerca al infinito, el clasificador vecino más cercano garantiza una tasa de error no peor que el doble de la tasa de error Bayes (la tasa de error mínima alcanzable dada la distribución de los datos).

El clasificador de vecino más cercano ponderado

El $k$ -el mejor clasificador de vecinos puede ser visto como asignar el $k$ vecinos más cercanos un peso ${displaystyle 1/k}$ y todos los demás $0$ peso. Esto se puede generalizar para ponderar los clasificadores vecinos más cercanos. Es decir, donde el $i$ a vecino más cercano se le asigna un peso ${displaystyle w_{ni}}$ Con ${textstyle sum _{i=1}^{n}w_{ni}=1}$ . Un resultado analógico sobre la fuerte consistencia de clasificadores vecinos más ponderados también sostiene.

Vamos. ${displaystyle C_{n}^{wnn}}$ denota el clasificador más cercano ponderado con pesos ${displaystyle {w_{ni}}_{i=1}^{n}}$ . Sujeto a las condiciones de regularidad, que en la teoría asintotica son variables condicionales que requieren supuestos para diferenciar entre parámetros con algunos criterios. En las distribuciones de clase el exceso de riesgo tiene la siguiente expansión asintotica

{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)},}

{displaystyle B_{1}}

{displaystyle B_{2}}

{displaystyle s_{n}^{2}=sum _{i=1}^{n}w_{ni}^{2}}

{displaystyle t_{n}=n^{-2/d}sum _{i=1}^{n}w_{ni}left{i^{1+2/d}-(i-1)^{1+2/d}right}}

El esquema de ponderación óptima ${displaystyle {w_{ni}^{*}}_{i=1}^{n}}$ , que equilibra los dos términos en la pantalla anterior, se da como sigue: 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]}

{displaystyle i=1,2,dotsk^{*}}

{displaystyle w_{ni}^{*}=0}

{displaystyle i=k^{*}+1,dotsn}

Con pesos óptimos el término dominante en la expansión asintotica del exceso de riesgo es ${displaystyle {mathcal {O}}(n^{-{frac {4}{d+4}}})}$ . Resultados similares son ciertos cuando se usa un clasificador vecino más cercano.

Propiedades

k-NN es un caso especial de un "globo" de densidad de núcleo y ancho de banda variable. Estimador con núcleo uniforme.

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

k-NN tiene algunos resultados de consistencia sólidos. A medida que la cantidad de datos se acerca al infinito, se garantiza que el algoritmo k-NN de dos clases producirá 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). ). Son posibles varias mejoras en la velocidad k-NN mediante el uso de gráficos de proximidad.

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_{kmathrm {NN} } leq R^{*}left(2-{frac {MR^{*}}{M-1}}right)}

{displaystyle R^{*}}

{displaystyle R_{kNN}}

M

{displaystyle M=2}

{displaystyle R^{*}}

Tasas de error

Hay muchos resultados en la tasa de error de la $k$ clasificadores vecinos más cercanos. El $k$ -El mejor clasificador de vecinos es fuerte (es decir, para cualquier distribución conjunta en ${displaystyle (X,Y)}$ ) consistente ${displaystyle k:=k_{n}}$ divergencias y ${displaystyle k_{n}/n}$ converge a cero como ${displaystyle nto infty }$ .

Vamos. ${displaystyle C_{n}^{knn}}$ denota el $k$ clasificador vecino más cercano basado en un conjunto de formación de tamaño $n$ . En determinadas condiciones de regularidad, el exceso de riesgo produce la siguiente expansión asintotica

{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)},}

{displaystyle B_{1}}

{displaystyle B_{2}}

La elección ${displaystyle k^{*}=lfloor Bn^{frac {4}{d+4}}rfloor }$ ofrece un intercambio entre los dos términos en la pantalla anterior, para el cual ${displaystyle k^{*}}$ -nearest error vecino converge al error Bayes a la velocidad óptima (minimax) ${displaystyle {mathcal {O}}(n^{-{frac {4}{d+4}}})}$ .

Aprendizaje métrico

El rendimiento de la clasificación de vecinos K-más cercanos a menudo se puede mejorar significativamente mediante el aprendizaje métrico (supervisado). Los algoritmos populares son el análisis de componentes de vecindad y el vecino más cercano de gran margen. Los algoritmos de aprendizaje de métricas supervisados utilizan la información de la etiqueta para aprender una nueva métrica o pseudométrica.

Extracción de características

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), los datos de entrada se transformarán en un conjunto de representación reducida de características (también vector de características nombradas). Transformar los datos de entrada en un conjunto de características se llama 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 de tamaño completo. La extracción de características se realiza en datos sin procesar antes de aplicar el algoritmo k-NN en los datos transformados en el espacio de características.

Un ejemplo de un proceso típico de cálculo de visión por computadora para el reconocimiento facial usando k-NN, que incluye pasos de preprocesamiento de extracción de características y reducción de dimensiones (generalmente implementados con OpenCV):

Detección de la cara de jabalí
Análisis de seguimiento de mediana tendencia
Proyección de PCA o Fisher LDA en espacio de características, seguido de k- Clasificación nacional

Reducción de dimensiones

Para datos de alta dimensión (por ejemplo, con un número de dimensiones superior a 10), la reducción de dimensión generalmente se realiza antes de aplicar el algoritmo k-NN para evitar los efectos de la maldición de la dimensionalidad. .

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 al vector de consulta de búsqueda (imagine 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 dimensiones 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 previo al procesamiento, seguido de agrupación por k-NN en vectores de características en un espacio de dimensión reducida. Este proceso también se denomina incrustación de baja dimensión.

Para conjuntos de datos muy dimensionales (por ejemplo, cuando se realiza una búsqueda de similitud en secuencias de vídeo en vivo, datos de ADN o series de tiempo de alta dimensión) ejecutan un rápido aprox. k- La búsqueda de la NN usando la piratería sensible a la localidad, "proyecciones aleatorias", "sketches" u otras técnicas de búsqueda de similitudes de alta dimensión de la caja de herramientas VLDB podría ser la única opción factible.

Límite de decisión

Las reglas del vecino más cercano en vigor calculan implícitamente el límite de decisión. También es posible calcular el límite de decisión explícitamente y hacerlo de manera eficiente, de modo que la complejidad computacional sea función de la complejidad del límite.

Reducción de datos

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

Seleccione Clase-outliers, es decir, datos de capacitación que se clasifican incorrectamente por k- AN (para un dado) k)
Separar 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 puede ser clasificado correctamente k- NN usando prototipos. Los puntos absorbidos se pueden eliminar del conjunto de entrenamiento.

Selección de aprendices de clase

Un ejemplo de entrenamiento rodeado de ejemplos de otras clases se llama outlier de clase. Las causas de los atípicos de clase incluyen:

error aleatorio
insuficientes ejemplos de formación de esta clase (un ejemplo aislado aparece en lugar de un grupo)
falta de características importantes (las clases están separadas en otras dimensiones que no conocemos)
demasiados ejemplos de entrenamiento de otras clases (clases no equilibradas) que crean un fondo "hostil" para la clase pequeña dada

Los valores atípicos de clase con k-NN producen ruido. Se pueden detectar y separar para futuros análisis. Dados dos números naturales, k>r>0, un ejemplo de entrenamiento se llama (k,r)NN clase atípica si sus k vecinos más cercanos incluyen más de r ejemplos de otras clases.

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

vecino más cercano (CNN, el algoritmo de Hart) es un algoritmo diseñado para reducir el conjunto de datos para k- Clasificación de la AN. Selecciona el conjunto de prototipos U de los datos de capacitación, tal que 1NN con U puede clasificar los ejemplos casi exactamente como lo hace 1NN con todo el conjunto de datos.

Tres tipos de puntos: prototipos, aulas y puntos absorbidos.

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

Escanear todos los elementos X, buscando un elemento x cuyo prototipo más cercano U tiene una etiqueta diferente x.
Retirar x desde X y añadirlo a U
Repita el escaneo hasta que no se añadan más prototipos U.

Uso U en lugar de X para clasificación. Los ejemplos que no son prototipos se llaman puntos "absorbed".

Es eficaz escanear los ejemplos de entrenamiento en orden decreciente de proporción de bordes. La relación de límites de un ejemplo de entrenamiento x se define como

a () x) . x'-y . / . x-y .

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

La relación del borde está en el intervalo [0,1] porque $‖ x'-y ‖$ nunca excede $‖ x-y ‖$ . Este orden da preferencia a los límites de las clases para su inclusión en el conjunto de prototipos U. Un punto con una etiqueta diferente a x se denomina externo a x. El cálculo de la relación límite se ilustra en la figura de la derecha. Los puntos de datos están etiquetados por colores: el punto inicial es x y su etiqueta es roja. Los puntos externos son azules y verdes. El punto externo más cercano a x es y. El punto rojo más cercano al y es x' . La relación del borde $a (x) = ‖ x'-y ‖ / ‖ x-y ‖$ 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 (roja, verde y azul). Fig. 1: inicialmente hay 60 puntos en cada clase. La figura 2 muestra el mapa de clasificación de 1NN: cada píxel es clasificado por 1NN utilizando todos los datos. La figura 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). La figura 4 muestra el conjunto de datos reducido. Los 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 los números de las clases atípicas, prototipos y puntos absorbidos para las tres clases. El número de prototipos varía del 15% al 20% para diferentes clases en este ejemplo. La figura 5 muestra que el mapa de clasificación 1NN con los prototipos es muy similar al del conjunto de datos inicial. Las figuras se produjeron utilizando el subprograma Mirkes.

Reducción del modelo CNN para clasificadores k-NN
Fig. 1. El conjunto de datos.
Fig. 2. El mapa de clasificación 1NN.
Fig. 3. El mapa de clasificación 5NN.
Fig. 4. El conjunto de datos CNN reducido.
Fig. 5. El mapa de clasificación 1NN basado en los prototipos extraídos de la CNN.

K-NN regression

En la regresión 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, ponderados por la inversa de su distancia. Este algoritmo funciona de la siguiente manera:

Computa la distancia Euclidean o Mahalanobis del ejemplo de consulta a los ejemplos etiquetados.
Ordene los ejemplos etiquetados aumentando la distancia.
Encontrar un número heurista óptimo k de vecinos más cercanos, basados en RMSE. Esto se hace utilizando validación cruzada.
Calcular un promedio de distancia inversa ponderado con el k- vecinos multivariados.

Valor atípico de K-NN

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

Validación de resultados

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 sólidos, como la prueba del índice de verosimilitud.

Más resultados...