The nearest neighbour

Two stored examples, written as points whose coordinates are their feature values, one coordinate per feature: (2, 3) labelled 0, and (6, 1) labelled 1. A query arrives at (5, 1). Which label should it receive?

First you require a numerical measure of how far apart two examples are. Subtract feature by feature, square each difference, add the squares, and extract the square root. From (2, 3) to (5, 1) the differences are −3 and 2, the squares 9 and 4, the sum 13, and the root 3.606. From (6, 1) to (5, 1) the differences are 1 and 0, the squares 1 and 0, the sum 1, and the root 1. The second example is closer, so the query inherits its label and the prediction is 1. !Three stored examples and one query. The distance from the query to A is 3.61, to B is 1, and to C is 8. The small circle of radius 1 holds B alone, so at k = 1 the answer is B's label, 1. The circle of radius 8 holds all three, whose labels are 0, 1 and 0, so at k = 3 the vote is two to one for 0. Status: schematic.

The rule is now one sentence long: identify the stored example that is closest to the query and return its label. An example selected that way is the query's nearest neighbour, and the recipe that produces the number is a distance metric. The recipe used above is the Euclidean distance, which measures straight-line separation with one coordinate for every feature [S:47:31]. !The same two rows and query under two units for the horizontal feature. On the left, width is recorded in centimetres: the width gap is 10 and the query takes the circle's label, 0. On the right, width is recorded in metres: the same gap is 0.1, the height gap decides, and the query takes the cross's label, 1. The rows did not move; the unit did. Status: schematic.

Write it once for d features, with ρ for the distance:

Read the formula in the order you would compute it. The index j runs over the features from 1 to d; x_j is feature j of the first example, and x'_j is feature j of the second, where the prime marks the second example rather than a derivative. For each j take one difference, then square it, then add the d squares, then take the root. Barber, whose textbook supplied the digit experiment in section 2.1, records the identical quantity without the final root and calls it the squared Euclidean distance [S:51:337]. Omitting the root changes every non-zero distance and changes no ordering, so either version returns the identical neighbour.

Why square each difference at all, rather than adding the absolute sizes of the differences? Two considerations answer that question. A difference of −3 and a difference of 3 describe the identical separation, and squaring renders them equal. Squaring also permits one large disagreement to count for more than several small ones, which is a decision about what "far" means.

Now permit more than one neighbour, because a single example can be atypical or mislabelled. Sort the stored examples by distance, retain the first k, and return the label that occurs most often among them; that is the k-nearest neighbours rule [S:51:339]. The fraction of the k examples carrying a particular label is its vote share, and the shares sum to one across the labels.

Worked example. Three stored examples: A at (2, 3) labelled 0, B at (6, 1) labelled 1, and C at (5, 9) labelled 0, with the query at (5, 1). From the calculation above, A is 3.606 away and B is 1 away, and C differs by 0 in the first feature and 8 in the second, so its distance is 8.

With k = 1 the closest example is B and the prediction is 1. With k = 3 the labels are 0, 1 and 0, so 0 occurs twice and wins, and the vote shares are two thirds and one third. The table and the query did not change; only the quantity of the table that the rule was permitted to read changed.

Adjusting this rule means storing the entire table, and there is no training phase because nothing is estimated [S:47:32]. A training phase is the part of a method's run in which it reads stored rows and fixes what it will use later. To estimate a quantity is to compute it from a finite sample rather than know it in advance. Here the rule fixes nothing, and the computational cost moves to the query, which measures the distance to every stored example and touches every feature each time. That expense is easy to overlook, because the fitting stage where other methods expend their effort does not exist here.

Two stored examples can occupy exactly the same distance from the query, and then "the closest row" designates more than one example. The rule requires a tie rule before it can be executed twice and produce the same answer, and the identical difficulty arises in a vote, where an even k can leave two labels possessing equal counts. Specifying the tie rule is part of defining the predictor, not an afterthought to it.

The choice matters more than the algorithm does. An algorithm is a finite list of steps that turns an input into an output. Hal Daumé's machine-learning course gives a ski and snowboard example in which width and height are recorded in different units. Change the unit of one feature and its numbers change scale while the other feature's numbers stay put; in his version the width values end up small enough that the rule ignores width and classifies almost by height alone [S:47:33].

Nothing was calculated incorrectly in either version, and no quantity of additional data repairs the change. The same trap waits in text: coding four colours as 0, 1, 2 and 3 asserts an ordering and a spacing that nobody measured [S:47:30]. A distance is an assertion about which differences matter, and the assertion is yours.

The formal statement. A distance on an input space $X$ is a function $\rho$ that takes two inputs and returns a number, subject to three conditions. First, $\rho (x,x^{\prime })=0$ exactly when $x=x^{\prime }$. Second, $\rho (x,x^{\prime })=\rho (x^{\prime },x)$. Third, $\rho (x,x^{\prime \prime })\le \rho (x,x^{\prime })+\rho (x^{\prime },x^{\prime \prime })$ for every third input. A function with these properties is a metric, and the third condition is the triangle inequality. Euclidean distance meets all three; the triangle inequality follows from Minkowski's inequality, and that verification is the step I omit.

The nearest-neighbour rule is then a definition rather than an algorithm: order the stored rows by $\rho (x,x_i)$, take the first in that order, and answer with its label. The ordering needs a tie rule, and Barber gives one: when several rows share the smallest distance, take the most numerous label among them [S:51:338]. Without that clause the rule is not a function.

The proof. The core claims that dropping the square root changes every non-zero distance and preserves every ordering. Let $f(t)=\sqrt{t}$, which is strictly increasing for $t\ge 0$. If the squared distance to row $i$ is at most the squared distance to row $j$, then applying $f$ gives the same inequality for the distances themselves, and applying $f$ in reverse gives the converse. The two orders therefore agree, and the smallest element is the same row. The argument holds for any strictly increasing $f$ and fails for any other: squaring is safe, and reversing the order is not.

The edge case. The axioms do not prevent the metric from ignoring a coordinate. Suppose $\rho$ compares only the first feature, so two rows that agree there sit at distance zero whatever their second entry. With such a metric a query can have two nearest neighbours at distance zero carrying different labels, and the rule has no answer until the tie clause supplies one. All three axioms hold and the predictor is useless. Daumé's ski and snowboard example is the gradual version: recorded in units that make the width numbers small, the width coordinate contributes little, and the rule reads height alone, with nothing computed wrongly in either version [S:47:33].

What the core left out. The decision boundary of the one-neighbour rule is the perpendicular bisector between stored rows that carry different labels, so the rule partitions the input space into a Voronoi tessellation with a piecewise linear boundary [S:51:337]. The core needed one query, not the whole partition. The partition matters at 2.6: it shows how much shape a rule with no parameters can produce.

Original sources. The algorithm with its tie clause is Algorithm 14.1 in Barber [S:51:338]. The metric formulation, with $\rho$ mapping two inputs to a number and the $k$-nearest-neighbour rule defined by a reordering of the sample, is chapter 19 of Shalev-Shwartz and Ben-David [S:79:258]. Fitting is storage in this rule, so the whole dataset is carried into prediction [S:47:32]. Szeliski records the classical result: Cover and Hart showed in 1967 that the rule is statistically optimal in the large-sample limit [S:89:269].

An open question. Which distance to use remains a modelling decision with no general answer. Euclidean distance treats the $d$ coordinates as commensurable, and nothing in the table certifies that they are [S:51:337]. Learned distances replace the fixed metric with one fitted to the data [S:66:104], but a fitted metric is chosen on rows that then score it, which returns you to the problem of 2.4. Evidence that would settle a case: a metric selected on a selection set and scored once on a test set, together with an argument that it is invariant to the transformations you know to be irrelevant. Without the second part you have fitted an invariance instead of stating it.

A frontier method. Approximate nearest-neighbour search makes the rule usable at scale. The FLANN library collects several index structures, and Faiss scales similarity search to billions of vectors [S:89:269]. The rule itself is unchanged; what changes is that the neighbour returned may not be the true nearest, so the method trades a stated amount of accuracy for time. The trade is measurable: fix a recall level, then compare the time each index needs to reach it on your data.

What to read next. Read chapter 19 of [S:79:258] for the finite-sample analysis, section 6.2 of [S:77:177] for the k-nearest-neighbour estimate as a local averaging method, and section 16.1 of [S:63:578] for the two-dimensional pictures. Then read section 5.1.1 of [S:89:269] for the indexing literature.