k nearest neighbours

Examples

\(k\) nearest neighbours has no parameters to fit. To predict at a new input we find the \(k\) closest training points and average their responses.

\[ \hat f(x) = \frac{1}{k}\sum_{i \in N_k(x)} y_i \]

For classification we take the most frequent class among the \(k\) neighbours, or the class frequencies as probabilities.

Regression

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsRegressor, KNeighborsClassifier

rng = np.random.default_rng(14)

def f(x):
    return np.sin(2 * x) + 2 * (x - 0.5) ** 3 - 0.5 * x

n, sigma = 60, 0.15
x = rng.uniform(0, 1, n)
y = f(x) + rng.normal(0, sigma, n)
X = x.reshape(-1, 1)
grid = np.linspace(0, 1, 400).reshape(-1, 1)

The same \(k\) applied to a regression and to a classification problem. Small \(k\) gives a rough fit and a jagged boundary. Large \(k\) gives a smooth fit and an almost straight boundary.

Here \(k\) plays the role that the degree played for polynomials, but in the other direction. Small \(k\) means flexible. Large \(k\) means rigid.

With \(k = 1\) the training error is exactly zero, because the nearest neighbour of a training point is itself. This is a good reminder that a training error of zero means nothing.

for k in [1, 5, 30]:
    m = KNeighborsRegressor(n_neighbors=k).fit(X, y)
    print(f"k = {k:2d}   training MSE = {np.mean((m.predict(X) - y)**2):.5f}")

k =  1   training MSE = 0.00000
k =  5   training MSE = 0.01308
k = 30   training MSE = 0.03762

Choosing k

Classification

With \(k = 1\) the boundary is jagged and it follows every single point. With \(k = 25\) it is almost a straight line.

Properties

\(k\) nearest neighbours does no work at fit time and all the work at predict time. For every prediction it has to find the nearest points among all training points, so prediction is slow when \(n\) is large.

It needs a distance, so the scale of the inputs matters. Standardize first, or a predictor measured in millimeters will dominate one measured in meters.

It suffers badly from the curse of dimensionality. In high dimensions all points are roughly equally far apart, so the nearest neighbours of a point are not actually near it. On MNIST, with \(p = 784\), it still works reasonably, because the images live on a much lower dimensional surface inside that space.