Choosing k

Three neighbours instead of one turn eighteen errors into fourteen on the 600 held-back digits [S:51:339], so four images change side while nothing else in the rule moves.

One neighbour is one vote, and one vote is one label, so a single stored row that carries an unusual, badly written or wrongly recorded label, perhaps by a tired person, decides the answer on its own. A vote is the count of labels among the k neighbours, and the label with the largest count wins, so asking three neighbours needs two corrupt labels instead of one to overturn the answer. That is what raising k buys, and it is a gain against local noise, the probability that a row near the query carries an atypical or wrong label. !Seven stored rows at distances 1 to 7 from the query, with labels 1, 0, 0, 0, 1, 1, 0. At k = 1 the answer is the nearest label, 1. At k = 3 the labels are 1, 0, 0, so 0 wins two votes to one. At k = 7 the four 0s outvote the three 1s, and the answer stops depending on where the query sits, because every stored row is inside the patch. Status: schematic.

The charge arrives in the same arithmetic, because neighbours are ordered by distance and the third therefore sits at least as far away from the query as the first. The question concerned one input, and the answer now derives from a patch, the region around the query that holds the k nearest rows. The wider the patch, the less its answer has to do with the point at the middle. !Selection-set error against k on one data set. The curve falls while extra neighbours outvote local noise, reaches a lowest point, then rises as the patch widens and stops describing the query. At k equal to the number of stored rows it returns the commonest stored label for every query. The lowest point is where k is chosen, and the curve belongs to the data, not to the method. Status: synthetic.

Worked example. Seven stored rows sit at distances 1, 2, 3, 4, 5, 6 and 7 from the query, with labels 1, 0, 0, 0, 1, 1 and 0. At k = 1 the nearest label is 1, and at k = 3 the labels are 1, 0 and 0, so 0 wins two votes to one. At k = 7 the labels are four 0s and three 1s, so 0 wins again.

The three answers are 1, 0 and 0, because the first follows a single row and the second follows three, while the third would be the same for every query. When k equals the number of stored rows, the rule returns the most frequent stored label and has stopped consulting the query [S:51:339], which is why a dial that can reach such a setting is not a minor detail.

The choice cannot be determined from the stored rows, because there k = 1 wins every time: every stored row is its own nearest neighbour. The choice requires a third portion of the data, a selection set, scored once with the test set untouched [S:93:335]. A tuning parameter is a choice such as k that is set from data other than the rows the rule stores.

No single value of k is appropriate for every problem: in one controlled experiment, the best setting of the tuning parameter differed for two problems built from the same features, the same sample size and the same code [S:64:487]. The error curve, the graph of selection-set error against k, is a property of the data rather than a law governing the method. You choose k at its lowest point on that curve, and published practice begins at three or five, with values between fifty and a hundred on collections far larger than six hundred rows [S:93:335].

Two considerations limit the possible gain: odd k makes a tied vote less probable, but it does nothing about two rows at an identical distance, and nothing about a three-way vote of two, two and one [S:93:335]. When neighbouring labels never disagree, additional neighbours have no disagreement to outvote, so they can only widen the patch and add error. That situation is not rare, which is why no rule of the form "always use more than one neighbour" survives contact with data.

The formal statement. Fix $k$ and a query $x$. Call the $k$ stored rows closest to $x$ the neighbourhood, ordered by distance. For each label $c$, the vote share is the fraction of that neighbourhood carrying $c$, and the rule answers the label with the largest share. The shares are non-negative and add to one over the labels, so a largest share always exists. It need not be unique, and a tie needs its own clause before the rule is a function.

The derivation. The trade-off the core describes in words has a known shape. Let the noise about the best predictor the distribution allows have variance ${\sigma }^2$. Under a Lipschitz condition on the target, the expected squared error of the $k$-nearest-neighbour estimate splits into two terms. One falls like $1/k$, because $k$ noisy labels are averaged and the noise divides. The other grows like $(k/n{)}^{2/d}$, because the $k$-th neighbour sits at a radius of order $(k/n{)}^{1/d}$ and the patch therefore widens as $k$ grows. Balancing the two gives a best $k$ that grows like $n^{2/(2+d)}$ [S:77:186].

The exponent is the substance of the core's claim that the best $k$ is a property of the data. It is a property of the sample size and the dimension as well, and the two enter through a single power.

The edge case. At $k=n$ the neighbourhood is the whole table, the vote share becomes the global frequency of each label, and the answer stops depending on $x$. The rule still returns a label; it has stopped being a prediction about the query. Ties behave in a similar way. An odd $k$ removes the two-label tie, because an odd number cannot split evenly in two. It does nothing about a three-label tie, which needs only three labels with equal counts. The tie in distance and the tie in votes are separate events, and no choice of $k$ removes the first.

What the core left out. The exponent $2/(2+d)$ says how fast the method can learn, and it also says why the method stays a baseline. Cutting the error by a fixed factor costs a fixed power of the data, and that power rises with $d$, so the requirement grows exponentially in the dimension [S:63:578]. The core presented the widening patch as a cost in locality. It is a cost in sample size as well, and the second cost is the one that ends the method's usefulness in high dimension.

Original sources. The result that three neighbours cut eighteen errors to fourteen is Barber's [S:51:339]. The practical rules are in Manning, Raghavan and Schütze [S:93:335]: odd $k$ makes ties less likely, three and five are common, values between fifty and a hundred appear on large collections, and $k$ can be chosen on a held-out portion. The warning that the best setting depends on the situation comes from the comparative study in Hastie, Tibshirani and Friedman [S:64:487].

An open question. How to choose $k$ without a search that costs a pass over the data is not settled. Theory gives the scaling $n^{2/(2+d)}$ under a Lipschitz assumption on the target [S:77:186], and it gives no usable constant: the constant contains the Lipschitz bound and the noise level, and you know neither. Evidence that would settle a case: learning curves measured over $n$ and $d$ on one task, showing that the empirical optimum follows the predicted exponent. Where it does not, the Lipschitz assumption is the thing to doubt, and that doubt is testable.

A frontier method. Adaptive nearest-neighbour rules modify the neighbourhood itself, stretching the metric along directions where the labels change quickly [S:64:487]. They keep the vote and change what counts as near, which is the same move as the metric discussion in 2.2, and they attack the bias term rather than the variance term. Their cost is the extra fitting, and the fitting needs data that the vote cannot then use. A rule of this kind can express a boundary that a fixed metric cannot, because the relevant directions may differ from region to region.

What to read next. Read section 6.3.2 of [S:77:185] for the rate and its proof. Read section 13.3 of [S:64:487] for the comparative study and the error curve. Read section 14.3 of [S:93:335] for the same rule in a retrieval setting, where the cost of the search is the subject.