52  Vecinos más cercanos

El clasificador de \(k\) vecinos más cercanos (\(k\)-NN, k-nearest neighbors) es quizá la idea más antigua y más intuitiva del aprendizaje supervisado: para decidir la clase de un caso nuevo, se buscan los casos de entrenamiento más parecidos y se responde lo que diga la mayoría de ellos. Fue propuesto por Fix y Hodges (1951) como un método de discriminación «no paramétrico» y Cover y Hart (1967) demostraron que, con suficientes datos, su error nunca es mayor que el doble del mínimo posible.

\(k\)-NN no construye una fórmula ni un árbol: guarda los datos y difiere todo el trabajo al momento de predecir. Por eso se le llama aprendizaje perezoso (lazy learning) o basado en instancias. Esa simplicidad lo convierte en el mejor punto de partida para entender tres ideas que valen para todos los clasificadores: la importancia de la representación de los datos (qué significa «parecido»), el control de la complejidad con un hiperparámetro y los problemas que trae la alta dimensión.

52.1 Intuición: ¿quién compra un seguro?

Una aseguradora ofreció un seguro de gastos médicos a ocho clientes y registró su edad, su ingreso mensual en pesos y si compró el seguro.

Cliente	Edad	Ingreso ($)	¿Compró?
1	20	30 000	no
2	30	50 000	no
3	36	10 000	no
4	28	38 000	no
5	52	34 000	sí
6	56	60 000	sí
7	60	18 000	sí
8	46	55 000	sí

Tabla 52.1: Clientes de entrenamiento.

A simple vista, la edad separa las clases: todos los mayores de 45 compraron y ninguno de los menores. El ingreso no parece importar. Llega una clienta nueva de 54 años con un ingreso de 31 000 pesos. La respuesta de sentido común es «comprará». Veamos qué responde \(k\)-NN.

52.2 Construcción paso a paso

52.2.1 Paso 1. Distancias con las variables tal como vienen

La distancia euclidiana entre la clienta nueva \(\mathbf{q} = (54, 31\,000)\) y el cliente 1 es

\[ d(\mathbf{q}, \mathbf{x}_1) = \sqrt{(54 - 20)^2 + (31\,000 - 30\,000)^2} = \sqrt{1\,156 + 1\,000\,000} \approx 1\,000.6. \]

Repitiendo el cálculo para los ocho clientes y ordenando:

Orden	Cliente	\((\Delta \text{edad})^2\)	\((\Delta \text{ingreso})^2\)	Distancia	Clase
1	1	1 156	1 000 000	1 000.6	no
2	5	4	9 000 000	3 000.0	sí
3	4	676	49 000 000	7 000.0	no
4	7	36	169 000 000	13 000.0	sí

Tabla 52.2: Los cuatro vecinos más cercanos con las variables originales.

Con \(k = 3\) los vecinos son los clientes 1, 5 y 4: dos «no» contra un «sí». \(k\)-NN predice que no comprará. El problema está en las columnas centrales: la diferencia de edad aporta a lo más unos miles a la suma de cuadrados, mientras que la de ingreso aporta millones. La distancia es, en la práctica, la diferencia de ingresos; la edad, la única variable útil, no cuenta. Si el ingreso se hubiera registrado en miles de pesos la conclusión sería otra. Un clasificador cuya respuesta depende de las unidades de medida no es confiable.

52.2.2 Paso 2. Llevar las variables a una escala común

La solución es escalar las variables antes de medir distancias. Con la normalización min-max¹, cada variable se transforma a \([0, 1]\) con el mínimo y el máximo del entrenamiento:

¹ Otra opción es la estandarización, \(z = (x - \bar{x})/s\), que deja cada variable con media 0 y desviación estándar 1. Min-max garantiza el rango \([0, 1]\) pero es sensible a valores atípicos; la estandarización no acota el rango pero es más estable. Ambas se estudian en el capítulo de conversión de tipos.

\[ z = \frac{x - \min}{\max - \min}, \qquad z_{\text{edad}} = \frac{\text{edad} - 20}{60 - 20}, \qquad z_{\text{ingreso}} = \frac{\text{ingreso} - 10\,000}{60\,000 - 10\,000}. \]

Para la clienta nueva: \(z_{\text{edad}} = 34/40 = 0.85\) y \(z_{\text{ingreso}} = 21\,000/50\,000 = 0.42\).

Cliente	1	2	3	4	5	6	7	8	Nueva
\(z_{\text{edad}}\)	0.00	0.25	0.40	0.20	0.80	0.90	1.00	0.65	0.85
\(z_{\text{ingreso}}\)	0.40	0.80	0.00	0.56	0.48	1.00	0.16	0.90	0.42

Tabla 52.3: Variables escaladas a [0, 1].

52.2.3 Paso 3. Distancias en la escala común

Ahora, por ejemplo, \(d(\mathbf{q}, \mathbf{x}_5) = \sqrt{(0.85-0.80)^2 + (0.42-0.48)^2} = \sqrt{0.0025 + 0.0036} \approx 0.078\). Todas las distancias, ordenadas:

Orden	Cliente	Distancia	Clase	Peso \(1/d\)
1	5	0.078	sí	12.80
2	7	0.300	sí	3.33
3	8	0.520	sí	1.92
4	6	0.582	sí	1.72
5	3	0.616	no	1.62
6	4	0.665	no	1.50
7	2	0.710	no	1.41
8	1	0.850	no	1.18

Tabla 52.4: Distancias euclidianas en la escala [0, 1].

Con \(k = 3\) los vecinos son 5, 7 y 8: tres «sí». Ahora \(k\)-NN predice que comprará, con una proporción de votos de \(3/3\). Nada cambió en los datos; solo la manera de medir el parecido.

52.2.4 Paso 4. El efecto de \(k\)

La proporción de vecinos de cada clase es una estimación de la probabilidad de la clase:

\(k\)	Votos «sí»	Votos «no»	\(\hat{p}(\text{sí} \mid \mathbf{q})\)	Predicción
1	1	0	1.00	sí
3	3	0	1.00	sí
5	4	1	0.80	sí
7	4	3	0.57	sí
8	4	4	0.50	empate

Tabla 52.5: Votos según el número de vecinos.

A medida que \(k\) crece se consultan clientes cada vez menos parecidos y la estimación se acerca a la proporción global de la clase (\(4/8\)). Con \(k = n\) el clasificador ignora a la clienta y responde siempre la clase mayoritaria: es la referencia del capítulo anterior. En el otro extremo, con \(k = 1\), la respuesta depende de un solo cliente, que podría ser una excepción.

52.2.5 Paso 5. Voto ponderado por la distancia

El voto uniforme trata igual al cliente 5, a distancia 0.078, que al cliente 3, a 0.616. Una variante natural pondera cada voto por el inverso de la distancia. Con \(k = 7\):

\[ \text{peso}(\text{sí}) = 12.80 + 3.33 + 1.92 + 1.72 = 19.78, \qquad \text{peso}(\text{no}) = 1.62 + 1.50 + 1.41 = 4.54, \]

de modo que \(\hat{p}(\text{sí} \mid \mathbf{q}) = 19.78 / (19.78 + 4.54) \approx 0.81\), frente al \(0.57\) del voto uniforme. La ponderación hace que el resultado sea menos sensible a la elección de \(k\), porque los vecinos lejanos casi no cuentan.

52.3 Formalización

52.3.1 La regla de \(k\)-NN

Sea \(\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n\) el conjunto de entrenamiento y \(d\) una función de distancia. Para un punto \(\mathbf{x}\), sea \(N_k(\mathbf{x})\) el conjunto de índices de sus \(k\) vecinos más cercanos. La estimación de la probabilidad de la clase \(c\) y la predicción son

\[ \hat{p}(c \mid \mathbf{x}) = \frac{1}{k} \sum_{i \in N_k(\mathbf{x})} \mathbb{1}[y_i = c], \qquad \hat{y}(\mathbf{x}) = \arg\max_{c} \, \hat{p}(c \mid \mathbf{x}). \tag{52.1}\]

Es decir, \(k\)-NN imita al clasificador de Bayes (\(\arg\max_c p(c \mid \mathbf{x})\)) sustituyendo la probabilidad verdadera por una proporción local. Con pesos \(w_i = 1/d(\mathbf{x}, \mathbf{x}_i)\) la versión ponderada es

\[ \hat{p}_w(c \mid \mathbf{x}) = \frac{\sum_{i \in N_k(\mathbf{x})} w_i \, \mathbb{1}[y_i = c]}{\sum_{i \in N_k(\mathbf{x})} w_i}. \tag{52.2}\]

Si \(\mathbf{x}\) coincide exactamente con un punto de entrenamiento (\(d = 0\)), se usa solo ese punto. En regresión, \(k\)-NN predice el promedio (simple o ponderado) de las respuestas de los vecinos, \(\hat{f}(\mathbf{x}) = \frac{1}{k}\sum_{i \in N_k(\mathbf{x})} y_i\).

Empates. En clasificación binaria se recomienda un \(k\) impar. Con varias clases pueden quedar empates aun con \(k\) impar; scikit-learn los resuelve eligiendo la clase que aparece primero en el orden de las etiquetas, y otra opción común es usar la clase del vecino más cercano entre las empatadas.

52.3.2 Distancias

La familia de Minkowski de orden \(s \ge 1\) generaliza las distancias más usadas:

\[ d_s(\mathbf{x}, \mathbf{z}) = \Big(\sum_{j=1}^{p} |x_j - z_j|^s\Big)^{1/s}. \tag{52.3}\]

\(s\)	Nombre	Fórmula	Forma de la «bola» en 2D
1	Manhattan	\(\sum_j \lvert x_j - z_j \rvert\)	rombo
2	Euclidiana	\(\sqrt{\sum_j (x_j - z_j)^2}\)	círculo
\(\infty\)	Chebyshev	\(\max_j \lvert x_j - z_j \rvert\)	cuadrado

Tabla 52.6: Casos particulares de la distancia de Minkowski.

La «bola» es el conjunto de puntos a distancia menor que \(r\) de un centro; para \(k\)-NN es la forma del vecindario. Con Chebyshev, la clienta nueva tendría como tercer vecino al cliente 3 (distancia \(\max(0.45, 0.42) = 0.45\)) en lugar del 8: la métrica cambia quiénes son los vecinos.

Otras distancias útiles:

• Mahalanobis, \(d_M(\mathbf{x}, \mathbf{z}) = \sqrt{(\mathbf{x} - \mathbf{z})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \mathbf{z})}\), con \(\boldsymbol{\Sigma}\) la matriz de covarianza: corrige a la vez escala y correlación entre variables.
• Hamming, la proporción de atributos categóricos distintos, para datos como los del problema de tenis.
• Gower, que combina variables numéricas y categóricas en una sola distancia².
• Coseno, \(1 - \frac{\mathbf{x}^\top\mathbf{z}}{\|\mathbf{x}\|\|\mathbf{z}\|}\), habitual para textos representados como vectores de frecuencias, donde importa la dirección y no la longitud.

² La distancia de Gower promedia, variable por variable, una disimilitud entre 0 y 1: para numéricas, la diferencia absoluta dividida entre el rango; para categóricas, 0 si coinciden y 1 si no. Permite aplicar \(k\)-NN a tablas mixtas sin codificación one-hot.

52.3.3 Escalamiento: parte del modelo

Como mostró el Paso 1, \(k\)-NN no es invariante a las unidades. Las dos opciones más comunes son la normalización min-max y la estandarización \(z = (x - \bar{x})/s\). En ambos casos los parámetros (\(\min\), \(\max\), \(\bar{x}\), \(s\)) se calculan solo con el entrenamiento y se aplican a los puntos nuevos; por eso el escalador forma parte del modelo y debe ir dentro de un pipeline. El capítulo de conversión de tipos y escalamiento tiene un laboratorio dedicado a este efecto.

Escalar es una forma de elegir la importancia de cada variable. Una variable irrelevante escalada a \([0, 1]\) pesa en la distancia lo mismo que una muy informativa, y añade ruido; por eso \(k\)-NN se beneficia mucho de una buena selección de variables.

52.3.4 Garantías teóricas

Sea \(R^{*}\) el error de Bayes. Cover y Hart (1967) demostraron que, cuando \(n \to \infty\), el error del vecino más cercano, \(R_1\), cumple con \(K\) clases

\[ R^{*} \le R_1 \le R^{*}\Big(2 - \frac{K}{K-1}R^{*}\Big) \le 2R^{*}. \tag{52.4}\]

Con infinitos datos, el vecino más cercano está tan próximo que tiene casi la misma distribución de clases que el punto consultado; el 1-NN acierta cuando ambos «sortean» la misma clase. Además, si \(k \to \infty\) y \(k/n \to 0\), \(k\)-NN es consistente: su error converge a \(R^{*}\) (Stone 1977). La condición \(k/n \to 0\) pide que el vecindario tenga cada vez más puntos sin dejar de ser local.

52.4 Laboratorio: el vecindario de \(k\)-NN

Arrastra la clienta nueva (el rombo) por el plano, cambia \(k\), la distancia y el tipo de voto. El contorno discontinuo es la «bola» que contiene a los \(k\) vecinos: círculo, rombo o cuadrado según la métrica. El estado inicial reproduce la Tabla 52.4.

Laboratorio · Vecinos más cercanos

¿Quiénes son los vecinos y cuánto vale su voto?

Arrastra el rombo (o haz clic en el plano) para mover el punto consultado. Las regiones sombreadas muestran la predicción en cada punto del plano con la configuración actual.

Datos

Distancia

Voto

Vecinos k:

Punto consultado

Predicción

Probabilidad estimada

Radio del vecindario

Plano escalado a [0, 1]

Distancias al punto consultado

Guía del laboratorio.

1. Comprueba el estado inicial contra la Tabla 52.4: vecinos, distancias y pesos.
2. Predice antes de mover: con distancia de Chebyshev y \(k = 3\), ¿quién será el tercer vecino? Compruébalo y observa la forma cuadrada del vecindario.
3. Sube \(k\) a 7 con voto uniforme y anota la probabilidad. Cambia a voto ponderado. ¿Por qué sube tanto?
4. Con \(k = 8\) y voto uniforme, arrastra el punto por todo el plano. ¿Por qué el color de fondo no cambia? ¿Qué pasa al activar el voto ponderado?
5. Cambia a Tres clases con \(k = 1\) y observa la frontera alrededor de los puntos aislados (por ejemplo, el punto 19, de la clase B, metido entre los de la clase A). Sube \(k\) a 9: ¿qué le pasa a la isla?
6. Busca un punto donde, con \(k = 4\) y voto uniforme, haya empate entre dos clases. ¿Cómo lo resuelve el voto ponderado?

52.5 Elegir \(k\)

\(k\) es el hiperparámetro que controla la complejidad de \(k\)-NN, como mostró el laboratorio del capítulo anterior: \(k\) pequeño da fronteras irregulares (poco sesgo, mucha varianza); \(k\) grande, fronteras suaves (más sesgo, menos varianza). En la práctica:

• se elige con validación cruzada, nunca con el conjunto de prueba;
• en problemas binarios se prefieren valores impares;
• una heurística inicial razonable es \(k \approx \sqrt{n}\), que después se refina con validación;
• el voto ponderado reduce la sensibilidad a \(k\) y suele permitir valores más grandes.

Una propiedad conveniente de \(k\)-NN es que la validación cruzada dejando uno fuera es barata: predecir el punto \(i\) sin él equivale a buscar sus \(k\) vecinos excluyéndolo, sin volver a «entrenar» nada.

52.6 La maldición de la dimensionalidad

\(k\)-NN confía en que haya puntos de entrenamiento cerca de cualquier punto nuevo. En pocas dimensiones es razonable; en muchas, deja de serlo. Bellman (1961) llamó a este fenómeno la maldición de la dimensionalidad, y tiene dos caras.

Los vecindarios dejan de ser locales. Supongamos datos uniformes en el hipercubo \([0, 1]^p\). Un subcubo de lado \(e\) contiene, en promedio, una fracción \(e^p\) de los datos. Para capturar una fracción \(r\) hay que tomar un lado

\[ e_p(r) = r^{1/p}. \tag{52.5}\]

Con \(r = 0.10\): en \(p = 1\) basta \(e = 0.10\); en \(p = 2\), \(e = 0.32\); en \(p = 10\), \(e = 0.79\); y en \(p = 100\), \(e = 0.977\). Para reunir solo el 10 % de los datos hay que abarcar casi todo el rango de cada variable (Hastie et al. 2009). El «vecino más cercano» ya no es parecido.

Las distancias se concentran. Al crecer \(p\), la distancia al vecino más cercano y al más lejano se vuelven casi iguales, de modo que el cociente \(d_{\min}/d_{\max}\) tiende a 1 (Beyer et al. 1999). Si todos los puntos están a la misma distancia, «el más cercano» es casi arbitrario.

La consecuencia práctica es que \(k\)-NN necesita pocas variables relevantes. Antes de usarlo conviene seleccionar variables o reducir la dimensión (por ejemplo con PCA), y desconfiar de representaciones con cientos de columnas one-hot.

Laboratorio · Maldición de la dimensionalidad

¿Sigue habiendo un vecino «cercano» en 100 dimensiones?

Se generan n puntos uniformes en el hipercubo [0, 1]^p y se miden sus distancias euclidianas a un punto consultado, también aleatorio. El histograma muestra cada distancia dividida entre la distancia promedio.

Dimensión p: Número de puntos n:

Muestra

Distancia mínima

Distancia máxima

Cociente d_min/d_max

Lado para capturar el 10 %

Distancias relativas (d / promedio)

distanciasvecino más cercanomás lejano

Concentración según la dimensión

d_min/d_max (simulado)lado e_p(0.1) = 0.1^1/pp actual

Guía del laboratorio.

1. Con \(p = 2\), observa el histograma: ¿qué tan lejos está el vecino más cercano en comparación con el promedio?
2. Predice antes de mover: en \(p = 100\), ¿el cociente \(d_{\min}/d_{\max}\) estará más cerca de 0 o de 1? Compruébalo.
3. En \(p = 100\) sube \(n\) a 2000. ¿Cuánto mejora el cociente? ¿Cuántos puntos crees que harían falta para recuperar la situación de \(p = 2\)?
4. Explica con la curva verde por qué un vecindario que contiene el 10 % de los datos deja de ser «local» en alta dimensión.

52.7 Costo computacional y búsqueda eficiente

Entrenar \(k\)-NN cuesta casi nada: basta guardar los datos. Predecir es caro: con búsqueda exhaustiva (fuerza bruta), cada consulta calcula \(n\) distancias de \(p\) componentes, es decir \(O(np)\), y necesita tener en memoria todo el conjunto de entrenamiento. Con millones de casos y predicciones en tiempo real esto se vuelve un problema. Hay tres familias de soluciones:

• Estructuras de búsqueda exacta. Los árboles k-d (Friedman et al. 1977) y los ball trees organizan los datos jerárquicamente y descartan regiones completas que no pueden contener al vecino. Si un nodo tiene centro \(\mathbf{M}_p\) y radio \(r_p\), y la mejor distancia encontrada hasta ahora es \(B\), la desigualdad del triángulo garantiza que el nodo puede descartarse cuando \(d(\mathbf{x}, \mathbf{M}_p) - r_p > B\) (Fukunaga y Narendra 1975). Funcionan muy bien en dimensión baja o moderada; en dimensión alta degeneran hacia la fuerza bruta.
• Búsqueda aproximada. Bibliotecas como FAISS o los grafos HNSW aceptan devolver un vecino casi más cercano a cambio de consultas miles de veces más rápidas. Son la base de los buscadores semánticos y de los sistemas de recomendación modernos.
• Reducir el conjunto de entrenamiento. La edición de Wilson (1972) elimina los puntos que sus propios vecinos clasifican mal (ruido y casos en zonas de traslape), lo que suaviza la frontera. La condensación de Hart (1968) conserva solo los puntos necesarios para que 1-NN tome las mismas decisiones: empieza con un punto y agrega cada caso que el subconjunto actual clasifica mal.

52.8 Implementación en Python

52.8.1 El ejemplo manual con scikit-learn

KNeighborsClassifier implementa la Ecuación 52.1. Lo usamos dos veces: con las variables originales y dentro de un pipeline que primero aplica MinMaxScaler.

import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import MinMaxScaler
from sklearn.pipeline import make_pipeline

seguro = pd.DataFrame({
    "edad":    [20, 30, 36, 28, 52, 56, 60, 46],
    "ingreso": [30_000, 50_000, 10_000, 38_000, 34_000, 60_000, 18_000, 55_000],
    "compra":  ["no", "no", "no", "no", "sí", "sí", "sí", "sí"],
}, index=range(1, 9))
X, y = seguro[["edad", "ingreso"]], seguro["compra"]
nueva = pd.DataFrame({"edad": [54], "ingreso": [31_000]})

crudo = KNeighborsClassifier(n_neighbors=3).fit(X, y)
escalado = make_pipeline(MinMaxScaler(), KNeighborsClassifier(n_neighbors=3)).fit(X, y)

for nombre, modelo, Xq in [("sin escalar", crudo, nueva),
                           ("min-max", escalado[-1], escalado[0].transform(nueva))]:
    dist, idx = modelo.kneighbors(Xq)
    print(f"{nombre:>12}: vecinos {list(X.index[idx[0]])}, distancias {np.round(dist[0], 3)}")
print("\nPredicción sin escalar:", crudo.predict(nueva)[0])
print("Predicción con min-max:", escalado.predict(nueva)[0])

 sin escalar: vecinos [1, 5, 4], distancias [1000.578 3000.001 7000.048]
     min-max: vecinos [5, 7, 8], distancias [0.078 0.3   0.52 ]

Predicción sin escalar: no
Predicción con min-max: sí

La probabilidad estimada (predict_proba) para distintos valores de \(k\) y ambos tipos de voto reproduce la Tabla 52.5 y el Paso 5:

filas = []
for k in [1, 3, 5, 7, 8]:
    fila = {"k": k}
    for pesos in ["uniform", "distance"]:
        m = make_pipeline(MinMaxScaler(), KNeighborsClassifier(n_neighbors=k, weights=pesos)).fit(X, y)
        fila[f"P(sí) {pesos}"] = m.predict_proba(nueva)[0, list(m.classes_).index("sí")]
    filas.append(fila)
pd.DataFrame(filas).round(3)

	k	P(sí) uniform	P(sí) distance
0	1	1.000	1.000
1	3	1.000	1.000
2	5	0.800	0.924
3	7	0.571	0.813
4	8	0.500	0.776

52.8.2 Un problema real: el conjunto wine

El conjunto wine de scikit-learn tiene 178 vinos de tres cultivares descritos por 13 mediciones químicas en escalas muy distintas: la prolina toma valores entre 278 y 1680, mientras que el tono está entre 0.48 y 1.71. Es el escenario típico en el que escalar marca la diferencia.

from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, cross_val_score, StratifiedKFold, GridSearchCV
from sklearn.preprocessing import StandardScaler

vino = load_wine(as_frame=True)
X_v, y_v = vino.data, vino.target
X_tr, X_te, y_tr, y_te = train_test_split(X_v, y_v, test_size=0.3, stratify=y_v, random_state=0)
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)

print(X_v[["proline", "magnesium", "hue", "nonflavanoid_phenols"]].describe().loc[["min", "max", "std"]].round(2))
for nombre, modelo in [("sin escalar", KNeighborsClassifier(n_neighbors=5)),
                       ("estandarizado", make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)))]:
    acc = cross_val_score(modelo, X_tr, y_tr, cv=cv)
    print(f"5-NN {nombre:>14}: exactitud CV = {acc.mean():.3f} ± {acc.std():.3f}")

     proline  magnesium   hue  nonflavanoid_phenols
min   278.00      70.00  0.48                  0.13
max  1680.00     162.00  1.71                  0.66
std   314.91      14.28  0.23                  0.12
5-NN    sin escalar: exactitud CV = 0.742 ± 0.039
5-NN  estandarizado: exactitud CV = 0.951 ± 0.047

Sin escalar, la prolina domina la distancia y el clasificador apenas usa la información de las otras doce variables. Ahora elegimos \(k\), el tipo de voto y la métrica con búsqueda en rejilla y validación cruzada, solo sobre el entrenamiento:

import plotly.graph_objects as go

pipe = make_pipeline(StandardScaler(), KNeighborsClassifier())
rejilla = {"kneighborsclassifier__n_neighbors": list(range(1, 32, 2)),
           "kneighborsclassifier__weights": ["uniform", "distance"],
           "kneighborsclassifier__p": [1, 2]}
busqueda = GridSearchCV(pipe, rejilla, cv=cv, scoring="accuracy").fit(X_tr, y_tr)
res = pd.DataFrame(busqueda.cv_results_)

fig = go.Figure()
for pesos, color in [("uniform", "#2563eb"), ("distance", "#ea580c")]:
    d = res[(res.param_kneighborsclassifier__weights == pesos) & (res.param_kneighborsclassifier__p == 2)]
    fig.add_trace(go.Scatter(x=d.param_kneighborsclassifier__n_neighbors, y=d.mean_test_score,
                             mode="lines+markers", name=f"voto {pesos} (euclidiana)", line=dict(color=color)))
fig.update_layout(xaxis_title="k", yaxis_title="exactitud CV", height=360, margin=dict(l=10, r=10, t=20, b=40))
fig.show()
print("Mejor configuración:", busqueda.best_params_, f"(CV = {busqueda.best_score_:.3f})")
print(f"Exactitud en prueba: {busqueda.score(X_te, y_te):.3f}")

Figura 52.1: Exactitud de validación cruzada (5 pliegues) del k-NN estandarizado según k, con voto uniforme y ponderado. El voto ponderado es menos sensible a k.

Mejor configuración: {'kneighborsclassifier__n_neighbors': 7, 'kneighborsclassifier__p': 1, 'kneighborsclassifier__weights': 'uniform'} (CV = 0.976)
Exactitud en prueba: 0.981

52.8.3 Variables irrelevantes y alta dimensión

Para ver la maldición de la dimensionalidad en un caso real, añadimos a wine columnas de puro ruido. Cada una entra en la distancia con el mismo peso que las variables químicas.

from sklearn.tree import DecisionTreeClassifier

rng = np.random.default_rng(0)
filas = []
for extra in [0, 5, 10, 25, 50, 100, 200]:
    X_ruido = np.hstack([X_tr.values, rng.normal(size=(len(X_tr), extra))])
    knn_acc = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(5)), X_ruido, y_tr, cv=cv).mean()
    arbol_acc = cross_val_score(DecisionTreeClassifier(max_depth=4, random_state=0), X_ruido, y_tr, cv=cv).mean()
    filas.append({"variables de ruido": extra, "5-NN": knn_acc, "árbol (prof. 4)": arbol_acc})
ruido = pd.DataFrame(filas)

fig = go.Figure()
fig.add_trace(go.Scatter(x=ruido["variables de ruido"], y=ruido["5-NN"], name="5-NN", mode="lines+markers", line=dict(color="#2563eb")))
fig.add_trace(go.Scatter(x=ruido["variables de ruido"], y=ruido["árbol (prof. 4)"], name="árbol", mode="lines+markers", line=dict(color="#16a34a")))
fig.update_layout(xaxis_title="variables de ruido agregadas", yaxis_title="exactitud CV", yaxis_range=[0.3, 1.02],
                  height=360, margin=dict(l=10, r=10, t=20, b=40))
fig.show()

Figura 52.2: Exactitud de validación cruzada de 5-NN estandarizado al agregar variables de ruido a las 13 variables reales de wine. El árbol de decisión, que elige variables al partir, se degrada menos.

Finalmente, la concentración de distancias del laboratorio, simulada con numpy:

rng = np.random.default_rng(1)
filas = []
for p in [1, 2, 10, 100, 1000]:
    datos, q = rng.uniform(size=(500, p)), rng.uniform(size=p)
    d = np.linalg.norm(datos - q, axis=1)
    filas.append({"p": p, "d_min": d.min(), "d_max": d.max(), "d_min/d_max": d.min() / d.max(),
                  "lado para 10 %": 0.1 ** (1 / p)})
pd.DataFrame(filas).round(3)

	p	d_min	d_max	d_min/d_max	lado para 10 %
0	1	0.000	0.577	0.001	0.100
1	2	0.016	0.994	0.016	0.316
2	10	0.464	1.889	0.246	0.794
3	100	3.410	4.963	0.687	0.977
4	1000	12.343	13.759	0.897	0.998

52.9 Ventajas y limitaciones

Ventajas.

• No supone ninguna forma para la frontera; con datos suficientes aproxima fronteras arbitrarias.
• Es multiclase de forma natural y sirve también para regresión.
• Incorporar datos nuevos es inmediato: basta agregarlos.
• Sus decisiones se explican con ejemplos: «se parece a estos cinco casos».

Limitaciones.

• Es sensible a la escala, a las variables irrelevantes y a la dimensión.
• Predecir es costoso en tiempo y memoria si no se usan estructuras de búsqueda.
• No produce un resumen de los datos: no dice qué variables importan.
• Sus probabilidades son burdas (múltiplos de \(1/k\)) y suelen necesitar calibración.

Cuándo usarlo. Como referencia rápida en problemas con pocas variables numéricas bien escaladas, en sistemas de recomendación y búsqueda por similitud (con búsqueda aproximada) y como componente de otros métodos, por ejemplo la imputación de valores faltantes con vecinos del capítulo de preprocesamiento.

52.10 Resumen

• \(k\)-NN clasifica un punto con el voto de sus \(k\) vecinos más cercanos; la proporción de votos estima \(p(c \mid \mathbf{x})\).
• Qué significa «cercano» lo deciden la distancia y, sobre todo, el escalamiento, que se ajusta solo con el entrenamiento y forma parte del modelo.
• \(k\) controla el compromiso sesgo–varianza y se elige con validación cruzada; el voto ponderado reduce la sensibilidad a \(k\).
• Con infinitos datos, el error del 1-NN es a lo más el doble del error de Bayes, y \(k\)-NN con \(k \to \infty\), \(k/n \to 0\) lo alcanza.
• En alta dimensión las distancias se concentran y los vecindarios dejan de ser locales: \(k\)-NN necesita pocas variables relevantes.

El siguiente capítulo aborda una pregunta que ya apareció varias veces: cómo medir el desempeño de un clasificador cuando la exactitud no basta.

Referencias

Bellman, Richard E. 1961. Adaptive Control Processes: A Guided Tour. Princeton University Press.

Beyer, Kevin, Jonathan Goldstein, Raghu Ramakrishnan, y Uri Shaft. 1999. «When Is “Nearest Neighbor” Meaningful?» Database Theory – ICDT’99, Lecture Notes en Computer Science, vol. 1540: 217-35. https://doi.org/10.1007/3-540-49257-7_15.

Cover, Thomas M., y Peter E. Hart. 1967. «Nearest Neighbor Pattern Classification». IEEE Transactions on Information Theory 13 (1): 21-27. https://doi.org/10.1109/TIT.1967.1053964.

Fix, Evelyn, y Joseph L. Hodges. 1951. Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties. No. 4. USAF School of Aviation Medicine, Randolph Field, Texas.

Friedman, Jerome H., Jon Louis Bentley, y Raphael Ari Finkel. 1977. «An Algorithm for Finding Best Matches in Logarithmic Expected Time». ACM Transactions on Mathematical Software 3 (3): 209-26. https://doi.org/10.1145/355744.355745.

Fukunaga, Keinosuke, y Patrenahalli M. Narendra. 1975. «A Branch and Bound Algorithm for Computing k-Nearest Neighbors». IEEE Transactions on Computers C-24 (7): 750-53. https://doi.org/10.1109/T-C.1975.224297.

Hart, Peter E. 1968. «The Condensed Nearest Neighbor Rule». IEEE Transactions on Information Theory 14 (3): 515-16. https://doi.org/10.1109/TIT.1968.1054155.

Hastie, Trevor, Robert Tibshirani, y Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2.ª ed. Springer Series en Statistics. Springer. https://doi.org/10.1007/978-0-387-84858-7.

Stone, Charles J. 1977. «Consistent Nonparametric Regression». The Annals of Statistics 5 (4): 595-620. https://doi.org/10.1214/aos/1176343886.

Wilson, Dennis L. 1972. «Asymptotic Properties of Nearest Neighbor Rules Using Edited Data». IEEE Transactions on Systems, Man, and Cybernetics SMC-2 (3): 408-21. https://doi.org/10.1109/TSMC.1972.4309137.