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 well beyond this 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:

d(a, b) = \sqrt{\sum_j (a_j - b_j)^2}

**Table 1.** Worked examples of the rule: distance, average, vote and weights
Case	Working	Result
Distance from (1, 2) to (4, 6)	$\sqrt{3^2 + 4^2}$	5 (the “city-block” or Manhattan distance, walking along one feature at a time, is 3 + 4 = 7)
$k = 3$ , neighbours’ returns 1%, 2%, 3%	average	2%
$k = 5$ votes up, up, down, up, down	majority	up, with P(up) = 0.6
Weights by 1/distance, distances 1 and 3	1 and 0.33, rescaled to sum to 1	0.75 and 0.25

The last row of Table 1 is distance weighting: closer neighbours count for more. It helps a little on smooth problems and on this one it is slightly worse (test RMSE 12.43 weighted against 12.39 unweighted 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 (Table 2).

**Table 2.** What the model predicts at small, medium and largest k
$k$	What it predicts	Training error	Steady on new data?	Verdict
1	the nearest point’s own value	0	no: one odd neighbour decides	memorises
medium	a local average	some	in between	choose on validation
$N$ , all rows	the global mean, for every query	highest	completely, but it ignores the features	too simple

Figure 1. The k curve, the effect of scaling, and useless features added

Real run. Next month’s volatility, 4,930 training rows and 2,205 test rows (one per ticker per trading day), features standardised. Table 3 sweeps $k$ from 1 to all of them; the score is RMSE, the typical size of a miss in points of volatility, and lower is better:

**Table 3.** Training and test RMSE by k, next month’s volatility
$k$	Training RMSE	Test RMSE	Reading
1	$\key{0.00}$	$\risk{17.05}$	memorised: barely better than guessing the mean (17.69)
5	11.16	13.32	clearly better than the mean
20	12.54	12.39
100	13.60	$\key{12.27}$	the bottom, give or take ( $k = 50$ scores 12.19); better than a linear model (12.78)
500	15.13	12.86
4,930, all of them	19.59	17.69	the global mean, by construction

The curve is the first panel of Figure 1, and it is the bias and variance trade-off drawn with the x-axis reversed. At $k = 1$ the model reproduces the training rows perfectly and on new rows is barely better than guessing the training average every time, 17.05 against 17.69. At $k = 100$ it averages a hundred similar rows and beats the linear model, 12.27 against 12.78. A model like this has no fixed set of parameters: it keeps the training data, so its size grows with the data (Murphy calls such models nonparametric).

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 (standard deviation) of 0.100 and the Bollinger position a spread of 0.65; between those two, the raw distance is nearly all Bollinger position. The second panel of Figure 1 draws one test row and its twenty nearest training rows, first on raw features and then on standardised ones (each feature rescaled to spread 1). The two sets of “nearest” rows are different rows. Standardising takes the test RMSE at $k = 20$ from 13.58 to $\key{12.39}$ .

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

**Table 4.** Time to fit and to predict 2,205 rows, neighbours against a line
Item	Fit	Predict 2,205 rows
Nearest neighbours, $k = 20$	1.1 ms	$\risk{19.2}$ ms
Linear regression	0.6 ms	0.1 ms

Training is nothing more than storing the rows, the 1.1 ms in Table 4. 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 about 190 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 (Table 5):

**Table 5.** Side of a box holding 10% of evenly spread points, by dimension
Dimensions $p$	Side of the box, $0.1^{1/p}$	Meaning
1	0.10	a small local window
2	0.32
10	0.79	79% of every feature’s range
100	0.98	the “neighbourhood” is almost everything

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. Table 6 adds random noise columns to the seven real features:

**Table 6.** Test RMSE as noise features are added, neighbours against a line
Useless features added	Nearest neighbours, test RMSE	Linear regression, test RMSE
0	12.39	12.78
5	12.87	12.79
10	13.29	12.83
20	13.87	12.85
50	$\risk{14.60}$	12.81

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. Five noise columns are enough to hand the lead back to the linear model. 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, as it is here (12.27 against 12.78), keep the linear one: it is cheaper to run and comes with coefficients you can read.

Traps

Table 7 lists the traps.

**Table 7.** Traps in nearest neighbours
Trap	Truth
Larger $k$ overfits more	Smaller $k$ does; the dial runs backwards
$k = N$ predicts each point’s own label	It predicts the global mean for everything
Larger $k$ lowers training error	It raises it
Scaling cures high dimensions	It cures units, not the curse
More features always help	Irrelevant ones distort every distance
It is fast because training is cheap	Prediction is the cost, and it grows with the data
Appending new rows handles drift	Stale rows stay in the pool

The code

Made-up data, so it runs as pasted (pip install numpy scikit-learn): two useful features on very different scales, the way a 20-day return (numbers like 0.05) and a Bollinger position (numbers like 1) differ. X holds the features, one row per case; y holds the answer for each row. The first 1,500 rows train, the last 500 test.

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

# Made-up data: two useful features on very different scales
rng = np.random.default_rng(0)
n = 2000
small = rng.normal(0, 0.05, n)      # like a 20-day return: numbers around ±0.05
big = rng.normal(0, 1.0, n)         # like a Bollinger position: numbers around ±1
y = 20 + 80 * small + 4 * big + rng.normal(0, 3, n)   # the answer depends on both, plus noise
X = np.c_[small, big]               # one row per case, one column per feature
X_train, X_test, y_train, y_test = X[:1500], X[1500:], y[:1500], y[1500:]

def test_rmse(model, Xtr=X_train, Xte=X_test):
    model.fit(Xtr, y_train)                         # "fit" only stores the rows (and fits the scaler)
    return round(root_mean_squared_error(y_test, model.predict(Xte)), 2)

# 1. The k dial runs backwards: small k memorises, k = all rows predicts the average
for k in (1, 20, 100, 1500):
    print(f"k = {k:4}: test RMSE", test_rmse(make_pipeline(StandardScaler(), KNeighborsRegressor(k))))

# 2. Scaling: without it, distance is nearly all the big-number feature
print("k = 20, raw features:   ", test_rmse(KNeighborsRegressor(20)))
print("k = 20, scaled features:", test_rmse(make_pipeline(StandardScaler(), KNeighborsRegressor(20))))

# 3. Useless features: add 50 columns of pure noise and every distance gets blurred
noise_tr, noise_te = rng.normal(size=(1500, 50)), rng.normal(size=(500, 50))
print("k = 20, plus 50 noise columns:",
      test_rmse(make_pipeline(StandardScaler(), KNeighborsRegressor(20)),
                np.c_[X_train, noise_tr], np.c_[X_test, noise_te]))

It prints:

The dial: test RMSE 4.06 at $k = 1$ , the best 3.04 at $k = 20$ , 3.19 at $k = 100$ , and 6.41 with every row averaged, which is just the overall mean.
Scaling: 3.56 on raw features, 3.04 once scaled.
Useless features: 5.3 with fifty noise columns added.

The noise added to y has a spread of 3, so 3 is the floor no model can beat here.

The script behind the real numbers

The tables above come from examples/nearest-neighbours/knn.py, which runs on the blog’s five tickers. To run it yourself, clone the examples repo: its README has a three-command Docker setup, or run uv run nearest-neighbours/knn.py.

Summary

Table 8 is the post in six lines.

**Table 8.** Nearest neighbours in six rules
Idea	Rule	Remember it as
Prediction	average of the $k$ nearest stored rows	the data is the model
The $k$ dial	small $k$ complex, big $k$ simple	backwards from depth and degree
Size	grows with the data	it keeps every training row
Scaling	standardise, fitted on training rows	distance uses raw numbers
Cost	fit free, predict $N \times p$	the bill comes at query time
Curse	box side $= 0.1^{1/p}$ to hold 10% of the points	neighbourhoods explode; drop junk features

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
Kevin P. Murphy, Probabilistic Machine Learning: An Introduction (MIT Press, 2022), chapter 16: nonparametric models that keep the training data, and the curse of dimensionality, with the box-edge formula (16.1.2)
Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997), chapter 8: instance-based learning, distance weighting and the curse of dimensionality
scikit-learn: nearest neighbors