KNN regression

Predict the (optionally distance-weighted) average target of the k nearest training points.

15 min read1378 wordscore7 viewsupdated 2026-10-07

Definition

KNN regression predicts a number for a new input qq by finding the kk training points closest to qq and averaging their targets, either equally or with closer points counting more. It fits no parameters. The stored training set is the model, and the shape of the prediction curve comes entirely from the data.

At a glance

Task
Regression (numeric target)
Input → output
query q∈Rdq\in\mathbb{R}^d → y^(q)\hat y(q), a (weighted) mean of kk training targets
Learns
nothing: it stores all nn pairs (xi,yi)(x_i, y_i) ("lazy" or instance-based learning)
Training cost
O(1)O(1) to store; O(dnlog⁡n)O(dn\log n) if you build a KD-tree or ball tree
Prediction cost
O(nd)O(nd) per query by brute force; roughly O(log⁡n)O(\log n) with a tree index in low dimension
Hyperparameters
n_neighbors k, weights (uniform or distance), distance metric (p), index algorithm
Assumes
the target changes smoothly: points close in your metric have similar yy. Features must be on comparable scales

The problem

Electricity demand against outdoor temperature has a U-shape. Cold days need heating, hot days need air-conditioning, and mild days need the least. A straight line (see linear regression) cannot bend, so it fits this U badly. On the 12-day dataset below, the best line explains only R2=0.256R^2=0.256 of the variance, and its leave-one-out error is 39.17 GWh², which is worse than always predicting the mean.

You could add x2x^2 and fit a parabola (polynomial regression). But that only works if you guess the right functional form. The real curve might be flat on one side, kinked at 18 °C, or bumpy. KNN regression makes no guess about the shape. It says: to predict demand at 21 °C, look at what happened on the days with temperatures nearest 21 °C.

The idea

Picture the training points as a scatter plot. Put a vertical line at the query qq and widen a window around it until it contains kk points. The prediction is the average height of those points. Slide qq along the axis and the window slides with it, so the prediction traces a curve that follows the data's local level, wherever it goes.

With k=1k=1 you copy the nearest point's target exactly, which reproduces every bit of noise. With k=nk=n every window contains the whole dataset, so you predict the global mean everywhere. Everything useful lies between those two extremes, and choosing kk is the whole game.

Vocabulary

Query point q
the input you want a prediction for
Neighbourhood N_k(q)
the indices of the kk training points closest to qq
k-th neighbour distance
d(k)(q)d_{(k)}(q), the radius of the smallest ball around qq that holds kk training points. It shrinks where data is dense and grows where data is sparse
Uniform weighting
every neighbour gets weight 1/k1/k, so y^\hat y is a plain mean
Distance weighting
neighbour ii gets weight ∝1/d(q,xi)\propto 1/d(q,x_i), so nearer points pull harder
Lazy learner
all work happens at prediction time; "training" just stores the data
Smoother
a method whose prediction is a weighted average ∑iℓi(q) yi\sum_i \ell_i(q)\,y_i of training targets. KNN is a linear smoother: the weights depend on xx, not on yy

The math

Fix a distance (usually Euclidean, d(q,x)=∥q−x∥2d(q,x)=\lVert q-x\rVert_2). Sort the training points by distance to qq and keep the first kk. Their indices form Nk(q)N_k(q).

y^(q)=1k∑i∈Nk(q)yi\hat y(q)=\frac{1}{k}\sum_{i\in N_k(q)} y_i
qq
query input
Nk(q)N_k(q)
indices of the kk training points nearest to qq
yiy_i
target of training point ii
kk
number of neighbours averaged

Why the mean? Ask for the single constant cc that best fits the neighbours in squared error, J(c)=∑i∈Nk(q)(yi−c)2J(c)=\sum_{i\in N_k(q)}(y_i-c)^2. Setting J′(c)=−2∑i(yi−c)=0J'(c)=-2\sum_i (y_i-c)=0 gives kc=∑iyikc=\sum_i y_i, so cc is the mean. KNN regression is therefore a local constant least-squares fit: at each query it solves a tiny regression problem using only nearby points. Under absolute error the same argument gives the neighbours' median instead, which is a robust variant.

y^(q)=∑i∈Nk(q)wi yi∑i∈Nk(q)wi,wi=1d(q,xi)\hat y(q)=\frac{\sum_{i\in N_k(q)} w_i\,y_i}{\sum_{i\in N_k(q)} w_i},\qquad w_i=\frac{1}{d(q,x_i)}
wiw_i
weight of neighbour i; larger for closer points
d(q,xi)d(q,x_i)
distance from the query to neighbour ii

This is the minimiser of the weighted squared error ∑iwi(yi−c)2\sum_i w_i (y_i-c)^2. Repeat the derivative: ∑iwi(yi−c)=0⇒c=∑iwiyi/∑iwi\sum_i w_i(y_i-c)=0 \Rightarrow c=\sum_i w_iy_i/\sum_i w_i. Distance weighting makes the curve continuous and lets it pass through every training point, because as q→xiq\to x_i the weight wi→∞w_i\to\infty. If qq sits exactly on a training point, scikit-learn gives that point all the weight.

How k trades bias for variance. Assume yi=f(xi)+εiy_i=f(x_i)+\varepsilon_i, where the noise εi\varepsilon_i has variance σ2\sigma^2, and treat the training inputs as fixed. Then the expected squared error at qq splits into three parts:

E[(y−y^(q))2]=σ2+[f(q)−1k∑i∈Nk(q)f(xi)]2+σ2k\mathbb{E}\big[(y-\hat y(q))^2\big]=\sigma^2+\Big[f(q)-\frac1k\sum_{i\in N_k(q)}f(x_i)\Big]^2+\frac{\sigma^2}{k}
ff
the true, unknown regression function
σ2\sigma^2
irreducible noise variance
[⋯ ]2[\cdots]^2
squared bias: how far the neighbours' true values sit from f(q) on average
σ2/k\sigma^2/k
variance: averaging k independent noises divides their variance by k

Raising kk shrinks the variance term σ2/k\sigma^2/k. But it also pulls in neighbours that are further away, whose f(xi)f(x_i) differs more from f(q)f(q), so the bias grows. When k=1k=1 the bias is close to 0 and the variance equals σ2\sigma^2. When k=nk=n the variance is σ2/n\sigma^2/n, but the bias equals the whole gap between f(q)f(q) and the global mean. The theory says KNN is consistent (its error approaches the noise floor) if k→∞k\to\infty while k/n→0k/n\to0. In practice you pick kk by cross-validation. The bias–variance trade-off article covers this decomposition in general.

Worked example: temperature → electricity demand

Twelve days of an illustrative regional grid: daily mean temperature xx (°C) and electricity demand yy (GWh). We want the demand on a 21 °C day, using k=3k=3.

DayTemp x (°C)Demand y (GWh)
1−2.541.8
20.037.9
33.032.1
45.530.4
57.527.1
610.525.4
713.022.6
817.023.7
920.023.4
1024.026.9
1127.528.8
1230.532.6
Training data. Highlighted: the 3 days nearest to the query q = 21 °C.

Predict demand at q = 21 °C

  1. 1Distances. With one feature, d=∣xi−21∣d=|x_i-21|. The nearest days are 20 °C (d=1d=1), 24 °C (d=3d=3), 17 °C (d=4d=4), then 27.5 °C (d=6.5d=6.5) and 13 °C (d=8d=8).
  2. 2Keep the 3 nearest: days 9, 10 and 8, with targets 23.4, 26.9 and 23.7. The neighbourhood radius is d(3)=4d_{(3)}=4 °C, so the window is [17, 25].
  3. 3Uniform average: y^=13(23.4+26.9+23.7)=74.03=\hat y=\tfrac13(23.4+26.9+23.7)=\tfrac{74.0}{3}= 24.67 GWh.
  4. 4Distance weights: w=1/1, 1/3, 1/4=1, 0.333, 0.25w=1/1,\ 1/3,\ 1/4 = 1,\ 0.333,\ 0.25, and ∑w=1.583\sum w=1.583.
  5. 5Weighted sum: 1(23.4)+0.333(26.9)+0.25(23.7)=23.4+8.967+5.925=38.291(23.4)+0.333(26.9)+0.25(23.7)=23.4+8.967+5.925=38.29.
  6. 6Distance-weighted prediction: 38.29/1.583=38.29/1.583= 24.18 GWh. The 20 °C day carries 1/1.583=63%1/1.583=63\% of the weight, so the prediction moves toward its 23.4.
kNeighbours (°C)Uniform ŷ1/d-weighted ŷ
12023.4023.40
220, 2425.1524.27
320, 24, 1724.6724.18
520, 24, 17, 27.5, 1325.0824.46
12all29.3925.88
The same query for other k. Uniform weighting drifts toward the global mean 29.39 as k grows; 1/d weighting stays anchored to the closest days. The straight line predicts 27.19.

To choose kk, use leave-one-out cross-validation: predict each day from the other 11 and average the squared errors. With uniform weights, k=1k=1 gives 8.62 GWh², k=2k=2 gives 7.08, k=3k=3 gives 11.81, and k=11k=11 gives 38.40. With 1/d1/d weights the best is again k=2k=2, at 5.68. Both are far below the straight line's 39.17. Training error tells you nothing here: with k=1k=1 it is exactly 0, because every point is its own nearest neighbour.

demand (GWh) vs temperature (°C) · — KNN fit · drag the query q2025303540-5051015202530ŷ = 24.67q = 21.0°Cleave-one-out MSE vs k (uniform) · best k = 20204011.801234567891011
20° d 1.0 · y 23.4 · w 0.33324° d 3.0 · y 26.9 · w 0.33317° d 4.0 · y 23.7 · w 0.333
ŷ(21.0) = (1/3)·Σ y = 24.67 GWh · neighbourhood radius 4.0°C
fig.The 12 days from the table. Drag the orange handle to move the query: its k nearest days light up, and the shaded band is the neighbourhood (radius = k-th distance). Line thickness shows each neighbour's weight. At q = 21 °C with k = 3, the prediction is 24.67 (uniform) or 24.18 (1/distance). The blue curve is the full KNN fit: uniform weighting gives a step function that flattens to the mean 29.39 at k = 12, while 1/distance passes through every point. The lower chart is leave-one-out MSE for each k (click a dot). The best is k = 2, at 7.08 uniform or 5.68 weighted, against 39.17 for the linear fit.

Reading the fitted curve

With one feature and uniform weights, the prediction only changes when the query's set of kk neighbours changes. That happens at midpoints between training points, so the fit is a step function. Unlike a regression tree, whose steps come from a few learned splits, KNN has a step at every point where its neighbour set changes. Three effects are worth seeing in the figure:

At a glance

Boundary bias
at the coldest day (−2.5 °C, demand 41.8), every neighbour lies to the right, at warmer and lower-demand days. With k=3k=3 the fit there is (41.8+37.9+32.1)/3=37.27(41.8+37.9+32.1)/3=37.27, which is 4.5 GWh too low. The averaging window cannot centre itself on an edge point
No extrapolation
at 40 °C (hotter than any training day) k=3k=3 predicts 29.43, the mean of the three hottest days, and it would predict the same at 50 °C. KNN outputs always lie inside the range of the training targets. The straight line predicts 21.95 at 40 °C, which is wrong in the other direction
Adaptive width
the window has a fixed count, not a fixed width. Where days are dense it is narrow; where they are sparse it widens automatically

The algorithm, step by step

fit(X, y) and predict(q)

  1. 1Fit: scale the features (store the means and standard deviations), then store X and y. Optionally build a KD-tree or ball tree over X.
  2. 2Distances: for a query qq, compute d(q,xi)d(q,x_i) for all nn training points. Brute force costs O(nd)O(nd).
  3. 3Select: take the kk smallest distances. A partial selection (argpartition) does this in O(n)O(n), without a full O(nlogn)O(nlog n) sort.
  4. 4Weight: wi=1w_i=1 (uniform) or wi=1/d(q,xi)w_i=1/d(q,x_i). If some d=0d=0, use only those exact matches.
  5. 5Average: return ∑wiyi/∑wi\sum w_iy_i/\sum w_i.
  6. 6Tune: choose kk (and the weighting and metric) by cross-validated MSE or MAE, never by training error.

Complexity. Training is free, and memory is O(nd)O(nd) because the whole dataset is the model. A batch of mm queries costs O(mnd)O(mnd) by brute force. Tree indexes cut a query to roughly O(log⁡n)O(\log n) when dd is small (under about 20). In high dimension they degrade back to brute force, and approximate nearest-neighbour libraries (FAISS, HNSW, Annoy) take over, trading exactness for speed.

Variants and tuning

ChoiceOptionsEffectStarting point
k (n_neighbors)1 … nsmall k: low bias, high variance; large k: smooth fit, flattens peaks and edgesgrid over 1–50 with CV; often near √n
weightsuniform, distance, or a callable1/d makes the fit continuous and less sensitive to large k; it interpolates the training data exactlytry both. 1/d helps when density varies
Metric (p)p=2 Euclidean, p=1 Manhattan, cosine…defines which points count as near; Manhattan is less dominated by one large differenceEuclidean on standardized features
Feature scalingstandardize, min-max, robustdecides how much each feature matters to distancealways, inside a Pipeline
Radius neighboursRadiusNeighborsRegressorfixed window width instead of fixed count; can find no neighbours in sparse areaswhen a physical radius makes sense
Kernel smoothingNadaraya–Watson, LOESSsmooth kernel weights K(d/h)K(d/h); LOESS fits a local line, which removes boundary biaswhen you need a smooth curve
Index (algorithm)brute, kd_tree, ball_tree, ANNspeed only. Results are identical, except for ANNauto; ANN for millions of points
The knobs, what they do, and sensible defaults.

In code

python
1import numpy as np
2
3def knn_regress(X_train, y_train, Q, k=3, weights="uniform"):
4 """Predict each row of Q as the (weighted) mean target of its k nearest rows."""
5 d = np.sqrt(((Q[:, None, :] - X_train[None, :, :]) ** 2).sum(-1)) # (n_q, n_train)
6 idx = np.argsort(d, axis=1, kind="stable")[:, :k] # k nearest
7 dk = np.take_along_axis(d, idx, axis=1)
8 yk = y_train[idx]
9 if weights == "uniform":
10 return yk.mean(axis=1)
11 with np.errstate(divide="ignore"):
12 w = 1.0 / dk
13 exact = np.isinf(w) # a query sitting on a training point
14 w[exact.any(axis=1)] = exact[exact.any(axis=1)] # ... takes that point's value
15 return (w * yk).sum(axis=1) / w.sum(axis=1)
16
17def loo_mse(X, y, k, weights="uniform"):
18 err = []
19 for i in range(len(y)):
20 m = np.arange(len(y)) != i
21 err.append((y[i] - knn_regress(X[m], y[m], X[i:i + 1], k, weights)[0]) ** 2)
22 return np.mean(err)
23
24temp = np.array([-2.5, 0, 3, 5.5, 7.5, 10.5, 13, 17, 20, 24, 27.5, 30.5])
25demand = np.array([41.8, 37.9, 32.1, 30.4, 27.1, 25.4, 22.6, 23.7, 23.4, 26.9, 28.8, 32.6])
26X, q = temp[:, None], np.array([[21.0]])
27
28for k in (1, 3, 5, 12):
29 print(k, knn_regress(X, demand, q, k).round(2), knn_regress(X, demand, q, k, "distance").round(2))
30# 1 [23.4] [23.4] / 3 [24.67] [24.18] / 5 [25.08] [24.46] / 12 [29.39] [25.88]
31for w in ("uniform", "distance"):
32 scores = [loo_mse(X, demand, k, w) for k in range(1, 12)]
33 print(w, "best k =", int(np.argmin(scores)) + 1, "LOO MSE =", round(min(scores), 2))
34# uniform best k = 2 LOO MSE = 7.08
35# distance best k = 2 LOO MSE = 5.68
From scratch in NumPy: vectorized prediction, both weightings, and leave-one-out selection of k. Prints 24.67 / 24.18 at k = 3 and best k = 2 (LOO MSE 7.08 uniform, 5.68 distance).
python
1import numpy as np
2from sklearn.neighbors import KNeighborsRegressor
3from sklearn.model_selection import GridSearchCV, LeaveOneOut
4from sklearn.metrics import mean_squared_error, r2_score
5
6temp = np.array([-2.5, 0, 3, 5.5, 7.5, 10.5, 13, 17, 20, 24, 27.5, 30.5])
7demand = np.array([41.8, 37.9, 32.1, 30.4, 27.1, 25.4, 22.6, 23.7, 23.4, 26.9, 28.8, 32.6])
8X = temp[:, None]
9
10knn = KNeighborsRegressor(n_neighbors=3).fit(X, demand)
11dist, idx = knn.kneighbors([[21.0]])
12print("neighbours:", temp[idx[0]], "distances:", dist[0]) # [20. 24. 17.] [1. 3. 4.]
13print("uniform k=3 :", knn.predict([[21.0]]).round(2)) # [24.67]
14print("distance k=3:", KNeighborsRegressor(3, weights="distance").fit(X, demand).predict([[21.0]]).round(2)) # [24.18]
15print("train MSE k=3:", round(mean_squared_error(demand, knn.predict(X)), 2),
16 "R2:", round(r2_score(demand, knn.predict(X)), 3)) # 3.15, 0.903
17
18search = GridSearchCV(
19 KNeighborsRegressor(),
20 {"n_neighbors": range(1, 12), "weights": ["uniform", "distance"]},
21 cv=LeaveOneOut(), scoring="neg_mean_squared_error",
22).fit(X, demand)
23print(search.best_params_, "LOO MSE:", round(-search.best_score_, 2)) # k=2, distance, 5.68
24print("q=21 ->", search.predict([[21.0]]).round(2)) # [24.27]
25
26# With several features, always scale inside the model:
27# from sklearn.pipeline import make_pipeline; from sklearn.preprocessing import StandardScaler
28# model = make_pipeline(StandardScaler(), KNeighborsRegressor(n_neighbors=10, weights="distance"))
scikit-learn: the same prediction, the neighbours it used, and a leave-one-out grid search over k and weighting.

Use when

  • +The relationship is nonlinear and you do not know its shape: KNN follows the data with no functional form assumed.
  • +You have few features (or a good learned embedding) and plenty of data that covers the input space densely.
  • +New data arrives constantly: adding a point is instant, with no retraining.
  • +You want predictions explained by example: "these 5 similar houses sold for…".

Avoid when

  • −There are many features or many irrelevant ones: distances concentrate and neighbourhoods stop being local.
  • −You must extrapolate beyond the training range, or capture a trend at the edges.
  • −Latency or memory is tight: every prediction scans (or indexes) the whole training set.
  • −Features have mixed units or categories that do not have a natural distance.

Where it's used

Real-estate comparables

Appraisers price a home from the sale prices of the most similar recently sold homes: KNN regression on size, location and age.

Missing-value imputation

KNNImputer fills a missing numeric field with the mean of that field over the k most similar complete rows.

Collaborative filtering

Predict a user's rating of an item as the similarity-weighted average rating from the k most similar users who rated it.

Short-term load and weather analogues

Forecast demand or rainfall by averaging what followed the k most similar past days ("analogue forecasting").

Check yourself

A query's three nearest neighbours have targets 23.4, 26.9 and 23.7 at distances 1, 3 and 4. What is the uniform k = 3 prediction?

Check yourself

With uniform weights and k = n (all 12 days), what does KNN regression predict at q = 21 °C — and at every other q?

Check yourself

On the temperature data, what does k = 3 (uniform) predict for a 40 °C day, which is hotter than any training day?

Check yourself

Under y=f(x)+εy=f(x)+\varepsilon with noise variance σ2=4\sigma^2=4, what is the variance term of a uniform k = 4 KNN prediction?

Remember

  • ✓KNN regression predicts y^(q)\hat y(q) as the mean of the kk nearest targets, which is the least-squares constant fitted to the neighbourhood. With 1/d1/d weights it is the weighted mean.
  • ✓kk is the bias–variance dial: the variance term is σ2/k\sigma^2/k, and the bias grows as neighbours get further away. k=nk=n predicts the global mean everywhere. Pick kk by cross-validation.
  • ✓Uniform KNN gives a step-function fit; distance weighting gives a continuous fit that interpolates the training points.
  • ✓It cannot extrapolate, and it is biased at the edges of the data, because predictions always stay inside the range of the neighbours' targets.
  • ✓Scale the features, keep the dimensionality low, and use tree or ANN indexes when n is large.
← back to ML Algorithms roadmap