K-Nearest Neighbors (k-NN) es un algoritmo de aprendizaje supervisado no paramétrico utilizado tanto para clasificación como para regresión. En clasificación, a un nuevo punto de datos se le asigna la clase más común entre sus k vecinos más cercanos en el espacio de características, determinada por una métrica de distancia. En regresión, la salida es el promedio (o promedio ponderado) de los valores de esos vecinos. El algoritmo se basa en instancias, lo que significa que almacena todo el conjunto de datos de entrenamiento y realiza cálculos solo cuando se requiere una predicción, difiriendo toda generalización hasta el momento de la consulta.
El método fue desarrollado por primera vez por Evelyn Fix y Joseph Hodges en 1951 y posteriormente ampliado por Thomas Cover. Es uno de los algoritmos de aprendizaje automático más simples, pero puede lograr una precisión competitiva en muchos dominios, especialmente cuando el límite de decisión es irregular. Su rendimiento depende en gran medida de la elección de k, la métrica de distancia y el escalado de características.
Desarrollo Histórico
Los orígenes de k-NN se remontan a 1951, cuando Evelyn Fix y Joseph Hodges, que trabajaban en la Escuela de Medicina de Aviación de la Fuerza Aérea de los Estados Unidos, introdujeron un método de clasificación no paramétrico basado en los vecinos más cercanos. Su trabajo fue motivado por la necesidad de clasificar observaciones sin asumir una distribución estadística específica. En 1967, Thomas Cover y Peter Hart publicaron un artículo fundamental que formalizó las propiedades del algoritmo, incluidos los límites de su tasa de error en relación con el clasificador óptimo de Bayes. Esto estableció a k-NN como un enfoque teóricamente fundamentado en el reconocimiento de patrones. El algoritmo ganó popularidad en las décadas de 1960 y 1970 con el auge de la informática, ya que requería un tiempo de entrenamiento mínimo pero un almacenamiento sustancial. Desarrollos posteriores, como la introducción del voto ponderado y el aprendizaje de métricas de distancia, abordaron algunas de sus limitaciones.
Resumen del Algoritmo
En la clasificación k-NN, la entrada consiste en un conjunto de entrenamiento de ejemplos etiquetados, cada uno representado como un vector de características en un espacio multidimensional. El algoritmo almacena estos vectores y sus etiquetas. Cuando se presenta un punto de consulta, calcula la distancia desde la consulta a todos los puntos de entrenamiento, selecciona los k más cercanos y asigna la clase que aparece con mayor frecuencia entre ellos. Para k=1, la consulta se asigna simplemente a la clase de su vecino más cercano. La elección de k es crítica: un k pequeño puede provocar una alta varianza y sensibilidad al ruido, mientras que un k grande puede suavizar en exceso el límite de decisión e incluir puntos de otras clases.
Para la regresión, la salida es el promedio de los valores objetivo de los k vecinos más cercanos. Esto se conoce como suavizado por vecinos más cercanos. Si k=1, se convierte en interpolación por vecino más cercano, donde el valor predicho es exactamente el del punto de entrenamiento más cercano. Las variantes ponderadas asignan una mayor influencia a los vecinos más cercanos, a menudo utilizando pesos proporcionales al inverso de la distancia (1/d).
Métricas de Distancia y Escalado de Características
La elección de la métrica de distancia es crucial. Para características continuas, la distancia euclidiana es la más común. Para características discretas, como en la clasificación de texto, se utilizan la distancia de Hamming o métricas de superposición. En dominios especializados como el análisis de expresión génica, se han empleado coeficientes de correlación (Pearson, Spearman). La dependencia del algoritmo de la distancia significa que las características con diferentes unidades o escalas pueden dominar el cálculo. Por lo tanto, normalizar cada característica a una escala común (por ejemplo, puntuación z o escalado mínimo-máximo) es esencial para garantizar una contribución igual. Este paso de preprocesamiento puede mejorar significativamente la precisión.
Propiedades Estadísticas
Desde una perspectiva estadística, k-NN es un método no paramétrico porque no asume una forma funcional para la distribución de datos subyacente. Se supone que los datos de entrenamiento son pares (X_i, Y_i) donde X_i es un vector de características e Y_i es la etiqueta de clase. Para un punto de consulta x dado, los puntos de entrenamiento se reordenan según su distancia a x. La tasa de error del algoritmo converge a la tasa de error de Bayes a medida que aumenta el tamaño de la muestra, siempre que k crezca apropiadamente con n y k/n se acerque a cero. Esta propiedad, establecida por Cover y Hart, hace que k-NN sea asintóticamente óptimo. Sin embargo, en muestras finitas, el algoritmo sufre la maldición de la dimensionalidad: a medida que aumenta el número de características, el volumen del espacio crece exponencialmente y los puntos se vuelven escasos, lo que hace que las medidas de distancia sean menos significativas.
Ventajas y Desventajas
Una de las principales ventajas de k-NN es su simplicidad y la falta de una fase de entrenamiento. Se puede actualizar fácilmente añadiendo nuevos puntos de datos. También es eficaz para problemas de clases múltiples y puede capturar límites de decisión complejos. Sin embargo, tiene desventajas notables. El tiempo de predicción es lento porque requiere calcular distancias a todos los puntos de entrenamiento, lo que lo hace poco práctico para grandes conjuntos de datos sin optimización (por ejemplo, utilizando KD-trees o ball trees). Es sensible a características irrelevantes y datos ruidosos. El algoritmo también es sensible a la estructura local de los datos, lo que significa que los valores atípicos o las distribuciones de clases desequilibradas pueden sesgar los resultados. En distribuciones sesgadas, las clases mayoritarias dominan porque es más probable que aparezcan entre los k vecinos. La ponderación por distancia inversa o el uso de técnicas de abstracción pueden mitigar esto.
Variantes y Extensiones
Varias variantes abordan las limitaciones de k-NN. El k-NN ponderado asigna pesos a los vecinos según la distancia, de modo que los puntos más cercanos tienen más influencia. Los métodos de aprendizaje de métricas de distancia, como el vecino más cercano de margen amplio y el análisis de componentes de vecindad, aprenden una métrica de distancia personalizada para mejorar la precisión. El k-NN editado elimina puntos de entrenamiento ruidosos o mal clasificados para mejorar la generalización. El k-NN condensado reduce el tamaño del conjunto de entrenamiento manteniendo solo los puntos esenciales para la clasificación. El k-NN localmente adaptativo ajusta k según la densidad de la región alrededor del punto de consulta. Estas variantes se han aplicado en campos como el Machine learning y la Artificial intelligence para mejorar el rendimiento.
Aplicaciones
El algoritmo k-NN se utiliza en diversos dominios. En el reconocimiento de patrones, se aplica a la clasificación de imágenes y al reconocimiento de escritura a mano. En medicina, se utiliza para el diagnóstico basado en características del paciente. En finanzas, ayuda en la calificación crediticia y la detección de fraude. En los sistemas de recomendación, encuentra usuarios o elementos similares. En bioinformática, clasifica datos de expresión génica. Su simplicidad lo convierte en una línea base común para comparar modelos más complejos como las Neural network y el Deep learning.
Relación con Otros Métodos
k-NN es una forma de aprendizaje basado en instancias, distinto de los enfoques basados en modelos como las Neural network o las Support Vector Machine que construyen un modelo explícito durante el entrenamiento. También está relacionado con la estimación de densidad no paramétrica. En el contexto más amplio del Machine learning, k-NN se utiliza a menudo como punto de referencia. Ha influido en el desarrollo del hashing sensible a la localidad y la búsqueda aproximada del vecino más cercano, que se utilizan en sistemas a gran escala. Aunque los métodos modernos como el Deep learning han superado a k-NN en muchas tareas, k-NN sigue siendo valioso para conjuntos de datos pequeños y predicciones interpretables.
Consideraciones Prácticas
Al implementar k-NN, surgen varios problemas prácticos. El valor de k se elige típicamente mediante validación cruzada. A menudo se utilizan valores impares de k para evitar empates en la clasificación binaria. El escalado de características es esencial. Estructuras de datos eficientes como los KD-trees pueden acelerar la búsqueda del vecino más cercano, pero se degradan en altas dimensiones. Para conjuntos de datos muy grandes, son necesarios métodos aproximados. El uso de memoria del algoritmo es proporcional al tamaño del conjunto de entrenamiento, lo que puede ser una limitación. En aplicaciones modernas, k-NN a veces se combina con otros algoritmos, como usarlo como clasificador final sobre incrustaciones aprendidas de una Neural network.
Véase También
- Machine learning
- Artificial intelligence
- Neural network
- Deep learning
- Stanford AI Lab
- MIT CSAIL
- Carnegie Mellon University
- BAIR (Berkeley AI Research)
- Xerox PARC
- Thomas G. Dietterich
- Michael I. Jordan
- Daphne Koller
- Anima Anandkumar
- Samy Bengio
- Joshua Tenenbaum
- Brendan Lake
- Melanie Mitchell
- Aaron Courville
- Alexei Efros
- Ali Rahimi