# KNN regression

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

Source: https://www.mlfoundry.in/learn/knn-regression  
Section: ML Algorithms › Supervised · Regression  
Level: core · 15 min read · updated 2026-10-07

**KNN regression:** predicts a number for a new input $q$ by finding the $k$ training points closest to $q$ 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.

- **Task:** Regression (numeric target)
- **Input → output:** query $q\in\mathbb{R}^d$ → $\hat y(q)$, a (weighted) mean of $k$ training targets
- **Learns:** nothing: it stores all $n$ pairs $(x_i, y_i)$ ("lazy" or instance-based learning)
- **Training cost:** $O(1)$ to store; $O(dn\log n)$ if you build a KD-tree or ball tree
- **Prediction cost:** $O(nd)$ per query by brute force; roughly $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 $y$. 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 $R^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 $x^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 $q$ and widen a window around it until it contains $k$ points. The prediction is the average height of those points. Slide $q$ 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=1$ you copy the nearest point's target exactly, which reproduces every bit of noise. With $k=n$ every window contains the whole dataset, so you predict the global mean everywhere. Everything useful lies between those two extremes, and choosing $k$ is the whole game.

**Vocabulary**

- **Query point q:** the input you want a prediction for
- **Neighbourhood N_k(q):** the indices of the $k$ training points closest to $q$
- **k-th neighbour distance:** $d_{(k)}(q)$, the radius of the smallest ball around $q$ that holds $k$ training points. It shrinks where data is dense and grows where data is sparse
- **Uniform weighting:** every neighbour gets weight $1/k$, so $\hat y$ is a plain mean
- **Distance weighting:** neighbour $i$ gets weight $\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 $\sum_i \ell_i(q)\,y_i$ of training targets. KNN is a *linear smoother*: the weights depend on $x$, not on $y$

## The math

Fix a distance (usually Euclidean, $d(q,x)=\lVert q-x\rVert_2$). Sort the training points by distance to $q$ and keep the first $k$. Their indices form $N_k(q)$.

$$
\hat y(q)=\frac{1}{k}\sum_{i\in N_k(q)} y_i
$$

- $q$: query input
- $N_k(q)$: indices of the $k$ training points nearest to $q$
- $y_i$: target of training point $i$
- $k$: number of neighbours averaged

**Why the mean?** Ask for the single constant $c$ that best fits the neighbours in squared error, $J(c)=\sum_{i\in N_k(q)}(y_i-c)^2$. Setting $J'(c)=-2\sum_i (y_i-c)=0$ gives $kc=\sum_i y_i$, so $c$ 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.

$$
\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)}
$$

- $w_i$: weight of neighbour i; larger for closer points
- $d(q,x_i)$: distance from the query to neighbour $i$

This is the minimiser of the **weighted** squared error $\sum_i w_i (y_i-c)^2$. Repeat the derivative: $\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\to x_i$ the weight $w_i\to\infty$. If $q$ sits exactly on a training point, scikit-learn gives that point all the weight.

**How k trades bias for variance.** Assume $y_i=f(x_i)+\varepsilon_i$, where the noise $\varepsilon_i$ has variance $\sigma^2$, and treat the training inputs as fixed. Then the expected squared error at $q$ splits into three parts:

$$
\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}
$$

- $f$: the true, unknown regression function
- $\sigma^2$: irreducible noise variance
- $[\cdots]^2$: squared bias: how far the neighbours' true values sit from f(q) on average
- $\sigma^2/k$: variance: averaging k independent noises divides their variance by k

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

> **Why KNN breaks down in high dimension:** Spread data uniformly in a unit cube in $d$ dimensions. To capture a fraction $r$ of it, a sub-cube needs edge length $r^{1/d}$. For 1% of the data that is 0.01 in 1-D, 0.215 in 3-D, **0.631 in 10-D** and 0.955 in 100-D. Your "local" neighbourhood then stretches across most of every feature's range, so the bias term blows up. KNN regression works best with a few informative features, or after dimensionality reduction.

## Worked example: temperature → electricity demand

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

Training data. Highlighted: the 3 days nearest to the query q = 21 °C.

| Day | Temp x (°C) | Demand y (GWh) |
| --- | --- | --- |
| 1 | −2.5 | 41.8 |
| 2 | 0.0 | 37.9 |
| 3 | 3.0 | 32.1 |
| 4 | 5.5 | 30.4 |
| 5 | 7.5 | 27.1 |
| 6 | 10.5 | 25.4 |
| 7 | 13.0 | 22.6 |
| 8 | 17.0 | 23.7 |
| 9 | 20.0 | 23.4 |
| 10 | 24.0 | 26.9 |
| 11 | 27.5 | 28.8 |
| 12 | 30.5 | 32.6 |

**Predict demand at q = 21 °C**

1. **Distances.** With one feature, $d=|x_i-21|$. The nearest days are 20 °C ($d=1$), 24 °C ($d=3$), 17 °C ($d=4$), then 27.5 °C ($d=6.5$) and 13 °C ($d=8$).
2. **Keep the 3 nearest:** days 9, 10 and 8, with targets 23.4, 26.9 and 23.7. The neighbourhood radius is $d_{(3)}=4$ °C, so the window is [17, 25].
3. **Uniform average:** $\hat y=\tfrac13(23.4+26.9+23.7)=\tfrac{74.0}{3}=$ **24.67 GWh**.
4. **Distance weights:** $w=1/1,\ 1/3,\ 1/4 = 1,\ 0.333,\ 0.25$, and $\sum w=1.583$.
5. **Weighted sum:** $1(23.4)+0.333(26.9)+0.25(23.7)=23.4+8.967+5.925=38.29$.
6. **Distance-weighted prediction:** $38.29/1.583=$ **24.18 GWh**. The 20 °C day carries $1/1.583=63\%$ of the weight, so the prediction moves toward its 23.4.

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.

| k | Neighbours (°C) | Uniform ŷ | 1/d-weighted ŷ |
| --- | --- | --- | --- |
| 1 | 20 | 23.40 | 23.40 |
| 2 | 20, 24 | 25.15 | 24.27 |
| **3** | **20, 24, 17** | **24.67** | **24.18** |
| 5 | 20, 24, 17, 27.5, 13 | 25.08 | 24.46 |
| 12 | all | 29.39 | 25.88 |

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

> Figure: 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 $k$ 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:

- **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=3$ the fit there is $(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=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

> **Unscaled features hijack the distance:** With several features, distance adds squared differences across them. If temperature is in °C (range about 33) and population served is in people (range about 10⁶), population decides every neighbourhood and temperature is ignored. Standardize (or min-max scale) inside a `Pipeline`, fitted on the training folds only. Scaling is part of the KNN model, not optional preprocessing.

## The algorithm, step by step

**fit(X, y) and predict(q)**

1. **Fit:** 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. **Distances:** for a query $q$, compute $d(q,x_i)$ for all $n$ training points. Brute force costs $O(nd)$.
3. **Select:** take the $k$ smallest distances. A partial selection (`argpartition`) does this in $O(n)$, without a full $O(nlog n)$ sort.
4. **Weight:** $w_i=1$ (uniform) or $w_i=1/d(q,x_i)$. If some $d=0$, use only those exact matches.
5. **Average:** return $\sum w_iy_i/\sum w_i$.
6. **Tune:** choose $k$ (and the weighting and metric) by cross-validated MSE or MAE, never by training error.

**Complexity.** Training is free, and memory is $O(nd)$ because the whole dataset is the model. A batch of $m$ queries costs $O(mnd)$ by brute force. Tree indexes cut a query to roughly $O(\log n)$ when $d$ 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

The knobs, what they do, and sensible defaults.

| Choice | Options | Effect | Starting point |
| --- | --- | --- | --- |
| k (`n_neighbors`) | 1 … n | small k: low bias, high variance; large k: smooth fit, flattens peaks and edges | grid over 1–50 with CV; often near √n |
| `weights` | uniform, distance, or a callable | 1/d makes the fit continuous and less sensitive to large k; it interpolates the training data exactly | try 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 difference | Euclidean on standardized features |
| Feature scaling | standardize, min-max, robust | decides how much each feature matters to distance | always, inside a Pipeline |
| Radius neighbours | `RadiusNeighborsRegressor` | fixed window width instead of fixed count; can find no neighbours in sparse areas | when a physical radius makes sense |
| Kernel smoothing | Nadaraya–Watson, LOESS | smooth kernel weights $K(d/h)$; LOESS fits a local *line*, which removes boundary bias | when you need a smooth curve |
| Index (`algorithm`) | brute, kd_tree, ball_tree, ANN | speed only. Results are identical, except for ANN | `auto`; ANN for millions of points |

> **KNN regression vs KNN classification:** The neighbour search is identical; only the last step differs. The classifier takes a vote over labels and reports class shares as probabilities (see **k-Nearest Neighbors**). The regressor takes a mean of numbers and is judged by MSE, MAE or R². For a robust regressor, swap the mean for the median of the neighbours' targets.

## In code

```python
import numpy as np

def knn_regress(X_train, y_train, Q, k=3, weights="uniform"):
    """Predict each row of Q as the (weighted) mean target of its k nearest rows."""
    d = np.sqrt(((Q[:, None, :] - X_train[None, :, :]) ** 2).sum(-1))  # (n_q, n_train)
    idx = np.argsort(d, axis=1, kind="stable")[:, :k]                  # k nearest
    dk = np.take_along_axis(d, idx, axis=1)
    yk = y_train[idx]
    if weights == "uniform":
        return yk.mean(axis=1)
    with np.errstate(divide="ignore"):
        w = 1.0 / dk
    exact = np.isinf(w)                       # a query sitting on a training point
    w[exact.any(axis=1)] = exact[exact.any(axis=1)]  # ... takes that point's value
    return (w * yk).sum(axis=1) / w.sum(axis=1)

def loo_mse(X, y, k, weights="uniform"):
    err = []
    for i in range(len(y)):
        m = np.arange(len(y)) != i
        err.append((y[i] - knn_regress(X[m], y[m], X[i:i + 1], k, weights)[0]) ** 2)
    return np.mean(err)

temp = np.array([-2.5, 0, 3, 5.5, 7.5, 10.5, 13, 17, 20, 24, 27.5, 30.5])
demand = 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])
X, q = temp[:, None], np.array([[21.0]])

for k in (1, 3, 5, 12):
    print(k, knn_regress(X, demand, q, k).round(2), knn_regress(X, demand, q, k, "distance").round(2))
# 1 [23.4] [23.4] / 3 [24.67] [24.18] / 5 [25.08] [24.46] / 12 [29.39] [25.88]
for w in ("uniform", "distance"):
    scores = [loo_mse(X, demand, k, w) for k in range(1, 12)]
    print(w, "best k =", int(np.argmin(scores)) + 1, "LOO MSE =", round(min(scores), 2))
# uniform best k = 2 LOO MSE = 7.08
# 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
import numpy as np
from sklearn.neighbors import KNeighborsRegressor
from sklearn.model_selection import GridSearchCV, LeaveOneOut
from sklearn.metrics import mean_squared_error, r2_score

temp = np.array([-2.5, 0, 3, 5.5, 7.5, 10.5, 13, 17, 20, 24, 27.5, 30.5])
demand = 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])
X = temp[:, None]

knn = KNeighborsRegressor(n_neighbors=3).fit(X, demand)
dist, idx = knn.kneighbors([[21.0]])
print("neighbours:", temp[idx[0]], "distances:", dist[0])   # [20. 24. 17.] [1. 3. 4.]
print("uniform k=3 :", knn.predict([[21.0]]).round(2))      # [24.67]
print("distance k=3:", KNeighborsRegressor(3, weights="distance").fit(X, demand).predict([[21.0]]).round(2))  # [24.18]
print("train MSE k=3:", round(mean_squared_error(demand, knn.predict(X)), 2),
      "R2:", round(r2_score(demand, knn.predict(X)), 3))     # 3.15, 0.903

search = GridSearchCV(
    KNeighborsRegressor(),
    {"n_neighbors": range(1, 12), "weights": ["uniform", "distance"]},
    cv=LeaveOneOut(), scoring="neg_mean_squared_error",
).fit(X, demand)
print(search.best_params_, "LOO MSE:", round(-search.best_score_, 2))  # k=2, distance, 5.68
print("q=21 ->", search.predict([[21.0]]).round(2))                    # [24.27]

# With several features, always scale inside the model:
# from sklearn.pipeline import make_pipeline; from sklearn.preprocessing import StandardScaler
# 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.

**Strengths**

- 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…".

**Limitations**

- 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.

- **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").

> **Choosing k on training error:** With `k=1`, or with `weights="distance"` at any k, the training predictions reproduce the training targets exactly, so training MSE is 0. On the worked example, training MSE at k = 1 is 0 but leave-one-out MSE is 8.62. Always pick k by cross-validation on held-out folds.

> **Duplicate and leaked neighbours:** If the same entity appears in both train and test (repeat customers, overlapping time windows), its own copy becomes the nearest neighbour and the error looks unrealistically good. Split by entity or by time, and in time series only allow neighbours from the past.

**Question:** 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?

- A. 23.40
- B. 24.18
- C. 24.67
- D. 26.90

**Answer:** C. 24.67 — The plain mean: $(23.4+26.9+23.7)/3=74.0/3=24.67$. The value 24.18 is the $1/d$-weighted mean, $38.29/1.583$.

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

- A. The target of the nearest day
- B. The global mean, 29.39
- C. The median, 27.1
- D. The least-squares line

**Answer:** B. The global mean, 29.39 — Every neighbourhood is the whole training set, so $\hat y=\frac1n\sum_i y_i=29.39$ everywhere. The bias term is maximal and the variance is minimal ($\sigma^2/n$).

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

- A. About 21.95, continuing the downward trend
- B. 29.43, the mean of the three hottest days
- C. Exactly 32.6
- D. It cannot predict outside the training range

**Answer:** B. 29.43, the mean of the three hottest days — The three nearest days to 40 °C are 30.5, 27.5 and 24 °C, with targets 32.6, 28.8 and 26.9, whose mean is 29.43. It predicts the same at 50 °C: KNN never extrapolates beyond the targets it has seen. 21.95 is what the straight line predicts.

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

- A. 4
- B. 2
- C. 1
- D. 0.25

**Answer:** C. 1 — Averaging $k$ independent noise terms divides the variance by $k$: $\sigma^2/k=4/4=1$. Increasing $k$ reduces this term but usually increases the bias term.

**Key points**

- KNN regression predicts $\hat y(q)$ as the mean of the $k$ nearest targets, which is the least-squares constant fitted to the neighbourhood. With $1/d$ weights it is the weighted mean.
- $k$ is the bias–variance dial: the variance term is $\sigma^2/k$, and the bias grows as neighbours get further away. $k=n$ predicts the global mean everywhere. Pick $k$ 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
