How Does K-Nearest Neighbours (K-NN) Classification Work?

K-Nearest Neighbours (K-NN) classifies a new data point by finding the $k$ most similar labelled examples in the training data and assigning the class that occurs most frequently among them.

K-NN is a supervised learning algorithm because it learns from a labelled training dataset. It is also described as an instance-based or “lazy” learning algorithm: it stores the training examples rather than constructing a model during training.

The classification process is:

1. Choose a value for $k$, the number of neighbours considered.
2. Calculate the distance from the unclassified point to each labelled training point.
3. Sort the training points from smallest to largest distance.
4. Select the nearest $k$ points.
5. Count the class labels among those neighbours.
6. Assign the most frequent class to the new point.

For numerical features, Euclidean distance is commonly used. For two points $(x_1,x_2)$ and $(y_1,y_2)$:

$$d=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$$

Suppose the four nearest training examples have the following distances and labels: $1.0$ (A), $1.4$ (B), $2.0$ (A), and $2.5$ (B). If $k=3$, the selected labels are A, B, and A, so the new point is classified as A by majority voting.

Features should usually be normalized so that a feature with large numerical values does not dominate the distance calculation.

Categorical features require an appropriate distance measure or numerical encoding. If majority voting produces a tie, the implementation should apply a stated rule, such as choosing the class of the closest neighbour. Validation data can help select $k$ by comparing classification accuracy.

In an IB Computer Science HL A4.3 response, describe the ordered algorithm and explain how $k$, distance, and majority voting affect classification. A common misconception is that K-NN calculates an average label; classification uses the most frequent class, while averaging is associated with K-NN regression.