A tempting wrong turn

Topic: Nearest neighbours · more questions on this topic
‹ The factor of two Normalisation and nearest neighbours ›

A student chooses k by minimising the training-set error of the k-nearest-neighbour classifier over k=1,\ldots,50, counting each training point as its own neighbour. What happens, and what should be done instead?

Worked answer (click to show)

If each training point may be its own neighbour, then for k=1 each point with a unique predictor vector is classified correctly, at distance 0 from itself, so the training error is 0. Then k=1 is always chosen. The apparent error is minimised by the most flexible classifier and says nothing about performance on new data. Use leave-one-out or K-fold cross-validation, with the ith point excluded from its own neighbour list, or a separate validation set, to choose k. For a final error estimate use a test set or nested cross-validation.