Ties and the choice of k
Section of Nearest neighbours, part of Statistical learning
Ties and the choice of k
| Type | Section |
| Taught in | Nearest neighbours |
| Part | Statistical learning |
Definition 1 (k-nearest neighbours) Given a metric, order the training points by increasing distance from a query x. The 1-nearest-neighbour rule predicts the label of the closest training point. The k-nearest-neighbour rule predicts the majority label among the k closest. A soft version uses the class proportions in that neighbourhood as an estimate of \tau_g(x).
There are two kinds of ties. Several observations can be equally distant, and several classes can receive the same vote. With exactly k voters and two classes, odd k rules out a vote tie. Software that includes every observation tied at the kth distance can use more than k voters, so that shortcut may no longer apply. Record the tie convention, and the seed, when random tie breaking is used.
The neighbourhood size is a bias–variance choice, and the apparent error cannot make it. The neighbours of a new x are useful when they carry the class probabilities that hold at x. If the regions where one class has the highest true posterior are large and roughly spherical in the scaled predictor space, a k with k/n not tiny can be used: many neighbours still lie inside the region. If those regions are small or winding, a large neighbourhood mixes in the other class, and a smaller k is required. The smallest choice is k=1. Nothing guarantees that the single nearest training point is close enough to x to say anything useful, particularly in high dimension, where most neighbours of a point are far away.
Small k produces a jagged boundary, flexible and variable from sample to sample. Large k produces a smooth boundary, stable and biased toward the majority. At k=n every query has the same neighbours, the whole sample, and the rule always predicts the majority class. On the iris petal plane the regions for k=1 follow the local labels closely, the regions for a moderate k such as 7 smooth the boundary, and a neighbourhood as large as 35 pulls the decision toward the majority species. In practice k is chosen by cross-validation. The apparent error always prefers k=1, for the same reason the 1-nearest-neighbour apparent error is zero: each training point is its own nearest neighbour.
Small neighbourhoods follow local noise. Large ones can smooth away a real minority-class pocket. Only a held-out comparison can tell whether added detail improves prediction. The iris picture illustrates the geometry. It does not claim that the true iris Bayes boundary is known.
Used in
See also
Rank distance · -nearest neighbours · Bayes consistency of -nearest neighbours · Distance and scale in nearest neighbours · Consistency and the factor of two · Laboratory: what a distance metric changes · Cover–Hart bound