El algoritmo de los k vecinos más cercanos (k-NN) es un método de aprendizaje no paramétrico y basado en instancias utilizado para clasificación y regresión. En ambos casos, la entrada consiste en los k ejemplos de entrenamiento más cercanos en un espacio de características. La salida depende de si k-NN se utiliza para clasificación o regresión: en clasificación, la salida es una pertenencia a una clase, determinada por un voto mayoritario entre los k vecinos más cercanos; en regresión, la salida es el promedio (o promedio ponderado) de los valores de los k vecinos más cercanos. k-NN es un tipo de aprendizaje perezoso, donde la función solo se aproxima localmente, y todo el cálculo se difiere hasta la evaluación de la función. Debido a que depende de cálculos de distancia, el algoritmo es sensible a la estructura local de los datos y a la elección de la métrica de distancia.
El algoritmo fue desarrollado por primera vez en 1951 por Evelyn Fix y Joseph Hodges en la Escuela de Medicina de Aviación de la Fuerza Aérea de los Estados Unidos, originalmente como una técnica de clasificación no paramétrica. Posteriormente fue ampliado y formalizado por Thomas Cover y Peter Hart en 1967, quienes establecieron sus límites de error asintóticos. Desde entonces, k-NN se ha convertido en una herramienta fundamental en aprendizaje automático, reconocimiento de patrones y minería de datos, utilizándose a menudo como referencia para modelos más complejos.
Cómo Funciona
Dado un punto de consulta, el algoritmo calcula la distancia (típicamente euclidiana, Manhattan o Minkowski) a cada ejemplo de entrenamiento. Luego selecciona los k ejemplos de entrenamiento con las distancias más pequeñas. Para clasificación, la etiqueta predicha es la más frecuente entre estos k vecinos. Para regresión, el valor predicho es la media de los valores objetivo de los vecinos. La elección de k es crítica: un k pequeño (por ejemplo, 1) conduce a una alta varianza y sensibilidad al ruido, mientras que un k grande puede suavizar patrones locales, aumentando el sesgo. La práctica común es seleccionar k mediante validación cruzada, utilizando a menudo valores impares para clasificación binaria para evitar empates.
El algoritmo también requiere una métrica de distancia. La distancia euclidiana es estándar para características continuas, pero para datos de alta dimensión o categóricos, se pueden utilizar otras métricas como la distancia de Hamming o la similitud del coseno. El escalado de características (por ejemplo, normalización o estandarización) es esencial porque las características con rangos más grandes dominan el cálculo de distancia.
Propiedades y Variantes
k-NN es no paramétrico, lo que significa que no hace suposiciones fuertes sobre la distribución subyacente de los datos. También está basado en instancias, almacenando todo el conjunto de entrenamiento y utilizándolo directamente en el momento de la predicción. Esto hace que el entrenamiento sea trivial (esencialmente solo almacenar datos), pero la predicción es computacionalmente costosa, con una complejidad temporal de O(nd) por consulta, donde n es el número de muestras de entrenamiento y d es el número de características.
Varias variantes abordan estas limitaciones. El k-NN ponderado asigna mayor influencia a los vecinos más cercanos, utilizando a menudo pesos de distancia inversa. La regresión localmente ponderada ajusta un modelo lineal dentro de la vecindad. Para conjuntos de datos grandes, las técnicas de búsqueda aproximada del vecino más cercano, como los árboles k-d, los árboles de bolas o el hashing sensible a la localidad, reducen el costo de búsqueda. En dimensiones altas, la maldición de la dimensionalidad degrada el rendimiento, ya que las distancias se vuelven menos discriminativas; a menudo se aplica reducción de dimensionalidad o selección de características.
Aplicaciones
El algoritmo se utiliza ampliamente en campos como visión por computadora para clasificación de imágenes, procesamiento de lenguaje natural para categorización de texto y bioinformática para análisis de expresión génica. Aparece en sistemas de recomendación, donde encuentra usuarios o elementos con preferencias similares. En finanzas, se utiliza para la calificación crediticia y la detección de fraude. Su simplicidad e interpretabilidad lo convierten en una primera opción común para el análisis exploratorio y como punto de referencia frente a modelos más complejos como redes neuronales.
Fortalezas y Limitaciones
Las principales fortalezas de k-NN son su simplicidad, facilidad de implementación y efectividad en conjuntos de datos pequeños a medianos con dimensionalidad baja a moderada. No requiere fase de entrenamiento, lo que lo hace adecuado para el aprendizaje incremental. Sin embargo, sus limitaciones incluyen un alto uso de memoria (almacenar todos los datos de entrenamiento), tiempo de predicción lento, sensibilidad a características irrelevantes y ruido, y un rendimiento deficiente en espacios de alta dimensión. También asume que todas las características son igualmente importantes, lo que rara vez es cierto en la práctica.
Relación con Otros Métodos
k-NN se compara a menudo con otros métodos no paramétricos como los árboles de decisión y las máquinas de vectores de soporte. Es una técnica fundamental en aprendizaje automático y se enseña frecuentemente junto con los planes de estudio de inteligencia artificial. Sus principios sustentan métodos más avanzados como las técnicas de aumento de datos que generan vecinos sintéticos, y se utiliza en aprendizaje curricular como una forma de ordenar los ejemplos de entrenamiento por dificultad. En la práctica moderna, k-NN se utiliza a veces como una capa final en modelos de aprendizaje profundo para el aprendizaje de métricas, donde las incrustaciones aprendidas se comparan mediante la búsqueda del vecino más cercano.
Véase También
- aprendizaje automático
- inteligencia artificial
- aumento de datos
- aprendizaje curricular
- funciones de pérdida
Referencias
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.