k nearest neighbours

Examples

Regression

To predict at a new input, find the \(K\) closest training points and average their responses.

Left, the training data, the \(K\) nearest neighbour fit and the data generator. Right, the training and the test loss at every \(K\), plotted against the flexibility \(1/K\), with the current \(K\) marked on both curves.

\(K\) plays the role the degree played for polynomials, but the other way round: the flexible end is \(K = 1\), on the right of the loss plot. At \(K = 1\) the training loss is exactly zero, because the nearest neighbour of a training point is itself, and the test loss is at its worst. The \(K\) with the lowest test error follows the noise — 2 at \(\sigma_{\text{gen}} = 0.01\), 6 at \(0.1\), 13 at \(0.2\) — because averaging more neighbours is how the method reduces uncertainty due to noise.

There is nothing to fit, so the whole method is one call. The training error at \(K = 1\) is the one number worth reading off it.

import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsRegressor

rng = np.random.default_rng(3)

def f(x):
    return 0.3 * np.sin(10 * x) + 0.7 * x

def regression_data(n, sigma=0.1, rng=rng):
    x = rng.uniform(0, 1, n)
    return pd.DataFrame({"x": x, "y": f(x) + sigma * rng.standard_normal(n)})

train, test = regression_data(50), regression_data(10**4)

for k in [1, 4, 20]:
    m = KNeighborsRegressor(n_neighbors=k).fit(train[["x"]], train["y"])
    tr = np.sqrt(np.mean((m.predict(train[["x"]]) - train["y"]) ** 2))
    te = np.sqrt(np.mean((m.predict(test[["x"]]) - test["y"]) ** 2))
    print(f"K = {k:2d}   training RMSE = {tr:.4f}   test RMSE = {te:.4f}")

1

Running this on more than a few predictors does not make much sense, and is very slow.

K =  1   training RMSE = 0.0000   test RMSE = 0.1518
K =  4   training RMSE = 0.0993   test RMSE = 0.1209
K = 20   training RMSE = 0.1579   test RMSE = 0.1532

Classification

For classification, take the class frequencies among those \(K\) neighbours as probabilities.

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

The same figure for the classification data. s_gen is the steepness of the logistic function in the generator.

\(K = 1\) gives a boundary that follows every single point, and a test loss far above the irreducible error. Similarly to the regression setting, the \(K\) with the lowest test error falls as the generator gets steeper (and therefore less noisy) — 41 at \(s_{\text{gen}} = 5\), 11 at \(20\), 5 at \(35\).

from sklearn.neighbors import KNeighborsClassifier

def logistic(z):
    return 1 / (1 + np.exp(-z))

def classification_data(n, s=20, rng=rng):
    X1, X2 = rng.uniform(0, 1, n), rng.uniform(0, 1, n)
    y = logistic(s * (f(X1) - X2)) > rng.uniform(0, 1, n)
    return pd.DataFrame({"X1": X1, "X2": X2, "y": y.astype(int)})

cls_train = classification_data(400)
m = KNeighborsClassifier(n_neighbors=3).fit(cls_train[["X1", "X2"]],
                                            cls_train["y"])
print("training accuracy:",
      round(m.score(cls_train[["X1", "X2"]], cls_train["y"]), 3))

training accuracy: 0.95

Handwritten digits

A one nearest neighbour classifier on MNIST. The fit is instant and the prediction is not: for each of the 10000 test images it has to find the closest of 60000 training images.

from sklearn.datasets import fetch_openml
from sklearn.neighbors import KNeighborsClassifier

mnist = fetch_openml("mnist_784", as_frame=False)
X, y = mnist.data / 255, mnist.target

m = KNeighborsClassifier(n_neighbors=1).fit(X[:60000], y[:60000])
print("error rate: ", (m.predict(X[60000:]) != y[60000:]).mean())

error rate:  0.0309

The misclassification rate is surprisingly low at about 3%.