k-Nearest Neighbors

Qué cubre este capítulo

La mayoría de los clasificadores dedican una fase de entrenamiento a condensar los datos en unos cuantos parámetros, y luego tiran los datos. k-nearest neighbors se niega. Conserva cada punto de entrenamiento y, para etiquetar algo nuevo, simplemente mira qué tiene más cerca y copia la mayoría local. No hay modelo que ajustar — el conjunto de entrenamiento es el modelo. Eso lo vuelve el machine learning más literal que existe: "las cosas cercanas entre sí tienden a parecerse", convertido en código.

Lo construimos a mano en NumPy, una función a la vez — una distancia, un ordenamiento, una votación — y luego dejamos que scikit-learn construya lo mismo y verificamos que los números coincidan. En el camino vas a verlo decidir: para cada flor de prueba encerramos en un círculo a sus k vecinos más cercanos, dibujamos los votos y coloreamos el punto según la clase que gane. Vas a ver exactamente dónde está seguro y exactamente dónde adivina, porque las dos cosas se ven distintas en pantalla.

Los datos son Iris — 150 flores, tres especies, y nos quedamos con dos mediciones (largo y ancho del pétalo) para que todo viva en un plano que de verdad puedes ver.

Un poco de historia

La idea es vieja y la demostración es famosa. En 1951 Evelyn Fix y Joseph Hodges, trabajando en un reporte técnico para la US Air Force School of Aviation Medicine, escribieron la discriminación no paramétrica por vecinos más cercanos — sin distribución supuesta, solo distancias. Se quedó casi sin leer durante años. Luego, en 1967, Thomas Cover y Peter Hart publicaron "Nearest Neighbor Pattern Classification" en las IEEE Transactions on Information Theory y le dieron el resultado que hizo que la gente pusiera atención: conforme el conjunto de entrenamiento crece sin límite, la tasa de error del vecino más cercano único nunca es peor que el doble del error de Bayes — lo mejor que cualquier clasificador podría lograr. Un vecino, cero entrenamiento, y ya estás a un factor de dos del óptimo. Es algo asombroso poder demostrar eso de una regla tan simple.

Lo que evitó que kNN fuera solo una curiosidad teórica es que nunca se fue. Es el caballo de batalla detrás de la recomendación ("usuarios como tú también compraron"), el baseline en cada paper de recuperación de imágenes, y el punto de referencia honesto para cualquier cosa que presuma haber aprendido estructura. Las bases de datos vectoriales modernas — las que guardan los embeddings detrás de la búsqueda semántica y la generación aumentada por recuperación — son, debajo del marketing, búsqueda rápida de vecinos más cercanos sobre millones de puntos. El algoritmo que Fix y Hodges bosquejaron en 1951 está corriendo en producción ahora mismo, solo que con un mejor índice.

La intuición

Mira las dos mediciones del pétalo graficadas una contra otra, un punto por flor, coloreadas por especie. Setosa está apartada, sola en la esquina inferior izquierda — pétalos pequeños, sin discusión. Versicolor y virginica están apiladas arriba a la derecha y se mezclan entre sí a lo largo de una costura difusa. Esa costura es toda la historia de este dataset.

Ahora imagina soltar una flor nueva, sin etiqueta, sobre ese plano. ¿Dónde cae? Si cae en lo profundo de la nube cian, todo a su alrededor es setosa y la decisión es obvia. Si cae en la costura donde el morado y el naranja se traslapan, sus vecinos no se ponen de acuerdo, y la etiqueta que le des depende de cuáles resulten estar más cerca. Eso es kNN en una sola imagen: encuentra los k puntos más cercanos, haz una votación. Sin línea, sin ecuación de una frontera — la frontera está donde sea que los votos cambien de bando, y se dobla alrededor de los datos tan ajustada o tan suelta como k lo permita.

La matemática

Dale a cada flor de entrenamiento un vector de features $x_i \in \mathbb{R}^{D}$ y una etiqueta $y_i$. Aquí $D = 2$ y $y_i$ es una de tres especies. Para clasificar un punto de consulta $q$, primero mide qué tan lejos está de cada punto de entrenamiento. La métrica por defecto es la distancia euclidiana de toda la vida:

Ordena esas $N$ distancias y toma las $k$ más pequeñas. Llama a ese conjunto de índices $N_k(q)$ — los k vecinos más cercanos. La predicción es la etiqueta que aparece más veces entre ellos:

La suma interna cuenta cuántos de los k vecinos llevan la clase $c$; el $\arg\max$ se queda con la clase que tenga más votos. Ese es el algoritmo completo. No hay ningún parámetro estimado a partir de los datos en esas dos líneas — lo único que eliges es $k$, y $k$ es una perilla que tú ajustas, no algo que los datos te entregan. Una $k$ pequeña confía en los puntos más cercanos individuales y sigue cada curvita; una $k$ grande promedia sobre una multitud más amplia y suaviza la frontera.

Un detalle que la fórmula esconde: cuando dos clases empatan, necesitas una regla para desempatar. Nosotros ordenamos las etiquetas de clase y nos quedamos con la más pequeña, lo cual es arbitrario pero fijo — la misma consulta siempre se resuelve igual. Los valores impares de $k$ evitan empates en el caso de dos clases exactamente por esta razón.

En qué es bueno, en qué no

El atractivo es que no hay nada que ajustar. Sin loop de entrenamiento, sin loss, sin convergencia que vigilar — cargas los datos y ya puedes predecir. La superficie de decisión puede tener cualquier forma, porque se cose localmente a partir de los puntos que haya alrededor, así que kNN maneja fronteras curvas, amorfas y no lineales que un solo corte recto no puede tocar. Y es un baseline honesto por la misma razón que lo era el umbral: si tu modelo elaborado no puede ganarle a "copia a los más cercanos", el modelo elaborado no se está ganando su complejidad.

Los costos son igual de directos. No hace ningún trabajo al momento de entrenar y todo al momento de predecir — cada predicción individual recorre todo el conjunto de entrenamiento, así que un modelo que fue instantáneo de "entrenar" es lento de usar, y se vuelve más lento entre más datos le des. Tiene que guardar todos esos datos en memoria, para siempre. Es sensible a la escala de las features: la distancia suma sobre dimensiones, así que una feature medida en miles ahoga a una medida en décimas a menos que estandarices primero. Y se pudre en dimensiones altas — la maldición de la dimensionalidad — porque cuando tienes cientos de features cada punto está más o menos equidistante de todos los demás, "más cercano" deja de significar algo, y la votación es ruido. kNN es maravilloso en dos dimensiones y traicionero en doscientas.

Los datos

Iris es el "hello world" de la clasificación, y por una vez el cliché se lo gana — es pequeño, limpio, y la estructura se ve a simple vista. Edgar Anderson midió las flores; Ronald Fisher las usó en su paper de análisis discriminante de 1936, y por eso también lo verás llamado el Iris de Fisher. Tres especies, cincuenta flores de cada una, cuatro mediciones por flor. Descartamos dos de las mediciones y nos quedamos con el largo y el ancho del pétalo, porque esas dos cargan casi toda la señal separadora y, más al punto, dos features caben en una pantalla. El scatter de arriba es el dataset completo — no hay nada escondido en una tercera dimensión que no te estemos mostrando.

El detalle que importa más adelante: versicolor y virginica genuinamente chocan. Un puñado de flores de las dos especies comparten exactamente el mismo largo y ancho de pétalo hasta la precisión registrada. Ningún clasificador puede separarlas con estas dos features — la información simplemente no está ahí — así que hay un techo por debajo del 100% horneado en los datos, y kNN se topa con él justo donde esperarías, en la costura.

Constrúyelo, una función a la vez

Seis funciones cortas, y las primeras tres son el algoritmo completo. Este es el orden en que yo lo escribiría en una terminal: la distancia primero, porque todo cuelga de ella.

Empieza con la distancia de un punto de consulta a todos los puntos de entrenamiento a la vez. La resta hace broadcast de la consulta sobre todas las filas, así que no hay loop — una sola expresión regresa las N distancias:

def euclidean(X, q):
    """Straight-line distance from a query point q to every row of X.

    X is (N, D) — N training points in D dimensions. q is (D,). The
    subtraction broadcasts q across all N rows, so one call gives back all N
    distances at once, no loop.
    """
    return np.sqrt(((X - q) ** 2).sum(axis=1))     # shape (N,)

Con las distancias en mano, "encontrar los vecinos" es un ordenamiento. argsort ordena cada punto de entrenamiento según qué tan cerca está; nos quedamos con los primeros k índices. Aquí es donde kNN gasta todo su presupuesto de cómputo, y es la razón por la que la predicción es la mitad cara:

def k_nearest(X, q, k):
    """Indices of the k training points closest to q, nearest first.

    argsort orders every point by distance; we keep the first k. That's the
    whole "search" — kNN spends all its effort here, at predict time.
    """
    d = euclidean(X, q)
    return np.argsort(d)[:k]

Luego la votación. Cuenta las etiquetas entre esos k vecinos y regresa la más común. np.unique devuelve las etiquetas en orden, así que tomar el argmax de los conteos desempata hacia la etiqueta más pequeña — una regla fija en lugar de un accidente del ordenamiento:

def majority_vote(labels):
    """The label that appears most among the neighbors.

    np.unique returns the labels in sorted order, so argmax on the counts
    breaks ties toward the smaller label — a fixed, reproducible rule rather
    than whatever order the neighbors happened to arrive in.
    """
    vals, counts = np.unique(labels, return_counts=True)
    return vals[np.argmax(counts)]

Esas tres se componen en una predicción para un solo punto: vecinos más cercanos, luego votación.

def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])

Para etiquetar un conjunto de prueba completo solo corres eso por punto. kNN no tiene trabajo compartido que amortizar entre consultas — cada una es una búsqueda independiente — así que esto es honestamente un loop, y ninguna astucia lo cambia:

def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])

Última pieza, el mismo accuracy que hemos usado desde el principio: qué fracción de las predicciones coincide con la verdad.

def accuracy(y_true, y_pred):
    """Fraction of predictions that match the truth."""
    return float((np.asarray(y_true) == np.asarray(y_pred)).mean())

Míralo trabajar

Esta es la parte por la que vale la pena ir despacio. Tomamos las flores de prueba apartadas, una a la vez, y dejamos que el clasificador haga lo suyo a la vista de todos. Los puntos tenues son las 105 flores de entrenamiento, coloreadas por su especie verdadera. Para cada consulta la encerramos en un círculo, dibujamos un anillo punteado cuyo radio llega exactamente hasta el quinto vecino más cercano, conectamos la consulta con cada uno de sus cinco vecinos, y luego coloreamos la consulta según la especie que gane la votación. Si el voto está mal, el punto recibe un anillo rojo. La leyenda narra el conteo.

Dale play y mira la consulta barrer el plano de izquierda a derecha.

Las primeras consultas caen en lo profundo del territorio de setosa y virginica y el voto es unánime — cinco para una clase, un circulito ajustado, nada que discutir. Luego la consulta se mete a la costura entre versicolor y virginica y todo el carácter cambia. El círculo sigue siendo pequeño pero los cinco vecinos adentro dejan de estar de acuerdo: cuatro a uno, luego tres a dos. Tres de estos puntos disputados reciben anillo rojo, y si lees sus conteos son todos el mismo tipo de error — una flor sentada del lado equivocado de una frontera que en realidad no existe, porque las dos especies se traslapan ahí. Eso no es un bug de kNN. Es kNN reportando fielmente que los datos son ambiguos exactamente donde los datos son ambiguos.

Ahora la perilla. Aquí están el accuracy de prueba y el de entrenamiento conforme k crece de 1 a 25. Las dos curvas están cerca y ambas son planas, lo cual es en sí la lección: cuando las clases están así de bien separadas, k apenas importa — puedes promediar sobre un vecino o sobre quince y obtener esencialmente la misma respuesta.

Mira el borde izquierdo. En k = 1 el accuracy de entrenamiento no es un 1.0 perfecto — se queda en 0.991 — y no es un capricho de redondeo. El vecino más cercano de un punto de entrenamiento debería ser él mismo, a distancia cero, lo cual haría el accuracy de entrenamiento exactamente uno. La brecha es esa colisión de la que te advertí: una versicolor y una virginica están en coordenadas de pétalo idénticas, así que una de ellas encuentra un vecino a distancia cero de la clase equivocada y se vota mal a sí misma. Los datos te ponen un techo por debajo de la perfección incluso en los puntos con los que entrenaste. En un dataset más sucio esta gráfica contaría la historia de siempre — k = 1 memoriza y hace overfitting, una k más grande suaviza y generaliza — pero Iris es demasiado limpio para dramatizarla, y fingir lo contrario sería deshonesto.

Para ver de verdad a k suavizando, mira la superficie de decisión en lugar del accuracy. Aquí está el mapa de lo que el clasificador predice en cada punto del plano, con k = 1. Cada punto de entrenamiento gobierna un pequeño territorio propio, así que la frontera es dentada y hay islas sueltas donde un outlier estampa su clase sobre el área circundante:

Ahora la misma superficie con k = 15. Promediar sobre quince vecinos borra las islas, endereza la costura y deja tres regiones limpias. Esta es la imagen que la curva plana de accuracy no podía mostrarte — k no cambió mucho el puntaje, pero cambió mucho la forma de la decisión, y en datos más ruidosos esa forma es la diferencia entre un modelo que generaliza y uno que memoriza:

La implementación completa

El clasificador entero, sin librería, de arriba a abajo. Este es el archivo que la animación de arriba realmente corrió:

"""k-Nearest Neighbors, built from scratch.

To label a new point, look at the k training points closest to it and let
them vote. There is no training step at all — the "model" is the training set
itself, kept around and searched at predict time. Pure NumPy, no ML library
anywhere in this file.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: euclidean
def euclidean(X, q):
    """Straight-line distance from a query point q to every row of X.

    X is (N, D) — N training points in D dimensions. q is (D,). The
    subtraction broadcasts q across all N rows, so one call gives back all N
    distances at once, no loop.
    """
    return np.sqrt(((X - q) ** 2).sum(axis=1))     # shape (N,)
# endregion


# region: k_nearest
def k_nearest(X, q, k):
    """Indices of the k training points closest to q, nearest first.

    argsort orders every point by distance; we keep the first k. That's the
    whole "search" — kNN spends all its effort here, at predict time.
    """
    d = euclidean(X, q)
    return np.argsort(d)[:k]
# endregion


# region: majority_vote
def majority_vote(labels):
    """The label that appears most among the neighbors.

    np.unique returns the labels in sorted order, so argmax on the counts
    breaks ties toward the smaller label — a fixed, reproducible rule rather
    than whatever order the neighbors happened to arrive in.
    """
    vals, counts = np.unique(labels, return_counts=True)
    return vals[np.argmax(counts)]
# endregion


# region: knn_predict_one
def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])
# endregion


# region: knn_predict
def knn_predict(X, y, Q, k):
    """Predict a label for every query row in Q by running the vote per point.

    X, y are the training set; Q is (M, D) of points to classify. kNN has no
    shared work to amortize across queries, so this is honestly just a loop.
    """
    return np.array([knn_predict_one(X, y, q, k) for q in Q])
# endregion


# region: accuracy
def accuracy(y_true, y_pred):
    """Fraction of predictions that match the truth."""
    return float((np.asarray(y_true) == np.asarray(y_pred)).mean())
# endregion


def load_data(path="../data/iris2d.csv"):
    """Iris, reduced to two features: petal length and petal width.

    Returns (X, y, names): X is (N, 2) float, y is (N,) int class ids
    0/1/2, names maps id -> class name.
    """
    df = pd.read_csv(path)
    X = df[["petal_length", "petal_width"]].to_numpy(float)
    y = df["class_id"].to_numpy(int)
    names = dict(sorted(df[["class_id", "class"]].drop_duplicates().itertuples(index=False)))
    return X, y, names

La versión de librería

Nadie escribe a mano la búsqueda de vecinos en producción, y una vez que la entiendes, tú tampoco deberías. El KNeighborsClassifier de scikit-learn es el mismo algoritmo — distancia, k más cercanos, voto por mayoría — con los defaults puestos para coincidir con lo que construimos: votos uniformes (sin pesos) y la métrica euclidiana simple. Ajustarlo solo almacena el conjunto de entrenamiento:

def knn_sklearn(X_train, y_train, X_test, k):
    """Fit a k-NN classifier and predict the test points. Returns predictions.

    n_neighbors is our k. The defaults match our scratch version: uniform
    (unweighted) votes and the plain Euclidean metric.
    """
    clf = KNeighborsClassifier(n_neighbors=k)
    clf.fit(X_train, y_train)
    return clf.predict(X_test)

Lo único que hace que nuestra versión no hace es la búsqueda misma. Nuestro k_nearest ordena las N distancias completas en cada consulta, lo cual está bien para 105 flores y es inviable para un millón. sklearn construye silenciosamente un índice espacial — un KD-tree o un ball tree — al momento del fit, para poder encontrar los k más cercanos sin mirar cada punto. La misma respuesta, un escalamiento dramáticamente mejor, y es la razón por la que el paso de "fit" existe siquiera en una librería donde fit no aprende nada.

Barrer k para dibujar una curva es la misma idea, una vez por valor:

def knn_curve_sklearn(X_train, y_train, X_test, y_test, ks):
    """Test accuracy for each k in ks — the library's version of the curve."""
    out = []
    for k in ks:
        clf = KNeighborsClassifier(n_neighbors=k)
        clf.fit(X_train, y_train)
        out.append(float(clf.score(X_test, y_test)))
    return out

Desde cero contra librería

Divide las 150 flores en 105 para entrenar y 45 apartadas, ajusta ambas versiones con k = 5, y evalúalas sobre el conjunto apartado:

Ambos caen en 0.9333 — idénticos, no parecidos, idénticos: las 45 predicciones de prueba coinciden flor por flor. Ese es el resultado que quieres, y con kNN está casi garantizado, porque no hay inicialización aleatoria, no hay optimizador, no hay nada que divergir. Con los mismos datos, la misma k y el mismo desempate, el voto es el voto. Las tres flores que fallamos son las tres sentadas en el traslape versicolor–virginica, y ningún valor de k las arregla, porque el techo está en los datos, no en el modelo.

Dos notas honestas sobre ese 0.9333. Primero, es un conjunto de prueba pequeño — 45 flores, así que cada error vale unos dos puntos y no deberías leer el tercer decimal como si fuera palabra santa; una división distinta cae en cualquier lugar entre más o menos 0.91 y 0.96, que es el rango real para este problema. Segundo, setosa es dinero gratis. Está perfectamente separada, así que un tercio del conjunto de prueba es trivialmente correcto y sostiene el número; toda la dificultad real vive en las otras dos clases. El número que produce el enfrentamiento vive en results.json, regenerado cada vez que el código cambia, para que la prosa y la imagen no puedan desviarse de lo que el código hizo.

Conclusiones

Recurre a kNN cuando quieras un baseline fuerte sin ceremonia de entrenamiento, tus datos sean de baja dimensión y puedas darte el lujo de ser lento al predecir. Es genuinamente difícil de vencer en problemas pequeños, bien escalados y de baja dimensión, y te dirá rápido si existe alguna estructura local que valga la pena modelar — si copiar a los más cercanos ya puntúa bien, tus clases se agrupan, y eso vale la pena saberlo antes de recurrir a algo más pesado.

Aléjate de él cuando cualquiera de tres cosas sea cierta, y una de ellas casi siempre lo es. Cuando tienes muchas features, las distancias dejan de discriminar y el método entero deja de funcionar en silencio — esa es la maldición de la dimensionalidad, y es la razón por la que kNN es un héroe en dos dimensiones y una liability en doscientas. Cuando tienes muchas filas, el trato de cero-entrenamiento-todo-predicción se vuelve en tu contra: cada consulta recorre todo, e "instantáneo de entrenar" se convierte en "demasiado lento para servir". Y cuando tus features viven en escalas salvajemente distintas, la distancia es una mentira hasta que estandarizas — que es exactamente por lo que el siguiente tramo de este curso trata de escalar features y elegirlas bien, porque kNN es el algoritmo que más duro te castiga por saltarte ese trabajo. Dos cosas que aun así te regala vale la pena conservarlas: nunca asume una forma para la frontera, y sus errores apuntan directo a donde tus clases realmente se traslapan. No es mala cosa para traer en el bolsillo, incluso en la era de los índices de miles de millones de vectores que son, por debajo, exactamente esta idea.