k-nearest neighbours

Neighbours, trees and ensemblesabout 8 minutes

The simplest classifier of all: to label a new point, find the $k$ training points closest to it and take a majority vote (or, for regression, average their targets). k-nearest neighbours (k-NN) has no training phase at all: the "model" is the training set itself. It was described by Fix and Hodges in 1951 and is still a strong baseline.

Each background cell is coloured by the vote of its k nearest training points. Small k gives jagged, noisy regions; large k smooths them.

Choosing k

k = 1: the boundary bends around every single training point, including mislabelled ones. Training accuracy is 100% (each point is its own neighbour), which tells you nothing. This is high variance: overfitting.
Large k: the vote averages over a wide area. Boundaries become smooth and eventually too simple; at $k = n$ every prediction is the majority class. This is high bias: underfitting.
In between is a sweet spot you find with validation data (module 3). Odd $k$ avoids ties for two classes.

Distance is everything

k-NN usually uses Euclidean distance, which adds up squared differences across features. If one feature is measured in thousands and another in fractions, the first completely dominates the distance and the second is ignored. Always standardise features for k-NN. And think about what "close" means for your data: for text, cosine similarity is often better than Euclidean distance.

The curse of dimensionality

In high dimensions, neighbourhoods stop being local. Spread points uniformly in a unit cube in $d$ dimensions: to capture 1% of them in a smaller cube you need a side length of $0.0 1^{1/ d}$ , which is 0.1 in 2-D but 0.63 in 10-D and 0.95 in 100-D. Your "nearest" neighbours are nearly as far away as everything else, and distances lose their meaning. Methods that rely on raw distance degrade, which is one reason learned representations (embeddings) matter so much.

side needed to capture a fraction f of a uniform cube = f^{1/ d}

Prediction is also slow for big datasets: a naive k-NN compares each query against every training point. Real systems use spatial indexes (k-d trees, ball trees) or approximate nearest-neighbour search, which is exactly how vector databases behind modern retrieval systems work.

try itedit the code and run it, nothing can break

python sleeps until you press run

k-NN memorises the data and votes. The choice of k trades noise for smoothness, and features must be scaled because distance is all it has.

← Numerically stable classification maths