Phase 02 - Lesson 06

K-Vecinos más cercanos y distancias

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Almacena todo. Predice mirando a tus vecinos. El algoritmo más simple que realmente funciona.

Tipo: Construcción Idioma: Python Requisitos previos: Fase 1 (Lección 14 Normas y Distancias) Tiempo: ~90 minutos

Objetivos de aprendizaje

• Implementar clasificación y regresión KNN desde cero con K configurable y votación ponderada por distancia
• Compare las métricas de distancia L1, L2, coseno y Minkowski y seleccione la adecuada para un tipo de datos determinado
• Explicar la maldición de la dimensionalidad y demostrar por qué KNN se degrada en espacios de alta dimensión
• Cree un árbol KD para una búsqueda eficiente del vecino más cercano y analice cuándo supera la fuerza bruta.

El problema

Tienes un conjunto de datos. Llega un nuevo punto de datos. Necesita clasificarlo o predecir su valor. En lugar de aprender parámetros de los datos (como regresión lineal o SVM), simplemente encuentra los K puntos de entrenamiento más cercanos al nuevo punto y déjalos votar.

Estos son los vecinos más cercanos. No hay fase de entrenamiento. No hay parámetros que aprender. No hay función de pérdida para minimizar. Almacena todo el conjunto de entrenamiento y calcula las distancias en el momento de la predicción.

Suena demasiado simple para funcionar. Pero KNN es sorprendentemente competitivo para muchos problemas, especialmente con conjuntos de datos pequeños y medianos, y comprenderlo revela profundamente conceptos fundamentales: la elección de la métrica de distancia (conectándose con la Fase 1, Lección 14), la maldición de la dimensionalidad y la diferencia entre el aprendizaje perezoso y entusiasta.

KNN también aparece en todas partes en la IA moderna, solo que con nombres diferentes. Las bases de datos vectoriales realizan KNN búsquedas sobre incrustaciones. La generación de recuperación aumentada (RAG) encuentra los K fragmentos de documentos más cercanos. Los sistemas de recomendación encuentran usuarios o elementos similares. El algoritmo es el mismo. La escala y las estructuras de datos son diferentes.

El concepto

Cómo funciona KNN

Dado un conjunto de datos de puntos etiquetados y un nuevo punto de consulta:

1. Calcule la distancia desde la consulta hasta cada punto del conjunto de datos.
2. Ordenar por distancia
3. Toma los K puntos más cercanos.
4. Para clasificación: voto mayoritario entre los vecinos K
5. Para regresión: promedio (o promedio ponderado) de los valores de los K vecinos

graph TD
    Q["Query point ?"] --> D["Compute distances<br>to all training points"]
    D --> S["Sort by distance"]
    S --> K["Select K nearest"]
    K --> C{"Classification<br>or Regression?"}
    C -->|Classification| V["Majority vote"]
    C -->|Regression| A["Average values"]
    V --> P["Prediction"]
    A --> P

Ese es el algoritmo completo. Sin ajuste. Sin descenso de gradiente. Sin épocas.

Eligiendo K

K es el hiperparámetro único. Controla el equilibrio entre sesgo y varianza:

Un punto de partida común es K = sqrt(N) para un conjunto de datos de N puntos. Utilice K impar para la clasificación binaria para evitar empates.

graph LR
    subgraph "K=1 (overfitting)"
        A["Jagged boundary<br>follows every point"]
    end
    subgraph "K=15 (good)"
        B["Smooth boundary<br>captures true pattern"]
    end
    subgraph "K=N (underfitting)"
        C["Flat boundary<br>predicts majority class"]
    end
    A -->|"increase K"| B -->|"increase K"| C

Métricas de distancia

La función de distancia define lo que significa "cerca". Diferentes métricas producen diferentes vecinos, diferentes predicciones.

L2 (Euclidean) es el valor predeterminado. Distancia en línea recta.

d(a, b) = sqrt(sum((a_i - b_i)^2))

Sensible a la escala de características. Estandarice siempre las funciones antes de usar L2 con KNN.

L1 (Manhattan) suma diferencias absolutas. Más robusto a los valores atípicos que L2 porque no cuadra las diferencias.

d(a, b) = sum(|a_i - b_i|)

Distancia del coseno mide el ángulo entre vectores, ignorando la magnitud. Esencial para texto e incrustación de datos.

d(a, b) = 1 - (a . b) / (||a|| * ||b||)

Minkowski generaliza L1 y L2 con el parámetro p.

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: Manhattan
p=2: Euclidean
p->inf: Chebyshev (max absolute difference)

Qué métrica utilizar depende de los datos:

Ponderado KNN

El estándar KNN otorga el mismo peso a todos los K vecinos. Pero un vecino a una distancia de 0,1 debería importar más que uno a una distancia de 5,0.

Ponderado por distancia KNN pondera a cada vecino inversamente por la distancia:

weight_i = 1 / (distance_i + epsilon)

For classification: weighted vote
For regression:     weighted average = sum(w_i * y_i) / sum(w_i)

El épsilon evita la división por cero cuando un punto de consulta coincide exactamente con un punto de entrenamiento.

La ponderación KNN es menos sensible a la elección de K porque, independientemente, los vecinos distantes contribuyen muy poco.

La maldición de la dimensionalidad

KNN el rendimiento se degrada en dimensiones altas. Esta no es una preocupación vaga. Es un hecho matemático.

Problema 1: las distancias convergen. A medida que aumenta la dimensionalidad, la relación entre la distancia máxima y la distancia mínima se acerca a 1. Todos los puntos quedan igualmente "lejos" de la consulta.

In d dimensions, for random uniform points:

d=2:    max_dist / min_dist = varies widely
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

When all distances are nearly equal, "nearest" is meaningless.

Problema 2: el volumen explota. Para capturar K vecinos dentro de una fracción fija de los datos, necesita ampliar su radio de búsqueda para cubrir una fracción mucho mayor del espacio de características. El "barrio" en altas dimensiones abarca la mayor parte del espacio.

Problema 3: dominan las esquinas. En un hipercubo unitario en d dimensiones, la mayor parte del volumen se concentra cerca de las esquinas, no del centro. Una esfera inscrita en el cubo contiene una fracción del volumen que desaparece a medida que d crece.

Consecuencia práctica: KNN funciona bien hasta entre 20 y 50 funciones. Más allá de eso, necesita una reducción de dimensionalidad (PCA, UMAP, t-SNE) antes de aplicar KNN, o necesita usar estructuras de búsqueda basadas en árboles que exploten la dimensionalidad inferior intrínseca de los datos.

KD-trees: búsqueda rápida del vecino más cercano

La fuerza bruta KNN calcula la distancia desde la consulta hasta cada punto de entrenamiento. Eso es O(n * d) por consulta. Para conjuntos de datos grandes, esto es demasiado lento.

Un árbol KD divide recursivamente el espacio a lo largo de ejes de características. En cada nivel, se divide a lo largo de una dimensión en el valor mediano.

graph TD
    R["Split on x1 at 5.0"] -->|"x1 <= 5.0"| L["Split on x2 at 3.0"]
    R -->|"x1 > 5.0"| RR["Split on x2 at 7.0"]
    L -->|"x2 <= 3.0"| LL["Leaf: 3 points"]
    L -->|"x2 > 3.0"| LR["Leaf: 4 points"]
    RR -->|"x2 <= 7.0"| RL["Leaf: 2 points"]
    RR -->|"x2 > 7.0"| RRR["Leaf: 5 points"]

Para encontrar el vecino más cercano, recorra el árbol hasta la hoja que contiene la consulta, luego retroceda y verifique las particiones vecinas solo si pueden contener puntos más cercanos.

Tiempo medio de consulta: O(log n) para dimensiones bajas. Pero los árboles KD se degradan a O(n) en dimensiones altas (d > 20) porque el retroceso elimina cada vez menos ramas.

Árboles de bolas: mejores para dimensiones moderadas

Los árboles de bolas dividen los datos en hiperesferas anidadas en lugar de cuadros alineados con los ejes. Cada nodo define una bola (centro + radio) que contiene todos los puntos de ese subárbol.

Ventajas sobre los árboles KD:

• Trabaja mejor en dimensiones moderadas (hasta ~50)
• Manejar estructura no alineada con el eje.
• Los volúmenes delimitados más estrictos significan que se podan más ramas durante la búsqueda

Tanto los árboles KD como los árboles de bolas son algoritmos exactos. Para búsquedas verdaderamente a gran escala (millones de puntos, cientos de dimensiones), se utilizan en su lugar métodos aproximados del vecino más cercano (HNSW, IVF, cuantificación de productos). Estos se tratan en la Fase 1, Lección 14.

Aprendizaje perezoso versus aprendizaje ansioso

KNN aprende con pereza: no funciona en el momento del entrenamiento y todo funciona en el momento de la predicción. La mayoría de los demás algoritmos (regresión lineal, SVM, redes neuronales) aprenden con entusiasmo: realizan cálculos intensos en el momento del entrenamiento para construir un modelo compacto y luego las predicciones son rápidas.

El aprendizaje perezoso es ideal cuando:

• El conjunto de datos cambia con frecuencia (agregar/eliminar puntos sin volver a entrenar)
• Necesitas predicciones para muy pocas consultas.
• Quieres cero tiempo de entrenamiento
• El conjunto de datos es lo suficientemente pequeño como para que la búsqueda por fuerza bruta sea rápida.

KNN para regresión

En lugar de votación mayoritaria, KNN para la regresión promedia los valores objetivo de los K vecinos.

prediction = (1/K) * sum(y_i for i in K nearest neighbors)

Or with distance weighting:
prediction = sum(w_i * y_i) / sum(w_i)
where w_i = 1 / distance_i

KNN la regresión produce predicciones por partes constantes (o por partes suaves con ponderación). No puede extrapolar más allá del rango de los datos de entrenamiento. Si todos los objetivos de entrenamiento están entre 0 y 100, KNN nunca predecirá 200.

Constrúyelo

Paso 1: Funciones de distancia

Implemente distancias L1, L2, coseno y Minkowski. Estos se conectan directamente con la Lección 14 de la Fase 1.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

Paso 2: KNN clasificador y regresor

Cree el KNN completo con K configurable, métrica de distancia y ponderación de distancia opcional.

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

Paso 3: árbol KD para una búsqueda eficiente

Construya un árbol KD desde cero que se divida recursivamente en la mediana de cada dimensión.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # Recursively partition the data
        self.axis = depth % len(X[0])
        # Split on median of the current axis
        ...

    def query(self, point, k=1):
        # Traverse to leaf, then backtrack
        ...

Consulte code/knn.py para ver la implementación completa con todos los métodos auxiliares y demostraciones.

Paso 4: escalado de funciones

KNN requiere escalado de características porque las distancias son sensibles a las magnitudes de las características. Una característica que va de 0 a 1000 dominará una característica que va de 0 a 1.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

Úsalo

Con scikit-learn:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")

Scikit-learn utiliza automáticamente árboles KD o árboles de bolas cuando el conjunto de datos es lo suficientemente grande y la dimensionalidad lo suficientemente baja. Para datos de alta dimensión, se recurre a la fuerza bruta. Puedes controlar esto con el parámetro algorithm.

Para una búsqueda de vecino más cercano a gran escala (millones de vectores), utilice FAISS, Annoy o una base de datos de vectores:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

Ejercicios

1. Implemente la clasificación KNN en un conjunto de datos 2D con 3 clases. Trace el límite de decisión para K=1, K=5, K=15 y K=N. Observe la transición del sobreajuste al desajuste.

2. Genere 1000 puntos aleatorios en 2, 5, 10, 50, 100 y 500 dimensiones. Para cada dimensionalidad, calcule la relación entre la distancia máxima por pares y la distancia mínima por pares. Traza la relación versus la dimensionalidad para visualizar la maldición de la dimensionalidad.

3. Compare L1, L2 y la distancia del coseno para KNN en un problema de clasificación de texto (use vectores TF-IDF). ¿Qué métrica ofrece la mejor precisión? ¿Por qué el coseno tiende a ganar en el texto?

4. Implemente un árbol KD y mida el tiempo de consulta frente a la fuerza bruta para conjuntos de datos de 1k, 10k y 100k puntos en 2D, 10D y 50D. ¿En qué dimensionalidad el árbol KD deja de ser más rápido que la fuerza bruta?

5. Construya un regresor KNN ponderado para y = sin(x) + ruido. Compárelo con KNN no ponderado para K=3, 10, 30. Demuestre que la ponderación produce predicciones más fluidas, especialmente para K grande.

Términos clave

Lectura adicional

• Cover & Hart: Clasificación del patrón del vecino más cercano (1967): el documento fundamental KNN que demuestra que tiene una tasa de error como máximo el doble del Bayes óptimo
• Friedman, Bentley, Finkel: Un algoritmo para encontrar las mejores coincidencias en el tiempo esperado logarítmico (1977) - el artículo original del árbol KD
• Beyer et al.: ¿Cuándo tiene sentido el término "vecino más cercano"? (1999) - análisis formal de la maldición de la dimensionalidad para el vecino más cercano
• scikit-learn Documentación de vecinos más cercanos - guía práctica con selección de algoritmo
• FAISS: Una biblioteca para una búsqueda eficiente de similitudes - Biblioteca de Meta para una búsqueda aproximada del vecino más cercano a escala de mil millones