k-Nearest Neighbours: Classification by Peer Pressure

The whole algorithm fits in one sentence

To classify a new point, find the k labelled training points closest to it and let them vote: the majority class among those k neighbours becomes the prediction. That is the entire algorithm - there is no training phase in the usual sense, no weights to fit, no loss function to minimise. k-NN simply stores the labelled data and defers every decision to query time, which is why it is called a lazy learner, in contrast to an eager learner like logistic regression or a neural network that does its work up front.

classify(query, k):
  distances = [ (dist(query, x_i), label_i) for each training point x_i ]
  neighbours = k points with smallest distance
  return the majority label among neighbours    // ties broken by smallest k or nearest

k=1 and the jagged Voronoi boundary

With k=1, every query point simply inherits the label of its single nearest training example, which means the decision boundary is exactly the edges of the training set's Voronoi diagram - the region around each point where it is the closest one. This boundary bends around every individual example, including noisy or mislabelled ones, giving very low bias on the training set but high variance: a small perturbation to the data can swing predictions in a whole neighbourhood. It is the textbook picture of overfitting made visible as a jagged, spiky region rather than an abstract number.

Choosing k: the bias-variance dial

Raising k averages the vote over more neighbours, which smooths the decision boundary and reduces variance - but push k too high and the boundary washes out entirely, eventually just predicting the globally most common class everywhere, which is maximum bias and minimum usefulness. In practice k is chosen by cross-validation, often restricted to an odd number for binary classification to avoid ties, and a common starting rule of thumb is k around the square root of the number of training examples.

Distance metrics matter as much as k

"Closest" depends entirely on the distance function. Euclidean distance is the default, but it silently assumes every feature is on a comparable scale - a feature measured in thousands will dominate one measured in single digits unless the data is standardised first. Manhattan distance is more robust to outliers along individual axes, and Minkowski distance generalises both with an exponent parameter. Feature scaling is not optional for k-NN the way it can be for some other algorithms; get it wrong and the "nearest" neighbours are really just the points closest along whichever feature happens to have the largest raw range.

The curse of dimensionality, and speeding up the search

A brute-force query checks the distance to every stored point, which is O(n) per prediction - fine for small datasets, painful at scale. Spatial index structures such as kd-trees and ball trees cut this down to roughly O(log n) in low dimensions by recursively partitioning the space so whole regions can be discarded without individually checking every point inside them. That speed-up erodes as the number of features grows, because of the curse of dimensionality: in high-dimensional spaces, the volume grows so explosively that data points become sparse and nearly equidistant from one another, so the very idea of a meaningfully "close" neighbour starts to break down, and spatial indexes degrade toward brute-force performance. Dimensionality reduction or feature selection before running k-NN is the standard remedy.

Frequently asked questions

Try it live

Everything above runs in your browser — open k-Nearest Neighbours and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.