algoritmo de k vecinos más cercanos

Método de clasificación no paramétrica.

En estadística , el algoritmo de k vecinos más cercanos ( k -NN ) es un método de aprendizaje supervisado no paramétrico desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951, ^[1] y posteriormente ampliado por Thomas Cover . ^[2] 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:

• En la clasificación k-NN , el resultado es una membresía de clase. Un objeto se clasifica mediante una pluralidad de votos 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 , normalmente pequeño). Si k  = 1, entonces el objeto simplemente se asigna a la clase de ese vecino más cercano.
• En la regresión k-NN , el resultado es el valor de propiedad del objeto. Este valor es el promedio de los valores de k vecinos más cercanos. Si k  = 1, entonces la salida simplemente se asigna al valor de ese 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. ^[3]

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

Los vecinos se toman de un conjunto de objetos para los cuales 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 del algoritmo k -NN es que es sensible a la estructura local de los datos.

Configuración estadística

Supongamos que tenemos pares que toman valores en , donde Y es la etiqueta de clase de X , de modo que for (y distribuciones de probabilidad ). Dada alguna norma y un punto , sea una reordenación de los datos de entrenamiento de tal manera 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 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 etiquetar (una consulta o 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 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 génica, por ejemplo, k -NN se ha empleado con coeficientes de correlación, como los de Pearson y Spearman, como métrica. ^[5] 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 vecino más cercano de margen grande o el análisis de componentes de vecindario .

Un inconveniente de la clasificación básica de "voto mayoritario" 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 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. 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, ^[7] 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 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 ^{[ cita necesaria ]} es el uso de algoritmos evolutivos para optimizar el escalado de funciones. ^[8] Otro enfoque popular es escalar características mediante la información mutua de los datos de entrenamiento con las clases de entrenamiento. ^{[ cita necesaria ]}

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 este entorno es mediante el método bootstrap. ^[9]

El clasificador de 1 vecino más cercano

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 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

Se puede considerar que el clasificador de k vecinos más cercanos asigna 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 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}$

Denotemos el clasificador ponderado más cercano con pesos . Sujeto a condiciones de regularidad, que en la teoría asintótica son variables condicionales que requieren supuestos para diferenciar entre parámetros con algunos criterios. En las distribuciones de clases, el exceso de riesgo tiene la siguiente expansión asintótica ^[11] ${\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 pantalla anterior, se proporciona de la siguiente manera: set , ${\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 pesos óptimos, el término dominante en la expansión asintótica del exceso de riesgo es . Se obtienen resultados similares cuando se utiliza un clasificador de vecino más cercano en bolsas . ${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$

Propiedades

k -NN es un caso especial de un estimador "globo" de densidad de núcleo de ancho de banda variable con un núcleo 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 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). ^[2] Son posibles varias mejoras en la velocidad k -NN mediante el uso de gráficos de proximidad. ^[14]

Para la clasificación k- NN de clases múltiples , 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)}$$

k-M^[15] ${\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 vecinos más cercanos. ^[16] El clasificador de vecino k -más cercano es fuertemente consistente (es decir, para cualquier distribución conjunta en ) siempre que diverja y converja a cero como . ${\displaystyle (X,Y)}$ ${\displaystyle k:=k_{n}}$ ${\displaystyle k_{n}/n}$ ${\displaystyle n\to \infty }$

Denotemos el k clasificador vecino más cercano 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 ^[11] ${\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 una compensación entre los dos términos de la imagen anterior, para la cual el error del vecino más cercano converge con el error de Bayes a la tasa óptima ( minimax ) . ${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$ ${\displaystyle k^{*}}$ ${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$

Aprendizaje métrico

El rendimiento de la clasificación del vecino K más cercano 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 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 representación reducida de características (también denominado vector de características). ). 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 utilizando k -NN, incluidos los pasos de preprocesamiento de extracción de características y reducción de dimensiones (generalmente implementado con OpenCV ):

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

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 . ^[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 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 características. vectores en un espacio de dimensiones reducidas. Este proceso también se denomina incrustación de baja dimensión . ^[18]

Para conjuntos de datos de muy alta dimensión (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 ), se ejecuta una búsqueda rápida aproximada de k -NN utilizando hash sensible a la localidad , "proyecciones aleatorias", ^[19] " sketches" ^[20] u 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 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 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:

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 determinado )
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 k -NN pueden clasificar correctamente utilizando prototipos. Luego, 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 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 desequilibradas) que crean un trasfondo "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 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, 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 a partir 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 fronteriza.

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 a U tenga una etiqueta diferente a x .
2. Elimina x de X y agrégalo 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 bordes. ^[23] La relación de límites de un ejemplo de entrenamiento x se define como

un ( 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 desde y al ejemplo más cercano x' con la misma etiqueta que x .

La relación límite está en el intervalo [0,1] porque ‖ x'-y ‖ nunca excede ‖ xy ‖ . Este ordenamiento 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 llama 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 a y es x' . La relació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 (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. ^[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. Conjunto de datos reducido de CNN.
• 
  Fig. 5. Mapa de clasificación 1NN basado en los prototipos extraídos de CNN.

k -NN regresión

En la regresión k -NN, el algoritmo k -NN ^{[ cita necesaria ]} se utiliza para estimar variables continuas. Uno de esos 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 heurísticamente óptimo k de vecinos más cercanos, según RMSE . Esto se hace mediante validación cruzada.
4. Calcule un promedio ponderado de distancia inversa con los k vecinos multivariados más cercanos.

k -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 atípica popular en la detección de anomalías . Cuanto mayor es la distancia al k -NN, menor es la densidad local y es más probable que el punto de consulta sea un valor atípico. ^[24] 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. ^[25]

Validación de resultados

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

Ver 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

Referencias

1. Arreglar, Evelyn; Hodges, José L. (1951). Análisis discriminatorio. Discriminación no paramétrica: propiedades de coherencia (PDF) (Reporte). Escuela de Medicina de Aviación de la USAF, Randolph Field, Texas. Archivado (PDF) desde el original el 26 de septiembre de 2020.
2. Portada, Thomas M .; Hart, Peter E. (1967). "Clasificación de patrones de vecino más cercano" (PDF) . Transacciones IEEE sobre teoría de la información . 13 (1): 21-27. CiteSeerX 10.1.1.68.2616 . doi :10.1109/TIT.1967.1053964. S2CID  5246200. 
3. 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.
4. Este esquema es una generalización de la interpolación lineal.
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 genética". Simposio Brasileño de Bioinformática (BSB 2011) : 1–8. CiteSeerX 10.1.1.208.993 . 
6. Coomans, Danny; Massart, Deseo L. (1982). "Reglas alternativas de k-vecino más cercano en el reconocimiento de patrones supervisados: Parte 1. Clasificación de k-vecino más cercano mediante el uso de reglas de votación alternativas". Analytica Chimica Acta . 136 : 15-27. doi :10.1016/S0003-2670(01)95359-0.
7. Everitt, Brian S.; Landau, Sabina; Leese, Morven; y Stahl, Daniel (2011) "Miscellaneous Clustering Methods", en Cluster Analysis , quinta edición, John Wiley & Sons, Ltd., Chichester, Reino Unido.
8. Nigsch, Florian; Bender, Andrés; 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". Revista de información y modelado químico . 46 (6): 2412–2422. doi :10.1021/ci060149f. PMID  17125183.
9. Salón, Pedro; Park, Universidad de Byeong; Samworth, Richard J. (2008). "Elección del orden de los vecinos en la clasificación de vecinos más cercanos". Anales de Estadística . 36 (5): 2135–2152. arXiv : 0810.5276 . Código Bib : 2008arXiv0810.5276H. doi :10.1214/07-AOS537. S2CID  14059866.
10. Piedra, 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 cercanos 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 núcleo variable". Anales de Estadística . 20 (3): 1236–1265. doi : 10.1214/aos/1176348768 .
13. Molinos, Peter (9 de agosto de 2012). "Clasificación estadística eficiente de mediciones satelitales". Revista Internacional de Percepción Remota .
14. Toussaint, Godfried T. (abril de 2005). "Gráficos de proximidad geométrica para mejorar los métodos del vecino más cercano en el aprendizaje basado en instancias y la minería de datos". Revista internacional de aplicaciones y geometría computacional . 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. Matemáticas aplicadas discretas 73, 192–194 (1997).
16. Devroye, Luc; Gyorfi, Laszlo; Lugosi, Gabor (1996). Una teoría probabilística del reconocimiento de patrones . Saltador. ISBN 978-0-3879-4618-4.
17. Beyer, Kevin; et al. "¿Cuándo tiene sentido la palabra "vecino más cercano"?" (PDF) . Teoría de bases de datos: ICDT'99 . 1999 : 217–235.
18. Shaw, Blake; Jebara, Tony (2009), "Estructura que preserva la incrustación" (PDF) , Actas de la 26ª Conferencia Internacional Anual sobre Aprendizaje Automático (publicada en junio de 2009), págs. 1 a 8, doi :10.1145/1553374.1553494, ISBN 9781605585161, S2CID  8522279
19. Bingham, Ella; Mannila, Heikki (2001). "Proyección aleatoria en 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. S2CID  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, Juan ; Langerman, Stefan ; Morín, 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 cercano". Transacciones IEEE sobre teoría de la información . 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; Calce, Kyuseok (2000). "Algoritmos eficientes para extraer valores atípicos de grandes conjuntos de datos". Actas de la conferencia internacional ACM SIGMOD 2000 sobre gestión de datos - SIGMOD '00 . Actas de la conferencia internacional ACM SIGMOD 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, Arturo; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Asentimiento, 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 conocimientos . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.

Otras lecturas

• Dasarathy, Belur V. , ed. (1991). Normas del vecino más cercano (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 aprendizaje y visión . Prensa del MIT . ISBN 978-0262195478.