Nearest neighbours: predict what similar past cases did

The simplest learning rule there is: to predict a new case, look up the most similar cases you have seen and copy what they did. Nothing is fitted. The data is the model. This post runs it on the series’ problem, predicting next month’s volatility from seven features of this month, and uses it to show three things that matter for every model: a dial that runs backwards, why scaling matters, and what happens as features pile up.

The rule

Store every training row. For a new row, measure its distance to every stored row, keep the $k$ closest, and predict their average (for a number) or their majority (for a category). Distance is the ordinary straight-line kind, across all the features at once:

The last row is distance weighting: closer neighbours count for more. It helps a little on smooth problems and does nothing on this one (8.55 against 8.44 at $k = 20$).

The k dial runs backwards

Every model has a dial that trades memorising against generalising. For a tree it is depth, for a polynomial it is degree, and in both cases turning it up makes the model more flexible. For nearest neighbours the dial is $k$, and turning it up makes the model simpler: more neighbours are averaged, the prediction is smoother, and at $k = N$ every query gets the global mean.

Real run. Next month’s volatility, 3,685 training months, 2,405 test months, features standardised, $k$ from 1 to all of them:

The curve is the first panel of the chart, and it is the bias and variance trade-off drawn with the x-axis reversed. At $k = 1$ the model reproduces the training months perfectly and does worse on new months than saying “22” every time. At $k = 100$ it averages a hundred similar months and matches the linear model. The effective number of parameters is about $N / k$: 3,685 at $k = 1$, 37 at $k = 100$.

Scaling: distance uses raw numbers

Distance adds squared differences across features, so a feature measured in bigger units dominates. In the training rows, the 20-day return has a spread of 0.079 and the Bollinger position a spread of 0.64; the raw distance is nearly all Bollinger position. The second panel of the chart draws one test month and its twenty nearest training months, first on raw features and then on standardised ones (each feature rescaled to spread 1). The two sets of “nearest” months are different months. Standardising takes the test RMSE at $k = 20$ from 9.01 to $\key{8.44}$.

Fit the scaler on the training rows and apply it to the test rows; fitting it on everything leaks the test set’s mean into the model. Trees do not need any of this, because a split only asks whether a value is above or below a threshold.

Cost: free to train, expensive to ask

Training is nothing more than storing the rows. Every prediction then scans all $N$ rows across all $p$ features, so the cost per query is $N \times p$ and it grows with the data. A linear model costs $p$ per query. The gap is 180 times here and grows with every row added. Daily allocation over a few thousand rows is trivial and comes with an explanation (“this month looks like these twenty”); a high-frequency book with half a million rows per tick is not a job for this model. Tree indexes speed up the search in low dimensions and fall back to brute force above about twenty features.

The curse of dimensionality

In many dimensions, everything is far from everything. Spread points evenly in a unit box and ask how wide a sub-box must be to contain 10% of them:

With a hundred features, the ten percent of points nearest you span nearly the whole range of every feature; they are not neighbours in any useful sense. Scaling fixes units; it does not fix this. Real run. Add random noise columns to the seven real features:

Noise features push distances around at random, so the neighbours chosen are less and less the right ones; the linear model simply gives the noise columns weights near zero. The fixes are to drop irrelevant features, or to give each feature its own weight chosen on validation data, which a tree does on its own by ignoring features it never splits on.

When to use it

Nearest neighbours wins when the true relationship is complicated overall but simple locally, there are few features, and there are many rows per feature. A linear model wins when the truth is nearly linear, when rows are scarce, or when a feature list is long. If the neighbour model is only slightly better, keep the linear one: it is cheaper to run and comes with coefficients you can read.

Traps

The code

import numpy as np
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

for k in (1, 5, 20, 100, 500):
    model = make_pipeline(StandardScaler(), KNeighborsRegressor(n_neighbors=k))
    model.fit(X_train, y_train)                           # stores the rows; the scaler is fitted here
    rmse = np.sqrt(np.mean((y_test - model.predict(X_test)) ** 2))

weighted = make_pipeline(StandardScaler(), KNeighborsRegressor(20, weights="distance"))

Summary

Next

Bias and variance: where the error curve above comes from, and why every model has a dial like $k$.

References

• James, Witten, Hastie, Tibshirani and Taylor, An Introduction to Statistical Learning, with Applications in Python (Springer, 2023), sections 2.2.3 and 3.5: the k dial, and KNN against linear regression as features are added
• Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997), chapter 8: instance-based learning, distance weighting and the curse of dimensionality
• scikit-learn: nearest neighbors