k -algoritmo de vecinos más cercanos- k-nearest neighbors algorithm

En estadística , el algoritmo k -vecinos más cercanos ( k -NN ) es un método de clasificación no paramétrico desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951, y luego 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 . La salida depende de si k -NN se usa para clasificación o regresión:

  • En la clasificación k-NN , la salida es una pertenencia a una clase. Un objeto se clasifica mediante un voto de pluralidad de sus vecinos, y el objeto se asigna a la clase más común entre sus k vecinos más cercanos ( k es un número entero positivo , típicamente pequeño). Si k  = 1, entonces el objeto simplemente se asigna a la clase de ese único vecino más cercano.
  • En la regresión k-NN , la salida es el valor de propiedad del objeto. Este valor es el promedio de los valores de k vecinos más cercanos.

k -NN es un tipo de clasificación donde la función solo se aproxima localmente y todos los cálculos se aplazan 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 su precisión drásticamente.

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 lejanos. Por ejemplo, un esquema de ponderación común consiste en darle a cada vecino una ponderación de 1 / d , donde d es la distancia al vecino.

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 se puede considerar 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.

Marco estadístico

Supongamos que tenemos pares que toman valores en , donde Y es la etiqueta de clase de X , de modo que para (y distribuciones de probabilidad ). Dada alguna norma sobre y un punto , vamos a ser un reordenamiento de los datos de entrenamiento de tal manera que .

Algoritmo

Ejemplo de clasificación k -NN. La muestra de prueba (punto verde) debe clasificarse en cuadrados azules o en triángulos rojos. Si k = 3 (círculo de línea continua) se asigna a los triángulos rojos porque hay 2 triángulos y solo 1 cuadrado dentro del círculo interior. Si k = 5 (círculo de línea discontinua) se asigna a los cuadrados azules (3 cuadrados frente a 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 solo 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 un punto de prueba) se clasifica asignando la etiqueta que es 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 para la clasificación de texto, se puede usar 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 génica, por ejemplo, k -NN se ha empleado con coeficientes de correlación, como Pearson y Spearman, como métrica. A menudo, la precisión de 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 más cercano de gran margen o vecindario .

Un inconveniente de la clasificación básica de "votación por mayoría" 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 los 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 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. A continuación, se puede aplicar K -NN al SOM.

Selección de parámetros

La mejor elección de k depende de los datos; generalmente, valores más altos 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 (ver 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 de vecino más cercano.

La precisión del algoritmo k -NN puede verse seriamente degradada por la presencia de características ruidosas o irrelevantes, o si las escalas de características no son consistentes con su importancia. Se ha realizado un gran esfuerzo 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 características. 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 la k empíricamente óptima en esta configuración es mediante el método bootstrap.

El clasificador de 1 vecino más cercano

El clasificador de tipo de vecino más cercano 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 .

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 de Bayes (la tasa de error mínima alcanzable dada la distribución de los datos).

El clasificador de vecino más cercano ponderado

El clasificador de k -vecino más cercano puede verse como asignando un peso a los k vecinos más cercanos y a todos los demás un 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 , con . También es válido un resultado análogo sobre la fuerte consistencia de los clasificadores de vecinos más cercanos ponderados.

Dejar que denotan el clasificador más cercana ponderada con pesos . Sujeto a las condiciones de regularidad en las distribuciones de clases, el exceso de riesgo tiene la siguiente expansión asintótica

para constantes y dónde y .

El esquema de ponderación óptimo , que equilibra los dos términos en la pantalla anterior, se da de la siguiente manera: set ,

para y
para .

Con ponderaciones óptimas, el término dominante en la expansión asintótica del exceso de riesgo es . Resultados similares son ciertos cuando se usa un clasificador de vecino más cercano empaquetado .

Propiedades

k -NN es un caso especial de un estimador de "globo" de densidad de kernel de ancho de banda variable con un kernel uniforme .

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 es computacionalmente intensivo para grandes conjuntos de entrenamiento. El uso de un algoritmo de búsqueda de vecino más cercano aproximado hace que k- NN sea computacionalmente manejable incluso para grandes conjuntos de datos. Se han propuesto muchos algoritmos de búsqueda de vecinos más cercanos a lo largo de los años; estos generalmente buscan reducir el número de evaluaciones a distancia realmente realizadas.

k- NN tiene algunos resultados de gran consistencia . 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). Es posible realizar varias mejoras en la velocidad k -NN mediante el uso de gráficos de proximidad.

Para la clasificación k- NN de clases múltiples , Cover y Hart (1967) prueban una tasa de error de límite superior de

donde es la tasa de error de Bayes (que es la tasa de error mínima posible), es la tasa de error k- NN y M es el número de clases en el problema. A medida que la tasa de error bayesiano se acerca a cero, este límite se reduce a "no más del doble de la tasa de error bayesiano".

Tasas de error

Hay muchos resultados sobre la tasa de error de los k clasificadores vecinos más cercanos. El clasificador de vecino más cercano k es fuertemente (es decir, para cualquier distribución conjunta activada ) consistente siempre que diverja y converja a cero como .

Vamos a denotar la k más próximo vecino clasificador basado en un conjunto de entrenamiento de tamaño n . Bajo ciertas condiciones de regularidad, el exceso de riesgo produce la siguiente expansión asintótica

para algunas constantes y .

La elección ofrece una compensación entre los dos términos en la pantalla anterior, para la cual el error del vecino más cercano converge con el error de Bayes en la tasa óptima ( minimax ) .

Aprendizaje métrico

El rendimiento de la clasificación de vecino más cercano K a menudo se puede mejorar significativamente a través del 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 supervisadas utilizan la información de la etiqueta para aprender una nueva métrica o pseudo-métrica .


Extracción de características

Cuando los datos de entrada a 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 características de representación reducida (también llamado vector de características ). La transformación de los datos de entrada en el conjunto de características 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 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 una canalización típica de computación de visión por computadora para el reconocimiento facial usando k -NN, incluidos los pasos de preprocesamiento de extracción de características y reducción de dimensión (generalmente implementados con OpenCV ):

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

Reducción de dimensión

Para datos de alta dimensión (por ejemplo, con un número de dimensiones superior a 10), la reducción de dimensiones se realiza normalmente 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 es inútil en dimensiones altas porque todos los vectores son casi equidistantes al vector de consulta de búsqueda (imagina 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 un paso previo al procesamiento, seguido de agrupamiento por k -NN en la característica vectores en el espacio de dimensión reducida. Este proceso también se denomina incrustación de baja dimensión .

Para conjuntos de datos de muy alta dimensión (p. Ej., Cuando se realiza una búsqueda de similitud en transmisiones de video en vivo, datos de ADN o series de tiempo de alta dimensión ) ejecutando una búsqueda rápida aproximada de k -NN usando hash sensible a la localidad , "proyecciones aleatorias", "bocetos" o otras técnicas de búsqueda de similitudes de alta dimensión de la caja de herramientas VLDB podrían ser la única opción factible.

Límite de decisión

En efecto, 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 explícitamente y hacerlo de manera eficiente, de modo que la complejidad computacional sea una 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 para trabajar con grandes conjuntos de datos. Por lo general, solo 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:

  1. Seleccione los valores atípicos de la clase , es decir, los datos de entrenamiento que están 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 clasificarse correctamente por k -NN utilizando prototipos. Los puntos absorbidos se pueden eliminar del conjunto de entrenamiento.

Selección de valores atípicos de clase

Un ejemplo de entrenamiento rodeado de ejemplos de otras clases se denomina valor atípico de clase. Las causas de los valores atípicos de la clase incluyen:

  • error al azar
  • ejemplos de entrenamiento insuficientes de esta clase (aparece un ejemplo aislado en lugar de un grupo)
  • faltan características importantes (las clases están separadas en otras dimensiones que no conocemos)
  • demasiados ejemplos de entrenamiento de otras clases (clases no balanceadas) que crean un trasfondo "hostil" para la clase pequeña dada

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

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. Selecciona el conjunto de prototipos U de los datos de entrenamiento, de modo que 1NN con U puede clasificar los ejemplos casi con tanta precisión como lo hace 1NN con todo el conjunto de datos.

Cálculo de la relación de fronteras.
Tres tipos de puntos: prototipos, valores atípicos de clase y puntos absorbidos.

Dado un conjunto de entrenamiento X , 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. Quite x de X y agréguelo a U
  3. Repetir la búsqueda hasta que no haya más prototipos se añaden a T .

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

Es eficaz escanear los ejemplos de entrenamiento en orden de proporción de borde decreciente. 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 que x , y | | x'-y | | es la distancia desde y hasta su ejemplo más cercano x ' con la misma etiqueta que x .

La relación de borde está en el intervalo [0,1] porque | | x'-y | | nunca excede | | xy | | . Esta ordenación da preferencia a las fronteras de las clases para su inclusión en el conjunto de prototipos U . Un punto de una etiqueta diferente a x se llama externo ax . El cálculo de la relación de la frontera 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 azul y verde. El punto externo más cercano ax 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. La figura 2 muestra el mapa de clasificación 1NN: cada píxel se clasifica 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 los valores atípicos de la clase, los prototipos y los 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.

regresión k -NN

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, ponderado por la inversa de su distancia. Este algoritmo funciona de la siguiente manera:

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

k -NN valor atípico

La distancia al k- ésimo vecino más cercano también puede verse como una estimación de la 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, más probable es 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 minería de datos, el factor de valores atípicos locales , funciona bastante bien también en comparación con enfoques más recientes y más complejos, según un análisis experimental a gran escala.

Validación de resultados

Una matriz de confusión o "matriz de emparejamiento" 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 de razón de verosimilitud .

Ver también

Referencias

Otras lecturas