k-Nearest Neighbors › Example

Before trusting code, it is worth carrying out one prediction entirely by hand. A single worked example with $k=3$ confirms that every operation (distance, ranking, tie-breaking, voting, averaging) is exactly what we think it is, and it exposes the one place where the rules leave us a choice.

Suppose a two-dimensional binary classification training set contains five points:

$$(\mathbf{x}_1, y_1) = ((1, 1), 0), \quad (\mathbf{x}_2, y_2) = ((2, 3), 0), \quad (\mathbf{x}_3, y_3) = ((3, 3), 1),$$ $$(\mathbf{x}_4, y_4) = ((4, 4), 1), \quad (\mathbf{x}_5, y_5) = ((5, 5), 1).$$

The query is $\mathbf{x}_q = (2.5, 2.5)$. Class-0 points sit near the origin, and class-1 points form a diagonal ridge going out toward $(5, 5)$, so the query lies between the two groups and the class votes are close. That is deliberate: an ambiguous query is exactly where the mechanics become visible.

Step 1: compute Euclidean distances to every training point.

For $\mathbf{x}_1$:

$$d(\mathbf{x}_q, \mathbf{x}_1) = \sqrt{(2.5 - 1)^2 + (2.5 - 1)^2} = \sqrt{2.25 + 2.25} = \sqrt{4.5} \approx 2.121.$$

For $\mathbf{x}_2$:

$$d(\mathbf{x}_q, \mathbf{x}_2) = \sqrt{(2.5 - 2)^2 + (2.5 - 3)^2} = \sqrt{0.25 + 0.25} = \sqrt{0.5} \approx 0.707.$$

For $\mathbf{x}_3$:

$$d(\mathbf{x}_q, \mathbf{x}_3) = \sqrt{(2.5 - 3)^2 + (2.5 - 3)^2} = \sqrt{0.25 + 0.25} = \sqrt{0.5} \approx 0.707.$$

For $\mathbf{x}_4$:

$$d(\mathbf{x}_q, \mathbf{x}_4) = \sqrt{(2.5 - 4)^2 + (2.5 - 4)^2} = \sqrt{2.25 + 2.25} = \sqrt{4.5} \approx 2.121.$$

For $\mathbf{x}_5$:

$$d(\mathbf{x}_q, \mathbf{x}_5) = \sqrt{(2.5 - 5)^2 + (2.5 - 5)^2} = \sqrt{6.25 + 6.25} = \sqrt{12.5} \approx 3.536.$$

The distances already show the ranking: $\mathbf{x}_2$ and $\mathbf{x}_3$ are closest and exactly tied, $\mathbf{x}_1$ and $\mathbf{x}_4$ form the next tier, and $\mathbf{x}_5$ is farthest. How we resolve the ties will decide which points enter the neighborhood, so it is worth handling them explicitly.

Step 2: sort the distances in increasing order:

$$0.707\;(\mathbf{x}_2), \quad 0.707\;(\mathbf{x}_3), \quad 2.121\;(\mathbf{x}_1), \quad 2.121\;(\mathbf{x}_4), \quad 3.536\;(\mathbf{x}_5).$$

Notice that $\mathbf{x}_2$ and $\mathbf{x}_3$ are exactly tied at $\sqrt{0.5}$, and $\mathbf{x}_1$ and $\mathbf{x}_4$ are tied at $\sqrt{4.5}$. Duplicate inputs or rounded and discrete features can produce exact ties in any dimension. This hand-designed coordinate set makes their effect visible. When they occur, we need a deterministic rule. We break equal-distance ties by training-row order, using np.argsort(..., kind="stable") in the implementation. If a class vote is tied, our classifiers choose the smallest class label. A different distance-tie rule can change the selected neighbor at the cutoff and therefore change the prediction.

Step 3: select the $k=3$ nearest neighbors. The first three sorted indices are $\{2, 3, 1\}$. Their labels are $y_2 = 0$, $y_3 = 1$, and $y_1 = 0$.

Step 4: count votes. Class 0 receives two votes and class 1 receives one vote. The majority class is therefore class 0, and our kNN prediction is $\hat{y}_q = 0$.

We can now check what happens with weighted voting. Suppose we use $w_i = 1/d_i^2$. The weights for the three neighbors are:

$$w_2 = \frac{1}{0.5} = 2, \quad w_3 = \frac{1}{0.5} = 2, \quad w_1 = \frac{1}{4.5} \approx 0.222.$$

where:

• $w_i$: weight assigned to neighbor $i$, equal to the reciprocal of its squared distance
• $d_i$: Euclidean distance from the query to neighbor $i$

Class 0 weight is $w_2 + w_1 \approx 2.222$; class 1 weight is $w_3 \approx 2$. Weighted voting still predicts class 0, but the margin is now narrow. Uniform voting predicted class 0 by a 2-to-1 vote; weighted voting predicts it by 2.22 versus 2.00. This illustrates how sensitive predictions near the decision boundary can be: the same neighbor set can carry very different levels of confidence depending on how much each neighbor is allowed to count.

Step 5 (regression analogue). If the same five training points had numeric labels $y = (0, 0, 1, 1, 1)$ as targets for a regression task, uniform kNN with $k=3$ would produce the local average

$$\hat{y}_q = \frac{1}{3}(y_2 + y_3 + y_1) = \frac{1}{3}(0 + 1 + 0) \approx 0.333.$$

This is the same set of neighbors, but now the answer is a continuous value rather than a class, and each observed label is contributing equally to the prediction. The result sits between the class-0 and class-1 values, which is what a local average should do. The uniform average is, in effect, the least-squares minimizer over the local neighborhood, the same justification used in the OLS chapter, restricted here to three nearby examples.