K-Nearest Neighbors (KNN)

K vecinos más cercanos (KNN) es un algoritmo de aprendizaje supervisado que predice la etiqueta de un ejemplo nuevo a partir de los k ejemplos etiquetados más cercanos: para la clasificación, se usa el voto mayoritario de esos vecinos; para la regresión, su media. KNN es no paramétrico y «perezoso»: no aprende pesos, simplemente almacena los datos de entrenamiento y realiza todo el trabajo cuando se solicita una predicción. Evelyn Fix y Joseph Hodges presentaron el método en 1951, y en 1967 Thomas Cover y Peter Hart demostraron que, con datos ilimitados, la regla del vecino más cercano tiene como máximo el doble de tasa de error que el mejor clasificador posible. La misma búsqueda de vecinos más cercanos se ejecuta ahora a gran escala en bases de datos vectoriales y sistemas de recuperación de imágenes que comparan incrustaciones de redes neuronales.

Cómo hace predicciones KNN#

Para cada punto de consulta, KNN ejecuta tres pasos:

1. Medir la distancia: Calcula la distancia entre el punto de consulta y cada ejemplo almacenado. La distancia euclídea es la opción predeterminada; las distancias de Manhattan y Minkowski son alternativas habituales, y la similitud del coseno es la opción estándar para las incrustaciones, en las que la dirección de un vector contiene su significado.
2. Seleccionar los vecinos: Conserva los k ejemplos con las distancias más pequeñas.
3. Combinar sus etiquetas: En clasificación, se elige la clase más frecuente entre los vecinos; en regresión, se calcula la media de sus valores. Con ponderación por distancia (weights="distance" en scikit-learn), los vecinos más cercanos tienen más peso.

Todas las características contribuyen a la distancia, por lo que las de mayor escala predominan: los ingresos en euros eclipsarían la edad en años. Por eso, las canalizaciones de KNN estandarizan primero las características o comparan incrustaciones de un modelo de extracción de características, para que cada dimensión contribuya en una escala comparable.

Cómo elegir k#

El valor de k determina el equilibrio entre el sobreajuste y el infraajuste. Con k = 1, cada punto de entrenamiento, incluidos los ruidosos y mal etiquetados, reclama su propia región, y el límite de decisión se vuelve irregular. Con una k muy grande, cada voto llega muy lejos del punto de consulta y difumina los límites reales entre clases. Para dos clases, una k impar evita los empates, y la validación cruzada es la forma estándar de elegir k. En el ruidoso conjunto de datos de dos lunas de scikit-learn, el compromiso se aprecia en tres valores:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Con k = 1, el clasificador memoriza sus puntos de entrenamiento y obtiene 1.00 en ellos y 0.83 en los puntos reservados para evaluación. Con k = 15, obtiene 0.90 y 0.89, el mejor resultado de prueba de los tres; con k = 300, casi la mitad de los 700 puntos de entrenamiento, suaviza el límite hasta que ambas puntuaciones bajan a 0.84 y 0.81.

Cómo acelerar la búsqueda de vecinos#

Una búsqueda por fuerza bruta compara la consulta con los n puntos almacenados en d dimensiones, por lo que cada predicción cuesta del orden de n × d operaciones y la memoria crece con el conjunto de datos. Las estructuras de partición espacial, como los árboles k-d y los árboles de bolas, omiten la mayoría de las comparaciones en dimensiones bajas; algorithm="auto" de scikit-learn elige entre fuerza bruta, árbol k-d y árbol de bolas. En dimensiones altas, la maldición de la dimensionalidad hace que las distancias entre puntos sean casi iguales, la poda del árbol deja de ser rentable y los sistemas grandes pasan a índices aproximados de vecinos más cercanos (ANN), como los grafos HNSW y los índices de archivo invertido (IVF) con cuantización de productos, implementados en bibliotecas como FAISS. Estos índices devuelven la mayoría de los vecinos más cercanos reales comparando la consulta con una pequeña fracción de los vectores almacenados:

KNN frente a métodos relacionados#

• Agrupamiento k-means: Un algoritmo no supervisado que agrupa puntos sin etiquetar en k grupos alrededor de centroides aprendidos. La letra compartida en los nombres es una coincidencia: en k-means, k cuenta los grupos.
• Búsqueda vectorial: La forma de recuperación de la misma operación: devuelve los elementos almacenados más cercanos a una incrustación de consulta, normalmente mediante un índice aproximado, y la aplicación utiliza esos elementos directamente.
• Máquinas de vectores de soporte y regresión logística: Modelos paramétricos que aprenden un límite de decisión durante el entrenamiento, por lo que el coste de predicción permanece constante a medida que crece el conjunto de entrenamiento.

Aplicaciones en el mundo real#

• Sistemas de recomendación: El filtrado colaborativo basado en elementos recomienda productos cuyos vectores de valoración o compra están más cerca de los de los elementos que ya le han gustado a un usuario.
• Detección de anomalías: La distancia de un punto a su k-ésimo vecino más cercano sirve como puntuación de anomalía, por lo que destacan las transacciones o lecturas de sensores alejadas de todos los ejemplos normales.
• Imputación de valores ausentes: KNNImputer de scikit-learn rellena cada valor ausente con la media de esa característica en las k filas más similares.
• Recuperación de imágenes y reidentificación: Los sistemas comparan la incrustación de una imagen con una galería para encontrar el mismo producto, rostro o persona vistos por otra cámara. La solución de búsqueda por similitud de Ultralytics genera incrustaciones de una carpeta de imágenes con CLIP de OpenAI, calcula la similitud del coseno entre cada imagen indexada y una consulta de texto como «coche rojo» mediante una búsqueda exacta por fuerza bruta y devuelve las imágenes más cercanas, hasta 30 de forma predeterminada.