k-Nearest Neighbours

Given a point to classify, k-nearest-neighbours finds the k training observations nearest to it, estimates the class probabilities as the proportions among those neighbours, and predicts the most common one. Nothing is fitted in advance: the entire training set is retained and consulted at prediction time, which makes training instantaneous and prediction expensive - the reverse of most methods.

The choice of k controls flexibility directly. At k = 1 every training point is its own nearest neighbour, so training error is exactly zero and the boundary is jagged: a high-variance fit that responds to individual observations. As k grows the boundary smooths, variance falls and bias rises, until at k approaching the sample size almost the whole training set votes on every prediction and the classifier returns the majority class regardless of input.

Because it imposes no shape on the boundary, the method can approximate curved and disconnected decision regions that a linear model cannot represent at all. The price is that it has no way to ignore an irrelevant feature: every dimension contributes to the distance, so accuracy degrades as uninformative features are added - a form of the curse of dimensionality, in which the nearest neighbours in high dimensions are not close in any useful sense.

The distance metric deserves attention that it usually does not get. Euclidean distance on raw features lets a variable measured in large units dominate the calculation, so features should be standardised unless their relative scales are deliberately meaningful. The method also offers no coefficients and no summary: it can say what it predicts but not why, which rules it out where the reasoning has to be inspectable.

On a two-dimensional problem whose optimal error rate is 0.092708, k-nearest-neighbours fitted to 200 training points and scored on 20,000 test points gives an error of 0.138200 at k = 1, falls to a best value of 0.097150 at k = 15, and rises again to 0.103550 at k = 75.

At k = 199, out of 200 training points, the error reaches 0.504850 - essentially the class prior, because almost the entire sample votes on every prediction. At the other end, k = 1 has a training error of exactly zero while its test error is the worst of every k but the degenerate k = 199, which is the clearest possible demonstration that training error is not an estimate of test error.

The best value is interior, and there is no formula for it. It is chosen by cross-validation, and the shallow floor between k = 9 and k = 45 here is typical: the method is not usually sensitive to getting k exactly right, only to getting it roughly right.