A1 · Supervised Machine Learning in Depth

k-Nearest Neighbours and Distance Metrics

k-nearest neighbours (k-NN) classifies a point by the majority label of the k training points closest to it, or for regression averages their values. It stores the training data instead of learning parameters. Closeness is measured by a distance metric such as Euclidean, Manhattan or cosine distance, so features must be scaled.

12 min Advanced Jump to the activity

What you need: The earlier topics of this module, and its prerequisites.

Definition

Are you like your neighbours? A classifier that simply asks them.

k-nearest neighbours (k-NN) classifies a point by the majority label of the k training points closest to it, or for regression averages their values. It stores the training data instead of learning parameters. Closeness is measured by a distance metric such as Euclidean, Manhattan or cosine distance, so features must be scaled.

In simple words

To guess whether a new student will pass, look at the three students with the most similar study hours and attendance, and go with the majority. Small k follows every quirk of the data; large k smooths everything out. In very many dimensions, all points end up roughly equally far apart, which weakens k-NN.

Why it matters

k-NN is a strong, assumption-free baseline, the basis of recommendation by similarity, and the core idea behind vector search in retrieval-augmented LLM systems, which find the nearest embeddings to a query.

Key terms

k-nearest neighbours (k-NN)
Predicting from the k training points closest to a new point: majority vote or average.
Euclidean distance
Straight-line distance: √Σ(aᵢ − bᵢ)².
Manhattan distance
Sum of absolute differences, like walking city blocks: Σ|aᵢ − bᵢ|.
Cosine distance
1 minus the cosine of the angle between vectors; common for text and embeddings.
Lazy learner
A method that stores the training data and does its work at prediction time.
Curse of dimensionality
In many dimensions, all points become nearly equally far apart, weakening distance-based methods.

Explained in detail

How k-NN predicts

k-NN makes no assumptions about the shape of the data. To classify a new point, it computes the distance to every training point, picks the k nearest and takes a majority vote; for regression it averages their values. With k = 1 the boundary follows every training point and overfits noise; with very large k it smooths away real structure and underfits. A common starting point is k around the square root of the number of training rows, refined by cross-validation, and an odd k avoids ties in two-class problems. Distance-weighted voting, where closer neighbours count more, often helps.

A worked example

Suppose a fruit seller classifies mangoes as "ripe" or "unripe" from firmness (1 to 10) and sweetness in degrees Brix. A new mango has firmness 4 and Brix 14. Its three nearest neighbours in standardised units are two ripe mangoes at distances 0.5 and 0.7 and one unripe mango at 0.9, so with k = 3 the vote is 2 to 1: ripe. If the features were not scaled and Brix ranged far more widely than firmness, Brix alone would decide the neighbours. Standardising features, or choosing a distance that suits the data, is therefore essential.

DistanceGood for
EuclideanContinuous, scaled features of similar importance
ManhattanHigh-dimensional data; less dominated by one big difference
CosineText vectors and embeddings, where direction matters more than length
HammingBinary or categorical features: count of positions that differ

k-NN is slow at prediction time because it compares each query with all training data; data structures such as k-d trees and ball trees, and approximate nearest-neighbour libraries such as FAISS, make search fast enough for millions of points. In high dimensions distances lose meaning, so k-NN works best after reducing dimensions or on learned embeddings. The same nearest-neighbour idea powers recommendation ("customers like you bought"), semantic search over embeddings, anomaly detection and missing-value imputation.

When to use k-NN: small to medium data sets with a few meaningful, scaled features, problems where similar cases should get similar answers, and situations where you want to show the user the actual similar examples behind a prediction, such as "these five past patients looked most like yours". When to avoid it: very large data sets that need fast predictions, many irrelevant features, and features on scales that cannot be made comparable.

How it works

DistanceFormula ideaGood for
Euclidean (L2)Straight-line distanceContinuous, scaled features
Manhattan (L1)Sum of absolute differencesGrid-like data, robust to outliers
CosineAngle between vectorsText and embeddings

The maths

Euclidean distance
Manhattan and cosine distance

In code

How k and scaling change k-NN accuracy on the wine dataset, plus the three distances computed by hand.

knn.py
import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_wine(return_X_y=True)
print(" k   unscaled   scaled")
for k in [1, 3, 5, 15, 51]:
    raw = cross_val_score(KNeighborsClassifier(k), X, y, cv=5).mean()
    scaled = cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(k)), X, y, cv=5).mean()
    print(f"{k:>2}   {raw:8.3f}   {scaled:6.3f}")

a, c = np.array([1.0, 2.0, 3.0]), np.array([2.0, 0.0, 3.0])
print("Euclidean:", round(float(np.linalg.norm(a - c)), 3))
print("Manhattan:", float(np.abs(a - c).sum()))
print("Cosine distance:", round(float(1 - a @ c / (np.linalg.norm(a) * np.linalg.norm(c))), 3))

Output

 k   unscaled   scaled
 1      0.725    0.950
 3      0.703    0.944
 5      0.691    0.949
15      0.714    0.955
51      0.714    0.961
Euclidean: 2.236
Manhattan: 3.0
Cosine distance: 0.185

Try it yourself

k and the vote

Move k and watch which neighbours vote and how the prediction changes.

Common mistakes

  • Forgetting to scale features, so one large-unit feature dominates the distance.
  • Using an even k for two classes, which allows ties.
  • Applying k-NN to hundreds of raw features, where distances lose meaning.

Check yourself

Question 1

1. What does k-NN learn during training?

Question 2

2. Increasing k usually makes the boundary…

Question 3

3. Which distance suits text embeddings?

Summary

  • k-NN predicts from the k most similar training points.
  • Scale features; choose k and the distance by validation.
  • Its idea powers vector search in modern AI systems.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Nearest neighbours · Hastie et al., The Elements of Statistical Learning