Understanding K-Nearest Neighbours Classification in Machine Learning

Introduction to KNN

In the field of machine learning, classification is a fundamental task where we aim to assign a discrete label to an input based on its features. One of the most intuitive and powerful algorithms for this purpose is the K-Nearest Neighbours (KNN) classifier. Unlike parametric models that learn a fixed set of weights, KNN is a non-parametric, lazy learning algorithm that makes predictions based on the local structure of the data.

For university students, understanding KNN is essential not only for its practical utility but also because it serves as a perfect introduction to the concepts of distance metrics, decision boundaries, and the bias-variance trade-off. By the end of this article, you will be able to perform manual KNN calculations and understand how to select optimal parameters for your models.

The Core Mechanism of KNN

The intuition behind KNN is simple: similar inputs have similar outputs. When we want to classify a new, unseen data point, we look at the $k$ training examples that are closest to it in the feature space. The algorithm then assigns the new point to the class that appears most frequently among those $k$ neighbours.

Because the algorithm does not build a model during training—it simply stores the training data—it is called a 'lazy learner'. The classification process happens entirely at run-time. The formal rule for classification is:

$$h(x) = \text{mode}({y_i : x_i \in S_x})$$

where $S_x$ is the set of the $k$ nearest neighbours to the test point $x$, and $y_i$ are their corresponding labels.

Measuring Distance

To find the 'nearest' neighbours, we must define a distance metric. The most common choice is the Euclidean distance. For two points in a 2D space, $P = (x_1, y_1)$ and $Q = (x_2, y_2)$, the distance $d$ is calculated as:

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

In higher dimensions, this generalises to the Minkowski distance, where the Euclidean distance is a special case ($p=2$). Another popular alternative is the Manhattan distance ($p=1$), which sums the absolute differences of coordinates. Choosing the right metric is crucial, as it dictates how the algorithm perceives 'similarity' between data points.

Worked Example 1: Binary Classification

Imagine we have a dataset with two features (Height in cm, Weight in kg) and two classes: 'Athlete' and 'Sedentary'. We want to classify a new person with features $(180, 80)$.

Training data:

• A: (170, 70) - Athlete
• B: (190, 90) - Athlete
• C: (160, 60) - Sedentary
• D: (165, 65) - Sedentary

Let $k=3$. We calculate the Euclidean distance from our test point $(180, 80)$ to each:

1. $d(A) = \sqrt{(180-170)^2 + (80-70)^2} = \sqrt{100+100} \approx 14.14$
2. $d(B) = \sqrt{(180-190)^2 + (80-90)^2} = \sqrt{100+100} \approx 14.14$
3. $d(C) = \sqrt{(180-160)^2 + (80-60)^2} = \sqrt{400+400} \approx 28.28$
4. $d(D) = \sqrt{(180-165)^2 + (80-65)^2} = \sqrt{225+225} \approx 21.21$

The 3 nearest neighbours are A, B, and D. Since A and B are 'Athlete' and D is 'Sedentary', the majority vote is 'Athlete'.

The Impact of K

The choice of $k$ significantly affects the decision boundary. A small $k$ (e.g., $k=1$) makes the model sensitive to noise, leading to a complex, jagged decision boundary (high variance). A large $k$ smooths the boundary but may ignore local patterns, potentially leading to underfitting (high bias). In practice, $k$ is often chosen as an odd number to avoid ties in binary classification.

Worked Example 2: Handling Ties

Suppose we have a test point and find 4 neighbours: 2 are 'Red' and 2 are 'Blue'. If we use $k=4$, we have a tie. To resolve this, we can either:

1. Use a weighted vote, where closer neighbours have more influence.
2. Reduce $k$ to 3 (ignoring the furthest neighbour).
3. Choose the class with the smallest average distance to the test point.

If the distances are $d_{Red} = {2.1, 2.5}$ and $d_{Blue} = {2.2, 2.4}$, the average distance for Red is $2.3$ and for Blue is $2.3$. If we use the 'closest neighbour' tie-breaker, we look at the single nearest point. If the nearest point is Red, we classify as Red.

Common Mistakes

• Feature Scaling: Failing to normalise features is a common error. If one feature has a range of 0-1000 and another 0-1, the larger feature will dominate the distance calculation.
• Computational Complexity: Forgetting that KNN is slow at prediction time because it must calculate distances to all training points.
• Choosing Even K: Using an even $k$ in binary classification without a tie-breaking strategy often leads to ambiguous results.
• Ignoring Outliers: KNN is highly susceptible to outliers, which can skew the local neighbourhood and lead to incorrect classifications.

FAQ

Is KNN suitable for large datasets? No, because the prediction time scales linearly with the number of training samples, making it computationally expensive for large datasets.

How do I choose the best k? Use cross-validation to test different values of $k$ and select the one that provides the best accuracy on your validation set.

Does KNN work with categorical data? Standard KNN uses distance metrics designed for numerical data. For categorical data, you would need to use metrics like Hamming distance or encode the categories numerically.

What is the 'Curse of Dimensionality'? As the number of features increases, the volume of the space grows exponentially, making data points sparse and distance metrics less meaningful.

Conclusion

K-Nearest Neighbours is a cornerstone of machine learning, offering a transparent and effective way to approach classification. By mastering distance metrics and the selection of $k$, you are well-equipped to handle various classification tasks. To see these concepts in action with interactive visualisations, generate a free animated lesson on this topic at MathInstructor AI.