KNN explained: training took 0.007 s, predicting 5.5 s, and with k = 1 it memorized what it saw

Fitting KNN on 74,145 rows of weather, one per city and day, took 0.007 seconds: scaling the variables and storing them. Scoring the 27,256 test rows afterwards took 5.5 seconds on one thread, almost 800 times longer. k-nearest neighbors flips the usual cost of a model: it does almost nothing at training time and the work at prediction time.

This is the eighth post in the series, with the same daily NASA POWER data from seven Chilean cities I used for Random Forest, linear regression, K-Means, logistic regression, decision trees, gradient boosting and SVM. The question is still whether at least 1 mm of rain will fall tomorrow. I trained on 1984-2012 and evaluated on the 2016-2026 test period, in a container with 8 CPUs and scikit-learn 1.7.2. I chose k, the weights and the other KNN settings by fitting on 1984-2009 (up to 30 December, because the label of the 31st is rain on 1 January 2010) and scoring on 2010-2012. The comparison models use the settings from their own posts, and the 2016-2026 curves and examples are descriptive.

What is KNN?

KNN stores the training table. When a new day arrives, it finds the k stored days most similar by Euclidean distance between their variables. With equal votes, the rain probability is the share of those neighbors that were followed by rain; with weighted votes, each neighbor counts by the inverse of its distance. It is the rule Evelyn Fix and Joseph Hodges described in 1951; Thomas Cover and Peter Hart proved in 1967 that, under certain assumptions and as data grows, the error of the nearest-neighbor rule is bounded by twice the Bayes error, the lowest possible.

With k = 1 the answer is its single closest day, which stayed dry: 0 %. With 5 and 15 neighbors, 80 % of them were followed by rain; with 51, 51 %. It did not rain the day after the query day. The model stores the table and does the work at prediction time; k is the only thing that changed.

With the same two variables as the SVM post, humidity and today’s rain, and the same 200 training days, I queried a La Serena day from June 2010. Its nearest neighbor stayed dry, so with k = 1 the rain probability was 0 %. With 5 and with 15 neighbors, 80 %. With 51, 51 %. It did not rain the next day.

k decides how much it memorizes

With k = 1 every training day is its own nearest neighbor, so the model gets all 200 right: AUC 1.000 on them and 0.671 on 2010-2012. With k = 15 it was 0.861 and 0.796; with k = 51, 0.823 and 0.797. A small k memorizes, the same failure as the unlimited tree and the SVM with a large gamma.

With k = 1 every training day is its own nearest neighbor, and the model gets all 200 right: AUC 1.000 on them and 0.671 on 2010-2012. With k = 51 the boundary smooths out and the numbers are 0.823 and 0.797. It is the same overfitting as the unlimited tree and the SVM with a large gamma, controlled here by a single number.

Distance belongs to whoever has the large numbers

KNN has no coefficients to compensate for units: it adds squared differences. I tested k = 50 on the 66,466 rows of 1984-2009 and scored on 2010-2012.

• humidity: 54 %
• radiation: 13 %
• latitude: 7.8 %
• max temp: 6.5 %
• rain today: 4.3 %
• other 10: 15 %

	no scaling	Standard	MinMax
pressure in kPa	0.840	0.872	0.864
pressure in Pa	0.832	0.872	0.864

In kPa, humidity carried 54 % of the distance and pressure 2.6 %. In Pa, pressure carried 100 %. Without scaling, AUC went from 0.840 to 0.832; standardized, 0.872 in both.

Without scaling, humidity, which runs from 6 to 100 % on these days, carried 54 % of the expected distance between two random days, and pressure in kPa, 2.6 %. AUC was 0.840; with the 15 variables standardized, 0.872, and with MinMaxScaler, 0.864.

In the SVM post, writing pressure in Pa sank the unscaled SVM from 0.835 to 0.555. It cost KNN less: it dropped to 0.832, even though pressure now carried 100 % of the distance. The reason is in the data. Pressure comes with two decimals and has only 899 distinct values in 66,466 rows. In Pa, 59 % of each day’s 50 neighbors had exactly its pressure, against 1.2 % in kPa, and among those ties the other variables kept choosing. Multiplying pressure by a million, 96 % of the neighbors shared the pressure and AUC fell to 0.807. Pressure alone scored 0.679. Standardized, the model did not change with either unit.

Choosing k

• validation, equal votes
• validation, 1/distance
• its own training days, equal votes

With k = 1 the model scored 1.000 on its own days and 0.687 on 2010-2012, with log loss 8.05: each probability was 0 or 1. Validation peaked at k = 100 with 1/distance votes, 0.873, only 0.0004 above equal votes. From k = 50 to 300 the curve moves less than 0.003; at 2,000 with equal votes it drops to 0.861. Refit on 1984-2012, the chosen model scored 0.870 on 2016-2026.

I tried k from 1 to 2,000 with equal votes and with votes weighted by inverse distance. With k = 1 AUC on 2010-2012 was 0.69 and log loss 8.05, because every probability was 0 or 1. The winner was k = 100 with inverse-distance-weighted votes, 0.873, just 0.0004 above equal votes. Between k = 50 and k = 300 the curve moved less than 0.003, so on this data, within that range, the exact choice changed little. Refit on 1984-2012, the chosen model scored 0.870 on 2016-2026.

The red line is KNN with equal votes scoring its own training days, where each day counts as its own neighbor: 1.000 with k = 1, 0.934 with k = 5 and 0.888 with k = 100. Scored on the data it stored, KNN looks much better than it is.

In many dimensions, near and far look alike

Adding 135 noise columns dropped AUC from 0.873 to 0.827; with Euclidean distance on standardized variables every column weighs the same, so a useless one adds distance without adding information. In uniform data with 2 dimensions the nearest point was at 0.003 of the farthest; with 150, at 0.695. The real table, in 15 dimensions, gave 0.026, against 0.268 for uniform data with 15: its nearest neighbor sits much closer than the farthest.

With Euclidean distance on standardized variables, every column weighs the same. I added normal noise columns to the 15 standardized variables: with 5, AUC on 2010-2012 fell from 0.873 to 0.865; with 45, to 0.847, and with 135, to 0.827. No noise column carried information, but all of them added distance.

The second half of the chart is the geometric reason, the one Beyer and coauthors described in 1999, and Aggarwal and coauthors in 2001. Among 20,000 uniform random points, the distance to the nearest neighbor was 0.003 of the distance to the farthest in 2 dimensions, 0.27 in 15 and 0.69 in 150. The real table, in 15 dimensions, gave 0.026: for real days the nearest neighbor sits much closer than the farthest, and validation AUC shows that closeness still helps predict.

A forward feature selection on 20,000 rows of 1984-2009, scored on 2010-2012, kept 8 of the 15: today’s rain, latitude, both wind components and wind speed, pressure change, maximum temperature and humidity. With k = 150 and distance-weighted votes, re-chosen on 2010-2012, it scored AUC 0.870 on 2016-2026, the same as all 15 variables. The subset came out 0.0007 higher, a difference with no interval computed, and it stores 8 of the 15 columns per row.

Training is cheap; querying is not

• brute force, 1 thread
• brute force, 8 threads
• kd_tree
• ball_tree
• fit

With all 74,145 rows, fitting took 0.007 s and scoring the test period 5.47 s on one thread and 0.77 s on eight. On one thread, the trees did not help in 15 dimensions: kd_tree took 9.05 s and ball_tree 12.45 s. Stored rows grew 37 times; exhaustive scoring time grew 10.4 times.

With all 74,145 rows, fitting took 0.007 s in the cost run: the scaler computes means and standard deviations, and scikit-learn stores the scaled rows with their labels. Scoring the 27,256 test rows against it took 5.5 s on one thread and 0.77 s on eight. From 2,000 to 74,145 stored rows, 37 times more, scoring time grew 10 times.

The scikit-learn documentation says a kd_tree, the tree Bentley proposed in 1975, is very fast in low dimensions, below 20, and becomes inefficient as they grow. With these 15 and k = 100 it was slower: kd_tree took 9.1 s and ball_tree 12.4 s on one thread, longer than exhaustive search. The serialized model takes 9.5 MB, which is the table.

Whose neighbors are they?

85.8 % of neighbors came from the same city and 88.9 % were within 30 days of the same date in the year. Latitude and day of year are among the 15 variables, so city and season weigh directly in the distance; the weather variables fill in the rest.

With all 74,145 rows stored and k = 100, 85.8 % of the neighbors of each 2016-2026 day came from its own city and 88.9 % were within 30 days of its date in the year. Latitude and day of year are among the 15 variables, so city and season weigh directly in the distance. Santiago found 99.8 % of its neighbors in Santiago; Temuco only 64 %, with 23 % in Concepción. KNN can be explained by showing the neighbors, and that also exposes its mistakes: on 1 January 2021 it rained the next day in Santiago, and of the 100 most similar days of 1984-2012, only 3 were followed by rain.

Probabilities in steps

With equal votes and k neighbors, the probability can only take k + 1 values. On 2016-2026, with k = 1 every row got 0 or 1 and log loss was 7.64; with k = 5, 1.36, and with k = 50, 0.385. The chosen model weighs by distance and produced 24,229 distinct values, with log loss 0.370. Even so, 11 % of rows got exactly 0 or 1: all 100 neighbors agreed. Logistic regression scored 0.378 and boosting 0.332.

The model predicted 23.8 % rain on average against 20.3 % observed. Logistic regression predicted 24.1 % and boosting 23.4 %: all three learned from 1984-2012, when 26.6 % of days were followed by rain, against 20.3 % in the test period; the bias is consistent with that change in frequency.

Shrinking what is stored

With 3,200 prototypes KNN scored 0.864 in 0.42 s; the full table, 0.870 in 5.70 s, 14 times slower. With 50 prototypes AUC fell to 0.826. The prototypes come in equal numbers per class, which distorts the rain frequency: log loss was 0.429 against 0.370 for the full table. Ranking ability largely survived; the probabilities would need calibrating before use.

If the cost is in the stored rows, they can be replaced with fewer points. Hart proposed in 1968 keeping only the necessary examples; here I used K-Means centroids fit separately on days followed by rain and days followed by dry weather, with k over the prototypes chosen on 2010-2012. With 3,200 prototypes, KNN scored AUC 0.864 on 2016-2026 and scored the test period in 0.42 s; the full table, in the same run, scored 0.870 in 5.7 s. With 50 prototypes, 0.826 in 0.015 s.

The cost shows up in the probabilities. With the same number of prototypes in each class, the share of rainy neighbors no longer reflects the real frequency, and log loss was 0.429 against 0.370; part of that gap may come from slightly worse ranking. Ranking ability largely survived; the probabilities would need calibrating before use.

For numbers: KNN regression

KNeighborsRegressor predicts the average of the neighbors. For tomorrow’s maximum temperature, k = 20 was best on 2010-2012, and refit on 1984-2012 it missed by 1.58 °C on average on 2016-2026; linear regression by 1.70 °C and boosting by 1.44 °C.

In the series’ extrapolation test, training on Santiago’s April to September months and predicting the 2016-2026 summers, KNN never went above 28.0 °C. The hottest day it had seen was 32.97 °C and the real summer averaged 29.63 °C. An average of neighbors cannot leave the range of what it stored, and KNN missed by 4.31 °C; boosting, which did not go above 29.56 °C either, by 5.48 °C. Linear regression missed by 1.72 °C. It is a seasonal cut, not a clean out-of-range test: summer changes several variables at once.

KNN, boosting, forest, tree and logistic regression

TrainScore the test period

KNN, k = 100 · AUC 0.8700.014 s

Logistic regression · AUC 0.8470.049 s

Tree, depth 7 · AUC 0.8620.37 s

Boosting, 594 rounds · AUC 0.8832.604 s

Forest, 200 trees · AUC 0.88223.812 s

At a quarter of real time.

Logistic regression0.001 s

Tree, depth 70.002 s

Forest, 200 trees0.319 s

Boosting, 594 rounds0.583 s

KNN, k = 1005.771 s

The 27,256 rows, in real time.

Scoring a single day took KNN 1.9 ms, boosting 3.1 ms and logistic regression 0.4 ms. Serialized, KNN takes 9.5 MB, boosting 2.1 MB and the forest 124 MB.

With the same rows, I resampled the city-year blocks of 2016-2026 2,000 times to compare AUC in pairs. KNN was below boosting by 0.013 (95 % interval: −0.017 to −0.010) and below the forest by 0.013, and above the depth-7 tree by 0.008 and logistic regression by 0.023. None of the four intervals crosses zero. One-day latency was 1.9 ms in this run and 2.5 ms in the cost run, and fitting 0.014 and 0.007 s: with times this small, two runs do not give the same number.

Where KNN lives in a real system

Measured on one thread with all 74,145 rows: KNN "trains" in 0.014 s, weighs 9.5 MB serialized because it is the table, scores one day in 1.87 ms and the 27,256 test rows in 5.8 s (AUC 0.870). Boosting: trains in 2.6 s, 3.06 ms per day, 2.1 MB, AUC 0.883. Logistic regression: 0.40 ms, AUC 0.847.

• Similarity search. Recommendations, similar documents or past cases: the same principle with high-dimensional vectors, often over an approximate index such as HNSW (Malkov and Yashunin) instead of exhaustive search.
• Tables that change often. There are no coefficients to re-optimize: a new example is one more row, although with a scikit-learn pipeline you refit and decide whether to update the scaler.
• Explaining with examples. A prediction can be justified by showing the similar days behind it.
• A baseline to measure against. With 15 standardized variables, KNN beat logistic regression and the tree, and came within 0.013 of boosting.

When I would choose it: for small or medium tables of well-scaled numeric variables, when the data changes often or when similar examples need to be shown. When not: when every prediction has to be cheap over many rows, when there are many irrelevant columns, when units are not under control or when it has to extrapolate. On this data a boosting model got higher AUC and lower log loss, and scored the test period ten times faster.

Sources

• Fix, E. and Hodges, J. L. (1989). “Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties”. International Statistical Review, 57(3). Reprint of the 1951 report. DOI 10.2307/1403797.
• Cover, T. and 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. and 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. and 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. and 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, nearest neighbors.
• NASA POWER, Daily API and data sources.