k-Nearest Neighbors

Classify by majority vote of the nearest training points.

The idea

k-nearest-neighbour (k-NN) classification predicts the label of a new point directly from the training set. Most classifiers fit a function to the training data and then discard the data; k-NN instead keeps the training set and consults it afresh for every query.

Algorithm.

Algorithm: k-NN Classification Input: a training set of labelled points, a query point q, a neighbour count k Output: a predicted label for q 1. compute the distance from q to each training point x // on a line d(q, x) = |q - x|; in the plane, straight-line distance 2. keep the k training points of smallest distance // the k nearest neighbours of q 3. tally the labels of those k neighbours 4. return the label occurring most often // the majority vote

The method fits nothing and estimates no parameters, which is what non-parametric means; it assumes only that points lying close together tend to share a label.

The choice of $k$ controls how many neighbours influence the prediction. At $k = 1$ the prediction copies one training point: it reproduces every training label exactly and changes wherever the nearest point changes, so the decision boundary follows the sample in detail, including its accidents. Larger $k$ averages more neighbours, which steadies the prediction and smooths the boundary, at the cost of missing a genuinely intricate one. At $k = n$ every query returns the majority label of the entire training set.

Ways to work on it

• Walkthrough. Distance, the majority vote, and the role of k.
• Practice. Classify a query by majority vote of its neighbors.
• Hardest. Rank by Euclidean distance in the plane, then vote.

Not sure where to start? Take the ten-question placement test.