KNN explicado: entrenar tardó 0,007 s, predecir 5,5 s y con k = 1 memorizó lo que vio

Ajustar KNN con 74.145 filas de clima, una por ciudad y día, tomó 0,007 segundos: escalar las variables y guardarlas. Puntuar después las 27.256 filas de prueba tomó 5,5 segundos con un hilo, casi 800 veces más. k vecinos más cercanos invierte el costo habitual de un modelo: casi no hace nada al entrenar y hace el trabajo al predecir.

Es la octava entrega de la serie, con los mismos datos diarios de NASA POWER de siete ciudades de Chile que usé en Random Forest, regresión lineal, K-Means, regresión logística, árbol de decisión, gradient boosting y SVM. La pregunta sigue siendo si lloverá al menos 1 mm mañana. Entrené con 1984-2012 y evalué en la prueba de 2016-2026, en un contenedor con 8 CPU y scikit-learn 1.7.2. k, los pesos y los demás parámetros de KNN los elegí ajustando con 1984-2009 (hasta el 30 de diciembre, porque la etiqueta del 31 es la lluvia del 1 de enero de 2010) y midiendo en 2010-2012. Los modelos de comparación usan la configuración de sus propios posts, y las curvas y ejemplos de 2016-2026 son descriptivos.

¿Qué es KNN?

KNN guarda la tabla de entrenamiento. Cuando llega un día nuevo, busca los k días guardados más parecidos según la distancia euclidiana entre sus variables. Con votos iguales, la probabilidad de lluvia es la parte de esos vecinos a los que les siguió lluvia; con votos ponderados, cada vecino pesa según el inverso de su distancia. Es la regla que Evelyn Fix y Joseph Hodges describieron en 1951; Thomas Cover y Peter Hart probaron en 1967 que, bajo ciertos supuestos y a medida que crecen los datos, el error de la regla del vecino más cercano queda acotado por el doble del error de Bayes, el mínimo posible.

Con k = 1 la respuesta es su único día más cercano, que siguió seco: 0 %. Con 5 y con 15 vecinos, al 80 % de ellos les siguió lluvia; con 51, al 51 %. Al día siguiente del día consultado no llovió. El modelo guarda la tabla y hace el trabajo al predecir; lo único que cambió fue k.

Con las mismas dos variables del post de SVM, humedad y lluvia de hoy, y los mismos 200 días de entrenamiento, consulté un día de La Serena de junio de 2010. Su vecino más cercano siguió seco, así que con k = 1 la probabilidad de lluvia fue 0 %. Con 5 y con 15 vecinos, 80 %. Con 51, 51 %. Al día siguiente no llovió.

k decide cuánto memoriza

Con k = 1 cada día de entrenamiento es su propio vecino más cercano, así que el modelo acierta los 200: AUC 1,000 en ellos y 0,671 en 2010-2012. Con k = 15 fue 0,861 y 0,796; con k = 51, 0,823 y 0,797. Un k chico memoriza, la misma falla del árbol sin límite y de la SVM con gamma grande.

Con k = 1 cada día de entrenamiento es su propio vecino más cercano, y el modelo acierta los 200: AUC 1,000 en ellos y 0,671 en 2010-2012. Con k = 51, la frontera se suaviza y los números quedan en 0,823 y 0,797. Es el mismo sobreajuste del árbol sin límite y de la SVM con gamma grande, controlado aquí por un solo número.

La distancia es de quien tiene los números grandes

KNN no tiene coeficientes que compensen las unidades: suma diferencias al cuadrado. Probé con k = 50 sobre las 66.466 filas de 1984-2009 y medí en 2010-2012.

• humedad: 54 %
• radiación: 13 %
• latitud: 7,8 %
• máxima: 6,5 %
• lluvia hoy: 4,3 %
• otras 10: 15 %

	sin escalar	Standard	MinMax
presión en kPa	0,840	0,872	0,864
presión en Pa	0,832	0,872	0,864

En kPa, la humedad aportó el 54 % de la distancia y la presión el 2,6 %. En Pa, la presión aportó el 100 %. Sin escalar, el AUC pasó de 0,840 a 0,832; estandarizado, 0,872 en los dos casos.

Sin escalar, la humedad, que en estos días va de 6 a 100 %, aportó el 54 % de la distancia esperada entre dos días al azar, y la presión en kPa, el 2,6 %. El AUC fue 0,840; con las 15 variables estandarizadas, 0,872, y con MinMaxScaler, 0,864.

En el post de SVM, escribir la presión en Pa hundió a la SVM sin escalar de 0,835 a 0,555. A KNN le costó menos: bajó a 0,832, aunque la presión pasó a aportar el 100 % de la distancia. La razón está en los datos. La presión viene con dos decimales y tiene solo 899 valores distintos en 66.466 filas. En Pa, el 59 % de los 50 vecinos de cada día tuvo exactamente su misma presión, contra el 1,2 % en kPa, y entre esos empates las demás variables siguieron eligiendo. Multiplicando la presión por un millón, el 96 % de los vecinos compartió la presión y el AUC bajó a 0,807. La presión sola dio 0,679. Estandarizado, el modelo no cambió con ninguna de las dos unidades.

Elegir k

• validación, votos iguales
• validación, 1/distancia
• sus propios días, votos iguales

Con k = 1 el modelo dio 1,000 en sus propios días y 0,687 en 2010-2012, con pérdida logarítmica 8,05: cada probabilidad fue 0 o 1. La validación tocó techo con k = 100 y votos por 1/distancia, 0,873, apenas 0,0004 sobre los votos iguales. Entre k = 50 y 300 la curva se mueve menos de 0,003; con 2.000 y votos iguales baja a 0,861. Reentrenado con 1984-2012, el modelo elegido dio 0,870 en 2016-2026.

Probé k de 1 a 2.000 con votos iguales y con votos pesados por el inverso de la distancia. Con k = 1 el AUC en 2010-2012 fue 0,69 y la pérdida logarítmica 8,05, porque cada probabilidad fue 0 o 1. Ganó k = 100 con votos ponderados por el inverso de la distancia, con 0,873, apenas 0,0004 sobre los votos iguales. Entre k = 50 y k = 300 la curva se movió menos de 0,003, así que en estos datos, dentro de ese rango, la elección exacta cambió poco. Reentrenado con 1984-2012, el modelo elegido dio 0,870 en 2016-2026.

La línea roja muestra KNN con votos iguales puntuando sus propios días de entrenamiento, donde cada día cuenta como su vecino: 1,000 con k = 1, 0,934 con k = 5 y 0,888 con k = 100. Medido con los datos que guardó, KNN parece mucho mejor de lo que es.

Con muchas dimensiones, cerca y lejos se parecen

Agregar 135 columnas de ruido bajó el AUC de 0,873 a 0,827; con la distancia euclidiana sobre variables estandarizadas cada columna pesa lo mismo, así que una inútil suma distancia sin sumar información. En datos uniformes con 2 dimensiones el punto más cercano quedó al 0,003 del más lejano; con 150, al 0,695. La tabla real, con 15 dimensiones, dio 0,026, contra 0,268 de los datos uniformes con 15: su vecino más cercano queda mucho más cerca que el más lejano.

Con la distancia euclidiana sobre variables estandarizadas, cada columna pesa lo mismo. Agregué columnas de ruido normal a las 15 variables estandarizadas: con 5, el AUC en 2010-2012 bajó de 0,873 a 0,865; con 45, a 0,847, y con 135, a 0,827. Ninguna columna de ruido tenía información, pero todas sumaban distancia.

La segunda mitad del gráfico es la razón geométrica, la que describieron Beyer y coautores en 1999, y Aggarwal y coautores en 2001. En 20.000 puntos uniformes al azar, la distancia al vecino más cercano quedó al 0,003 de la del más lejano con 2 dimensiones, al 0,27 con 15 y al 0,69 con 150. La tabla real, con 15 dimensiones, dio 0,026: en los días reales el vecino más cercano queda mucho más cerca que el más lejano, y el AUC de validación muestra que esa cercanía todavía sirve para predecir.

Una selección de variables hacia adelante con 20.000 filas de 1984-2009, midiendo en 2010-2012, se quedó con 8 de las 15: lluvia de hoy, latitud, las dos componentes y la velocidad del viento, cambio de presión, máxima y humedad. Con k = 150 y votos por distancia, elegidos de nuevo en 2010-2012, dio AUC 0,870 en 2016-2026, lo mismo que las 15 variables. El subconjunto quedó 0,0007 arriba, una diferencia sin intervalo calculado, y guarda 8 de las 15 columnas por fila.

Entrenar es barato; consultar, no

• exhaustiva, 1 hilo
• exhaustiva, 8 hilos
• kd_tree
• ball_tree
• ajuste

Con las 74.145 filas, ajustar tomó 0,007 s y puntuar el período de prueba 5,47 s con un hilo y 0,77 s con ocho. Con un hilo, los árboles no ayudaron en 15 dimensiones: kd_tree tardó 9,05 s y ball_tree 12,45 s. Las filas guardadas crecieron 37 veces; el tiempo de puntuar con búsqueda exhaustiva, 10,4 veces.

Con las 74.145 filas, el ajuste tomó 0,007 s en la corrida de costo: el escalador calcula medias y desviaciones, y scikit-learn guarda las filas escaladas con sus etiquetas. Puntuar las 27.256 filas de prueba contra ella tomó 5,5 s con un hilo y 0,77 s con ocho. Entre 2.000 y 74.145 filas guardadas, 37 veces más, el tiempo de puntuar creció 10 veces.

La documentación de scikit-learn dice que un kd_tree, el árbol que propuso Bentley en 1975, es muy rápido con pocas dimensiones, menos de 20, y que se vuelve ineficiente cuando crecen. Con estas 15 y k = 100 fue más lento: kd_tree tardó 9,1 s y ball_tree 12,4 s con un hilo, más que la búsqueda exhaustiva. El modelo serializado ocupa 9,5 MB, que es la tabla.

¿De quién son los vecinos?

El 85,8 % de los vecinos vino de la misma ciudad y el 88,9 % estaba a 30 días o menos de la misma fecha del año. La latitud y el día del año están entre las 15 variables, así que ciudad y estación pesan directamente en la distancia; el resto lo completan las variables del clima.

Con las 74.145 filas guardadas y k = 100, el 85,8 % de los vecinos de cada día de 2016-2026 vino de su misma ciudad y el 88,9 % estaba a 30 días o menos de su fecha en el año. La latitud y el día del año están entre las 15 variables, así que ciudad y estación pesan directamente en la distancia. Santiago encontró el 99,8 % de sus vecinos en Santiago; Temuco, solo el 64 %, y el 23 % en Concepción. KNN se puede explicar mostrando los vecinos, y eso también expone sus errores: el 1 de enero de 2021 llovió al día siguiente en Santiago, y de los 100 días más parecidos de 1984-2012, solo a 3 les siguió lluvia.

Probabilidades en escalones

Con votos iguales y k vecinos, la probabilidad solo puede tomar k + 1 valores. En 2016-2026, con k = 1, cada fila recibió 0 o 1 y la pérdida logarítmica fue 7,64; con k = 5, 1,36, y con k = 50, 0,385. El modelo elegido pondera por distancia y produjo 24.229 valores distintos, con pérdida 0,370. Aun así, el 11 % de las filas recibió exactamente 0 o 1: sus 100 vecinos coincidieron. La regresión logística dio 0,378 y el boosting 0,332.

El modelo predijo en promedio 23,8 % de lluvia contra 20,3 % observado. La regresión logística predijo 24,1 % y el boosting 23,4 %: los tres aprendieron con 1984-2012, cuando al 26,6 % de los días le siguió lluvia, contra el 20,3 % de la prueba; el sesgo es compatible con ese cambio de frecuencia.

Achicar lo que se guarda

Con 3.200 prototipos KNN dio 0,864 en 0,42 s; la tabla completa, 0,870 en 5,70 s, 14 veces más lento. Con 50 prototipos el AUC bajó a 0,826. Los prototipos vienen en igual número por clase, lo que distorsiona la frecuencia de lluvia: la pérdida logarítmica fue 0,429 contra 0,370 de la tabla completa. La capacidad de ordenar se conservó en gran parte; las probabilidades convendría calibrarlas antes de usarlas.

Si el costo está en las filas guardadas, se pueden reemplazar por menos puntos. Hart propuso en 1968 guardar solo los ejemplos necesarios; aquí usé centroides de K-Means ajustados por separado sobre los días seguidos de lluvia y los seguidos de tiempo seco, con el k sobre los prototipos elegido en 2010-2012. Con 3.200 prototipos, KNN dio AUC 0,864 en 2016-2026 y puntuó la prueba en 0,42 s; la tabla completa, en la misma corrida, dio 0,870 en 5,7 s. Con 50 prototipos, 0,826 en 0,015 s.

El costo aparece en las probabilidades. Como hay el mismo número de prototipos de cada clase, la parte de vecinos con lluvia ya no refleja la frecuencia real, y la pérdida logarítmica fue 0,429 contra 0,370; parte de esa diferencia puede venir de ordenar un poco peor. La capacidad de ordenar se conservó en gran parte; las probabilidades convendría calibrarlas antes de usarlas.

Para números: KNN como regresión

KNeighborsRegressor predice el promedio de los vecinos. Para la máxima de mañana, k = 20 fue la mejor en 2010-2012, y reentrenado con 1984-2012 erró por 1,58 °C en promedio en 2016-2026; la regresión lineal, por 1,70 °C, y el boosting, por 1,44 °C.

En la prueba de extrapolación de la serie, entrenar con los meses de abril a septiembre de Santiago y predecir los veranos de 2016-2026, KNN no pasó de 28,0 °C. El día más caluroso que vio tenía 32,97 °C y el verano real promedió 29,63 °C. Un promedio de vecinos no puede salir del rango de lo que guardó, y KNN erró por 4,31 °C; el boosting, que tampoco pasó de 29,56 °C, por 5,48 °C. La regresión lineal erró por 1,72 °C. Es un corte por estación, no una prueba limpia fuera del rango: el verano cambia varias variables a la vez.

KNN, boosting, bosque, árbol y logística

EntrenarPuntuar la prueba

KNN, k = 100 · AUC 0,8700,014 s

Regresión logística · AUC 0,8470,049 s

Árbol, profundidad 7 · AUC 0,8620,37 s

Boosting, 594 rondas · AUC 0,8832,604 s

Bosque, 200 árboles · AUC 0,88223,812 s

A un cuarto del tiempo real.

Regresión logística0,001 s

Árbol, profundidad 70,002 s

Bosque, 200 árboles0,319 s

Boosting, 594 rondas0,583 s

KNN, k = 1005,771 s

Los 27.256 filas, en tiempo real.

Puntuar un solo día tomó 1,9 ms a KNN, 3,1 ms al boosting y 0,4 ms a la regresión logística. Serializado, KNN ocupa 9,5 MB, el boosting 2,1 MB y el bosque 124 MB.

Con las mismas filas, remuestreé 2.000 veces los bloques ciudad-año de 2016-2026 para comparar el AUC en pares. KNN quedó por debajo del boosting por 0,013 (intervalo del 95 %: de −0,017 a −0,010) y del bosque por 0,013, y por encima del árbol de profundidad 7 por 0,008 y de la regresión logística por 0,023. Ninguno de los cuatro intervalos cruza el cero. La latencia de un día fue 1,9 ms en esta corrida y 2,5 ms en la de costo, y el ajuste, 0,014 y 0,007 s: con tiempos tan chicos, dos corridas no dan lo mismo.

Dónde vive KNN en un sistema real

Medido con un hilo sobre las 74.145 filas: KNN «entrena» en 0,014 s, serializado ocupa 9,5 MB porque es la tabla, puntúa un día en 1,87 ms y las 27.256 filas de prueba en 5,8 s (AUC 0,870). El boosting entrena en 2,6 s, tarda 3,06 ms por día, ocupa 2,1 MB y da AUC 0,883. La regresión logística: 0,40 ms, AUC 0,847.

• Búsqueda por similitud. Recomendaciones, documentos parecidos o casos anteriores: el mismo principio con vectores de muchas dimensiones, a menudo sobre un índice aproximado como HNSW (Malkov y Yashunin) en vez de la búsqueda exhaustiva.
• Tablas que cambian seguido. No hay coeficientes que reoptimizar: un ejemplo nuevo es una fila más, aunque con un pipeline de scikit-learn hay que volver a ajustar y decidir si se actualiza el escalador.
• Explicar con ejemplos. Una predicción se puede justificar mostrando los días parecidos que la sostienen.
• Una base contra la que medir. Con 15 variables estandarizadas, KNN quedó sobre la regresión logística y el árbol, y a 0,013 del boosting.

Cuándo lo elegiría: con tablas pequeñas o medianas de variables numéricas bien escaladas, cuando los datos cambian seguido o cuando hace falta mostrar ejemplos parecidos. Cuándo no: cuando cada predicción tiene que ser barata sobre muchas filas, cuando hay muchas columnas irrelevantes, cuando las unidades no están controladas o cuando hay que extrapolar. En estos datos un boosting obtuvo mayor AUC y menor pérdida logarítmica, y puntuó la prueba diez veces más rápido.

Fuentes

• Fix, E. y Hodges, J. L. (1989). «Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties». International Statistical Review, 57(3). Reimpresión del informe de 1951. DOI 10.2307/1403797.
• Cover, T. y Hart, P. (1967). «Nearest neighbor pattern classification». IEEE Transactions on Information Theory, 13(1), 21–27. DOI 10.1109/TIT.1967.1053964.
• Hart, P. (1968). «The condensed nearest neighbor rule». IEEE Transactions on Information Theory, 14(3), 515–516. DOI 10.1109/TIT.1968.1054155.
• Bentley, J. L. (1975). «Multidimensional binary search trees used for associative searching». Communications of the ACM, 18(9), 509–517. DOI 10.1145/361002.361007.
• Beyer, K., Goldstein, J., Ramakrishnan, R. y Shaft, U. (1999). «When Is “Nearest Neighbor” Meaningful?». Database Theory — ICDT’99, 217–235. DOI 10.1007/3-540-49257-7_15.
• Aggarwal, C. C., Hinneburg, A. y Keim, D. A. (2001). «On the Surprising Behavior of Distance Metrics in High Dimensional Space». Database Theory — ICDT 2001, 420–434. DOI 10.1007/3-540-44503-X_27.
• Malkov, Y. A. y Yashunin, D. A. (2020). «Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs». IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824–836. DOI 10.1109/TPAMI.2018.2889473.
• scikit-learn 1.7, vecinos más cercanos.
• NASA POWER, Daily API y fuentes de datos.