18 · Regresión KNN + aceleración con KD-tree / Ball-tree
Promedia los k objetivos más cercanos para regresión, luego usa KD-trees y Ball-trees para convertir búsquedas O(n) en O(log n) — haciendo KNN práctico en datasets reales.
La regresión KNN promedia los objetivos de los k vecinos más cercanos — y los KD-trees / Ball-trees aceleran las búsquedas O(n) a O(log n).
Sin esto:
Sin la aceleración basada en árboles, KNN es demasiado lento para usar en cualquier dataset más grande que un juguete.
La regresión KNN extiende la idea de clasificación a objetivos continuos. Para un nuevo punto de consulta x:
- Encuentra los K puntos de entrenamiento más cercanos por distancia.
- Devuelve el valor medio de sus objetivos como predicción: ŷ = (1/K) Σ yᵢ
Sin línea, sin polinomio, sin función explícita — solo promediado local. Esto hace que la regresión KNN sea un estimador no paramétrico y suave por tramos.
Votación uniforme vs ponderada por distancia
Con pesos uniformes (default), todos los K vecinos contribuyen por igual. Con ponderación por distancia, los vecinos más cercanos cuentan más:
wᵢ = 1 / d(x, xᵢ) → ŷ = Σ wᵢ yᵢ / Σ wᵢ
El cuello de botella de fuerza bruta
Escanear todos los n puntos de entrenamiento para cada consulta es O(n·d). Para n = 100 000 y d = 20, una sola consulta requiere 2 millones de cálculos de distancia — impracticable para grandes datasets.
KD-trees
Un KD-tree divide recursivamente el espacio de características a lo largo de hiperplanos alineados con los ejes. Tiempo de construcción: O(n log n). Tiempo de consulta: O(log n) para datos de baja dimensión. Se degrada a O(n) cuando d > ~20.
Ball-trees
Los Ball-trees dividen los datos en hiperesfera anidadas. Son más costosos de construir pero mantienen su tiempo O(log n) en dimensiones más altas o con métricas no euclidianas.
Selección automática de sklearn
algorithm='auto' elige el mejor algoritmo según las dimensiones de entrada. Raramente necesitas configurarlo manualmente.
Python (in browser)
La regresión KNN con k=5 predice la media de los 5 objetivos de entrenamiento más cercanos. El resultado es una curva suave por tramos (no una función paramétrica). Nota que sigue bien el verdadero sin(x) en el centro (datos de entrenamiento densos) pero se desvía en los bordes donde hay menos puntos.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
La votación ponderada por distancia (`weights='distance'`) asigna peso wᵢ = 1/dᵢ — los puntos justo al lado de una muestra de entrenamiento se ajustan exactamente al objetivo de esa muestra. En entornos muy ruidosos, la ponderación uniforme puede ser más robusta.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
En d=10 (muy por debajo del umbral de ~20 dimensiones), el KD-tree logra aproximadamente 5–15× de aceleración sobre la fuerza bruta. La aceleración proviene de podar subárboles: si el punto más cercano en el cuadro delimitador de un subárbol es más lejano que el K-ésimo vecino más cercano actual, todo el subárbol se omite.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Para sistemas de recomendación en línea o búsqueda semántica a escala (n > 1M, d = 768 de embeddings), ninguno de los algoritmos de sklearn es suficientemente rápido — necesitas librerías de NN aproximado como FAISS o HNSW que intercambian una pequeña pérdida de precisión por una aceleración de 100–1000×.
La regresión KNN con k=1 producirá predicciones que son:
- La regresión KNN predice ŷ = media(y de los K vecinos más cercanos). `weights='distance'` da predicciones más suaves al ponderar más los vecinos más cercanos.
- Los KD-trees dividen el espacio a lo largo de planos alineados con los ejes — consultas O(log n) para d < 20. Los Ball-trees usan hiperesfera — mejores para d ≥ 20 o métricas no euclidianas.
- `algorithm='auto'` en sklearn selecciona el backend correcto automáticamente; casi nunca necesitas anularlo.
- Para producción a escala (n > 100k), reemplaza el KNN de sklearn con librerías de NN aproximado (FAISS, HNSW, Annoy) para lograr inferencia de submilisegundo.
Recuperación de imágenes (encontrar imágenes similares mediante FAISS, que es KNN aproximado); recomendación (usuarios/ítems similares); predicción de precios en bienes raíces ('ventas comparables' es literalmente regresión KNN).
Si lo quitas: Muchos sistemas de recomendación y recuperación no se pueden construir — todos son KNN en el fondo.