Textbook
The $k$-nearest neighbours method stores labelled training examples. For a new $x$, it computes their distances, selects the $k$ nearest, and predicts the majority class. It requires $1\le k\le n$, where $n$ is the training sample size.
The distance, feature representation, and tie-breaking rules must be fixed beforehand. In binary classification, odd $k$ prevents a voting tie, but equal distances at the neighbour cutoff still require a convention. The example uses distance $|x-z|$ on the real line.
With $k=1$, one nearest example determines the answer. Small $k$ makes predictions sensitive to individual observations; larger $k$ uses a broader neighbourhood and can smooth away useful local differences. The method does not explicitly construct a decision boundary before a query: the answer follows from distances to stored examples.
On training objects, $k=1$ has zero error if every object selects itself as its nearest neighbour. Identical features with conflicting labels can violate that condition. Even zero training error promises nothing about a new object.
Related concepts: Supervised classification, Hyperparameter selection.
With equal voting weights, each selected neighbor contributes one vote regardless of its exact distance from the query. The closest object need not belong to the winning class when $k>1$. Feature scale affects distances: changing one coordinate’s units can change the neighbor set without changing any labels. A prediction rule therefore includes both $k$ and the representation used before computing distances.
In plain language
Nearest neighbors resemble passersby voting on a direction. One confident expert may point toward a closed bridge, while several votes reduce dependence on that person. Polling the whole city can instead erase local detail. Under ordinary voting, people a hundred and two hundred meters away each receive one vote if both belong to the selected group. Distance, feature scales, and group size must therefore be specified beforehand; mixing city blocks with centimeters turns precise counting into an unexpected journey.
Example
The toy training points lie at 0 with label 0, and at 2 and 3 with label 1. The query is $x=0.8$. All distances differ; the example compares $k=1$ with $k=3$.
The k-nearest neighbours method
Neighbor distances
Distances to coordinates 0, 2, and 3 are 0.8, 1.2, and 2.2, respectively.
Step 1 of 3: Neighbor distances
Read all steps
Neighbor distances
Distances to coordinates 0, 2, and 3 are 0.8, 1.2, and 2.2, respectively.
- Coordinates
- 023
- Distances
- 0.8current1.22.2
One neighbour
The point at 0 is closest. Its label 0 becomes the prediction.
- Neighbours
- 0 → class 0included2 → class 13 → class 1
- Prediction
- 0included
Three neighbours
Two neighbours vote for 1 and one for 0. Changing k changes the answer for the same input.
- Votes
- 0excluded1included1included
- Prediction
- 1included
The neighbor order is unambiguous: point 0 first, then 2, then 3. At $k=3$, the closest class-0 object loses to two more distant class-1 objects because votes determine the result. Changing the prediction from 0 to 1 does not establish improvement: the query’s true label is unspecified. This demonstration checks how two settings operate rather than selecting a winner by accuracy.
Source of the original notes: lecture notes.