algoritmo de los k vecinos más cercanos

Método de clasificación no paramétrico

En estadística , el algoritmo de k -vecinos más cercanos ( k -NN ) es un método de aprendizaje supervisado no paramétrico . Fue desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951, ^[1] y luego ampliado por Thomas Cover . ^[2] La mayoría de las veces, se utiliza para la clasificación , como un clasificador k -NN , cuyo resultado es una pertenencia a una clase. Un objeto se clasifica por 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 entero positivo , normalmente pequeño). Si k  = 1, entonces el objeto simplemente se asigna a la clase de ese único vecino más cercano.

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

Tanto para la clasificación como para la regresión, una técnica útil puede ser la de asignar pesos 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. ^[3]

La entrada consta de los k ejemplos de entrenamiento más cercanos en 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 se puede considerar 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 todos los cálculos se posponen hasta la evaluación de la función. Dado que este algoritmo se basa en la distancia, si las características representan unidades físicas diferentes o vienen en escalas muy diferentes, entonces la normalización de los datos de entrenamiento por características puede mejorar en gran medida su precisión. ^[4]

Configuración estadística

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 en y un punto , sea un reordenamiento de los datos de entrenamiento tal que . ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$ ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$ ${\displaystyle X|Y=r\sim P_{r}}$ ${\displaystyle r=1,2}$ ${\displaystyle P_{r}}$ ${\displaystyle \|\cdot \|}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle x\in \mathbb {R} ^{d}}$ ${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$ ${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$

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 ú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 etiqueta (un punto de consulta o 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.

Aplicación de un clasificador k- NN considerando k = 3 vecinos. Izquierda: Dado el punto de prueba "?", el algoritmo busca los 3 puntos más cercanos en el conjunto de entrenamiento y adopta el voto mayoritario para clasificarlo como "clase roja". Derecha: Al repetir iterativamente la predicción sobre todo el espacio de características (X1, X2), se puede representar la "superficie de decisión".

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 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 Pearson y Spearman, como métrica. ^[5] 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 vecindad o de vecino más cercano de margen grande .

Un inconveniente de la clasificación básica de "votación mayoritaria" se produce 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. ^[6] 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 al inverso 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. K -NN se puede aplicar entonces 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, ^[7] pero hacen que los límites entre clases sean menos claros. Se puede seleccionar un buen 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 del 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 las características no son coherentes con su importancia. Se ha dedicado mucho esfuerzo de investigación a seleccionar o escalar características para mejorar la clasificación. Un enfoque particularmente popular ^{[ cita requerida ]} es el uso de algoritmos evolutivos para optimizar el escalamiento de características. ^[8] Otro enfoque popular es escalar características mediante la información mutua de los datos de entrenamiento con las clases de entrenamiento. ^{[ cita requerida ]}

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

El1-clasificador de vecino más cercano

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

El clasificador de vecino más próximo ponderado

El clasificador de k vecinos más cercanos puede considerarse como el que asigna a los k vecinos más cercanos un peso y a todos los demás un peso 0. Esto se puede generalizar a los 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 se cumple un resultado análogo sobre la fuerte consistencia de los clasificadores de vecinos más cercanos ponderados. ^[10] ${\displaystyle 1/k}$ ${\displaystyle w_{ni}}$ ${\textstyle \sum _{i=1}^{n}w_{ni}=1}$

Sea el clasificador ponderado más próximo con pesos . Sujeto a condiciones de regularidad, que en la teoría asintótica son variables condicionales que requieren suposiciones para diferenciar entre parámetros con algún criterio. En las distribuciones de clase el riesgo excesivo tiene la siguiente expansión asintótica ^[11] para constantes y donde y . ${\displaystyle C_{n}^{wnn}}$ ${\displaystyle \{w_{ni}\}_{i=1}^{n}}$ $${\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 óptimo , que equilibra los dos términos en la visualización anterior, se da de la siguiente manera: conjunto , para y para . ${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$ ${\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,\dots ,k^{*}}$ $${\displaystyle w_{ni}^{*}=0}$$ ${\displaystyle i=k^{*}+1,\dots ,n}$

Con ponderaciones óptimas, el término dominante en la expansión asintótica del riesgo excesivo es . Se obtienen resultados similares cuando se utiliza un clasificador de vecino más próximo en bolsas . ${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$

Propiedades

k -NN es un caso especial de un estimador "global" de densidad de kernel y ancho de banda variable con un kernel uniforme . ^{[12] [13]}

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 gran esfuerzo computacional para conjuntos de entrenamiento grandes. El uso de un algoritmo de búsqueda aproximada del vecino más cercano hace que la red neuronal k sea computacionalmente factible 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 la cantidad de evaluaciones de distancia que realmente se realizan.

El algoritmo k- NN tiene algunos resultados de consistencia sólida . A medida que la cantidad de datos se acerca al infinito, se garantiza que el algoritmo k -NN de dos clases arrojará 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 varias mejoras en la velocidad del algoritmo k -NN mediante el uso de gráficos de proximidad. ^[14]

Para la clasificación multiclase k- NN, 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 asintótica k -NN y M es el número de clases en el problema. Este límite es estricto en el sentido de que tanto el límite inferior como el superior se pueden lograr mediante alguna distribución. ^[15] Para y a medida que la tasa de error bayesiana se acerca a cero, este límite se reduce a "no más del doble de la tasa de error bayesiana". $${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$ ${\displaystyle R^{*}}$ ${\displaystyle R_{kNN}}$ ${\displaystyle M=2}$ ${\displaystyle R^{*}}$

Tasas de error

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

Sea el clasificador vecino más próximo k basado en un conjunto de entrenamiento de tamaño n . En determinadas condiciones de regularidad, el riesgo excesivo produce la siguiente expansión asintótica ^[11] para algunas constantes y . ${\displaystyle C_{n}^{knn}}$ $${\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 ofrece un equilibrio entre los dos términos en la visualización anterior, para el cual el error del vecino más cercano converge al error de Bayes en la tasa óptima ( minimax ) . ${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$ ${\displaystyle k^{*}}$ ${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$

Aprendizaje métrico

El rendimiento de la clasificación de K vecinos más cercanos a menudo se puede mejorar significativamente a través del aprendizaje métrico ( supervisado ). Los algoritmos populares son el análisis de componentes del vecindario y el vecino más cercano de margen grande . Los algoritmos de aprendizaje métrico supervisado 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), entonces 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 un proceso típico de cálculo de visión artificial para reconocimiento facial utilizando k -NN, que incluye pasos de preprocesamiento de extracción de características y reducción de dimensión (generalmente implementados con OpenCV ):

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

Reducción de dimensión

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

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 ubicados 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 dimensión 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 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 . ^[18]

Para conjuntos de datos de dimensiones muy altas (por ejemplo, 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 ), ejecutar una búsqueda rápida aproximada de k -NN utilizando hash sensible a la localidad , "proyecciones aleatorias", ^[19] "bocetos" ^[20] 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.

Límite de decisión

Las reglas del vecino más próximo 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. ^[21]

Reducción de datos

La reducción de datos es uno de los problemas más importantes a la hora de trabajar con grandes conjuntos de datos. Normalmente, solo se necesitan algunos 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 clase , es decir, los datos de entrenamiento que están clasificados incorrectamente por k -NN (para un k dado )
2. 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 pueden clasificarse correctamente mediante k -NN utilizando prototipos. Los puntos absorbidos pueden luego eliminarse del conjunto de entrenamiento.

Selección de valores atípicos de clase

Un ejemplo de entrenamiento rodeado de ejemplos de otras clases se denomina clase atípica. Las causas de las clases atípicas incluyen:

• error aleatorio
• 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 desequilibradas) que crean un entorno "hostil" para la pequeña clase dada.

Los valores atípicos de clase con k -NN producen ruido. Se pueden detectar y separar para un análisis futuro. Dados dos números naturales, k > r > 0, un ejemplo de entrenamiento se denomina 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 reducción de datos

El vecino más cercano condensado (CNN, el algoritmo Hart ) es un algoritmo diseñado para reducir el conjunto de datos para la clasificación k -NN. ^[22] 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 borde

Tres tipos de puntos: prototipos, valores atípicos de clase y puntos absorbidos.

Dado un conjunto de entrenamiento X , CNN funciona iterativamente:

1. Escanee todos los elementos de X , buscando un elemento x cuyo prototipo más cercano a U tenga una etiqueta diferente a x .
2. Quitar x de X y agregarlo 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 proporción de borde. ^[23] La proporció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 orden da preferencia a los bordes de las clases para su inclusión en el conjunto de prototipos U . Un punto de 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 por 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. La Fig. 2 muestra el mapa de clasificación 1NN: cada píxel es clasificado por 1NN utilizando todos los datos. La 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). La 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 los números de los 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 del conjunto de datos inicial. Las figuras se generaron utilizando la aplicación Mirkes. ^[23]

• 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 reducido de CNN.
• 
  Fig. 5. Mapa de clasificación 1NN basado en los prototipos extraídos de CNN.

a-Regresión NN

En la regresión k -NN, también conocida como suavizado k -NN, se utiliza el algoritmo k -NN para estimar variables continuas . ^{[ cita requerida ]} 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. 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 de vecinos más próximos óptimo desde el punto de vista heurístico, en función del RMSE . Esto se hace mediante validación cruzada.
4. Calcule un promedio ponderado por distancia inversa con los k vecinos multivariados más cercanos.

a-NN valor atípico

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 de valor atípico 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. ^[24] Aunque bastante simple, este modelo de valor atípico, junto con otro método clásico de minería de datos, el factor de valor atípico local , 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. ^[25]

Validación de resultados

A menudo se utiliza una matriz de confusión o "matriz de emparejamiento" 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 . ^{[ ¿Cómo? ]}

Véase también

• Portal de matemáticas

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

Referencias

1. Fix, Evelyn; Hodges, Joseph L. (1951). Análisis discriminatorio. Discriminación no paramétrica: propiedades de consistencia (PDF) (Informe). Facultad de Medicina de Aviación de la USAF, Randolph Field, Texas. Archivado (PDF) del original el 26 de septiembre de 2020.
2. Cover, Thomas M. ; Hart, Peter E. (1967). "Clasificación de patrones de vecinos más próximos" (PDF) . IEEE Transactions on Information Theory . 13 (1): 21–27. CiteSeerX 10.1.1.68.2616 . doi :10.1109/TIT.1967.1053964. S2CID  5246200. 
3. Este esquema es una generalización de la interpolación lineal.
4. Hastie, Trevor. (2001). Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción: con 200 ilustraciones a todo color . Tibshirani, Robert., Friedman, JH (Jerome H.). Nueva York: Springer. ISBN 0-387-95284-5.OCLC 46809224  .
5. Jaskowiak, Pablo A.; Campello, Ricardo JGB (2011). "Comparación de coeficientes de correlación como medidas de disimilitud para la clasificación del cáncer en datos de expresión génica". Simposio Brasileño de Bioinformática (BSB 2011) : 1–8. CiteSeerX 10.1.1.208.993 . 
6. Coomans, Danny; Massart, Desire L. (1982). "Reglas alternativas de vecino más cercano en reconocimiento de patrones supervisado: Parte 1. Clasificación de vecino más cercano mediante reglas de votación alternativas". Analytica Chimica Acta . 136 : 15–27. doi :10.1016/S0003-2670(01)95359-0.
7. Everitt, Brian S.; Landau, Sabine; Leese, Morven; y Stahl, Daniel (2011) "Métodos de agrupamiento diversos", en Análisis de conglomerados , 5.ª edición, John Wiley & Sons, Ltd., Chichester, Reino Unido
8. Nigsch, Florian; Bender, Andreas; van Buuren, Bernd; Tissen, Jos; Nigsch, Eduard; Mitchell, John BO (2006). "Predicción del punto de fusión empleando algoritmos de k vecinos más cercanos y optimización de parámetros genéticos". Journal of Chemical Information and Modeling . 46 (6): 2412–2422. doi :10.1021/ci060149f. PMID  17125183.
9. Hall, Peter; Park, Byeong U.; Samworth, Richard J. (2008). "Elección del orden de vecinos en la clasificación del vecino más próximo". Anales de Estadística . 36 (5): 2135–2152. arXiv : 0810.5276 . Código Bibliográfico :2008arXiv0810.5276H. doi :10.1214/07-AOS537. S2CID  14059866.
10. Stone, Charles J. (1977). "Regresión no paramétrica consistente". Anales de Estadística . 5 (4): 595–620. doi : 10.1214/aos/1176343886 .
11. Samworth, Richard J. (2012). "Clasificadores de vecinos más próximos ponderados óptimos". Anales de Estadística . 40 (5): 2733–2763. arXiv : 1101.5783 . doi :10.1214/12-AOS1049. S2CID  88511688.
12. Terrell, George R.; Scott, David W. (1992). "Estimación de densidad de kernel variable". Anales de Estadística . 20 (3): 1236–1265. doi : 10.1214/aos/1176348768 .
13. Mills, Peter (9 de agosto de 2012). "Clasificación estadística eficiente de mediciones satelitales". Revista Internacional de Teledetección .
14. Toussaint, Godfried T. (abril de 2005). "Gráficos de proximidad geométrica para mejorar los métodos de vecino más cercano en el aprendizaje basado en instancias y la minería de datos". Revista internacional de geometría computacional y aplicaciones . 15 (2): 101–150. doi :10.1142/S0218195905001622.
15. Devroye, L., Gyorfi, L. y Lugosi, G. Una teoría probabilística del reconocimiento de patrones. Discrete Appl Math 73, 192–194 (1997).
16. Devroye, Luc; Gyorfi, Laszlo; Lugosi, Gabor (1996). Una teoría probabilística del reconocimiento de patrones . Springer. ISBN 978-0-3879-4618-4.
17. Beyer, Kevin; et al. "¿Cuándo tiene sentido el término "vecino más próximo"?" (PDF) . Teoría de bases de datos—ICDT'99 . 1999 : 217–235.
18. Shaw, Blake; Jebara, Tony (2009), "Incrustación que preserva la estructura" (PDF) , Actas de la 26.ª Conferencia internacional anual sobre aprendizaje automático (publicada en junio de 2009), págs. 1-8, doi : 10.1145/1553374.1553494, ISBN 9781605585161, Número de identificación del sujeto  8522279
19. Bingham, Ella; Mannila, Heikki (2001). "Proyección aleatoria en la reducción de dimensionalidad". Actas de la séptima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '01 . págs. 245–250. doi :10.1145/502512.502546. ISBN 158113391X. Número de identificación del sujeto  1854295.
20. Ryan, Donna (editora); Descubrimiento de alto rendimiento en series temporales , Berlín: Springer, 2004, ISBN 0-387-00857-8 
21. Bremner, David; Demaine, Erik ; Erickson, Jeff; Iacono, John ; Langerman, Stefan ; Morin, Pat ; Toussaint, Godfried T. (2005). "Algoritmos sensibles a la salida para calcular los límites de decisión del vecino más cercano". Geometría discreta y computacional . 33 (4): 593–604. doi : 10.1007/s00454-004-1152-0 .
22. Hart, Peter E. (1968). "La regla condensada del vecino más próximo". IEEE Transactions on Information Theory . 18 : 515–516. doi :10.1109/TIT.1968.1054155.
23. Mirkes, Evgeny M.; KNN y energía potencial: subprograma, Universidad de Leicester, 2011
24. Ramaswamy, Sridhar; Rastogi, Rajeev; Shim, Kyuseok (2000). "Algoritmos eficientes para extraer valores atípicos de grandes conjuntos de datos". Actas de la conferencia internacional ACM SIGMOD de 2000 sobre gestión de datos - SIGMOD '00 . Actas de la conferencia internacional ACM SIGMOD de 2000 sobre gestión de datos - SIGMOD '00. págs. 427–438. doi :10.1145/342009.335437. ISBN 1-58113-217-4.
25. Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). "Sobre la evaluación de la detección de valores atípicos no supervisados: medidas, conjuntos de datos y un estudio empírico". Minería de datos y descubrimiento de conocimiento . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.

Lectura adicional

• Dasarathy, Belur V. , ed. (1991). Normas de vecinos más cercanos (NN): técnicas de clasificación de patrones NN . 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.