K-Nearest Neighbours Regression

KNN regression predicts a value by looking up the k training points with the closest x and averaging their y. There is no equation to fit: the data itself is the model.

The idea

Guessing the price of a house? Look at the few most similar houses that sold recently and take their average. That is the whole algorithm.

Here similarity means distance along the x-axis. The number of neighbours, k, controls the trade-off: a few neighbours copy local detail, many neighbours blur it into a smooth trend.

How it works

  1. Store every training point. That is the entire training phase.
  2. To predict at some x, measure the horizontal distance to every stored point.
  3. Keep the k closest ones.
  4. Average their y values, either equally or weighting closer neighbours more heavily.

Reading the picture

The curve is the prediction at every x across the canvas. With Equal weighting it is a staircase: the prediction only changes when a new point enters the set of k nearest. With By distance weighting the steps soften and the curve passes through each training point.

Turn on Show residuals to see the vertical gaps between points and the curve. Training MSE in the stats is the mean of their squares.

Try this

  1. On Wave, set Neighbours (k) to 1. The curve jumps to every point's height and copies all the noise.
  2. Now slide Neighbours (k) up to 30. The wave flattens out, because each prediction now averages over a big chunk of the axis.
  3. Switch Weighting to By distance with k around 10. The curve goes through every point again but stays smooth in between.
  4. Load Outliers and compare k = 1 with k = 9. Larger k quietly outvotes the strays.

The maths

Neighbours

Nk(x)=the k training points with smallest ∣x−xi∣N_k(x) = \text{the } k \text{ training points with smallest } \lvert x - x_i \rvert

Equal weights

y^(x)=1k∑i∈Nkyi\hat{y}(x) = \frac{1}{k} \sum_{i \in N_k} y_i

Distance weights

y^(x)=∑iwiyi∑iwi,wi=1∣x−xi∣\hat{y}(x) = \frac{\sum_i w_i y_i}{\sum_i w_i}, \quad w_i = \frac{1}{\lvert x - x_i \rvert}

Training MSE

MSE=1n∑i(yi−y^(xi))2\text{MSE} = \frac{1}{n} \sum_i \big(y_i - \hat{y}(x_i)\big)^2

Strengths and weaknesses

Good at

  • No assumptions about the shape of the curve.
  • One intuitive knob: k.
  • Adding data is instant, with no retraining.

Struggles with

  • Every prediction scans the whole dataset.
  • Flattens out beyond the edges of the data.
  • Struggles when there are many input features.