K-Nearest Neighbours

KNN: K-nearest neighbours

KNN is used for both classification and regression. To make a prediction for a new point, it finds the K training points closest to it and lets them decide: the most common class among them (classification) or the average of their values (regression). It is a lazy learner: it stores the training data instead of building a model in advance, and it measures "closeness" with a distance metric such as the Euclidean distance.

What does the "K" mean?

K is the number of neighbours the algorithm looks at. For example, when classifying a fruit with \(K = 3\): if 2 of its 3 nearest neighbours are apples and 1 is a banana, the fruit is predicted to be an apple — the majority vote.

How KNN works

1. Choose K — the number of neighbours to consider.
2. Compute the distance from the new point to every point in the training data (most often the Euclidean distance).
3. Find the K nearest neighbours — the K training points with the smallest distances.
4. Predict — by majority vote of their classes (classification) or by averaging their values (regression).

Worked example

Five training points — \([1,2], [2,3], [3,4]\) with label A and \([6,7], [7,8]\) with label B — and a new point \([4,5]\) with \(K = 3\):

Distance metrics

• Euclidean distance — the straight-line distance between two points:
  \[ d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2} \]
• Manhattan distance — the distance travelled along the axes, like moving through a grid of city blocks ("taxicab" distance):
  \[ d(x, y) = \sum_{i=1}^{n} |x_i - y_i| \]
• Minkowski distance — a family of distances with a parameter \(p\); \(p = 2\) gives the Euclidean and \(p = 1\) the Manhattan distance:
  \[ d(x, y) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p} \]

Each metric has its own idea of a "circle" — all the points at the same distance from the centre. Move the Minkowski \(p\) and click the plot to move point Y.

Because KNN is built on distances, features measured on large scales (e.g. income in euros) dominate features on small scales (e.g. age in years). Features are therefore usually scaled to similar ranges before using KNN — see feature scaling in Lab 06.

How to choose the value of K

K controls a trade-off:

• A small K follows the training data very closely and is sensitive to noise — a single mislabelled point can change a prediction (overfitting).
• A large K averages over many points and is robust to noise, but if K is too large the local structure is lost (underfitting).

Common ways to pick K:

• Cross-validation — split the data into parts, repeatedly train on some parts and validate on the remaining one, and choose the K with the best average validation performance.
• Elbow method — plot the error rate for different values of K and choose the K where the curve bends and stops improving much (the "elbow").
• Odd values of K — for classification with two classes, an odd K avoids ties in the majority vote.

Try it: KNN classifier

The shading shows what KNN would predict at every location; circles are training points and diamonds are held-out validation points. Change K to see the boundary go from jagged (small K) to overly smooth (large K), and watch the validation error — the elbow chart below plots it for every K. Click anywhere to classify a new point and see its K neighbours.

Implementing KNN from scratch

The worked example above in a few lines of Python:

import numpy as np
from collections import Counter

def euclidean_distance(a, b):
    return np.sqrt(np.sum((np.array(a) - np.array(b)) ** 2))

def knn_predict(training_data, training_labels, test_point, k):
    # 1. distance from the test point to every training point
    distances = [euclidean_distance(test_point, x) for x in training_data]
    # 2. indexes of the k closest points
    nearest = np.argsort(distances)[:k]
    # 3. majority vote among their labels
    labels = [training_labels[i] for i in nearest]
    return Counter(labels).most_common(1)[0][0]

training_data = [[1, 2], [2, 3], [3, 4], [6, 7], [7, 8]]
training_labels = ['A', 'A', 'A', 'B', 'B']

print(knn_predict(training_data, training_labels, [4, 5], k=3))  # A

Advantages

• Simplicity and intuition: KNN is very easy to understand and implement. The core concept — that similar points are close to each other — is highly intuitive.
• No training phase (lazy learner): since it's a lazy learning algorithm, KNN simply stores the entire training dataset. There is no complex training or model-building process upfront, which can make it very fast to "train".
• Adaptable to new data: the model is not fixed after a training period. New data can be added seamlessly without requiring a full retraining process.
• Non-parametric: KNN makes no underlying assumptions about the data's distribution (e.g., that the data is linear or normally distributed). This makes it effective for data where decision boundaries are non-linear or complex.
• Versatility: it can be used effectively for both classification (majority vote) and regression (averaging neighbour values) tasks.

Disadvantages

• Slow predictions on large datasets: the work happens at prediction time — every new point is compared with every stored training point, so predictions get slower as the dataset grows, and the whole dataset must be kept in memory.
• Curse of dimensionality: with many features, points become far apart and distances become less meaningful, so "nearest" neighbours are no longer really similar and accuracy drops.
• Overfitting with a small K: with K = 1 or other very small values, the prediction follows noise and outliers in the training data.
• Sensitive to the scale of the features: without scaling, features with larger ranges dominate the distance.

Applications

• Recommendation systems — suggest items liked by users with similar tastes.
• Spam detection — classify an email by the most similar known emails.
• Customer segmentation — group customers with similar behaviour.
• Speech recognition — match a spoken sample to the most similar known patterns.