I5 · Machine Learning Foundations

k-Nearest Neighbours

k-nearest neighbours (k-NN) is a supervised learning method that predicts for a new example by finding the k training examples closest to it, using a distance such as Euclidean distance, and taking a majority vote of their labels for classification or the average of their values for regression. It does no real training: it stores the data and does the work at prediction time.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

You move to a new city and want to guess whether you will like a restaurant. You ask the three friends whose tastes are closest to yours. That is the whole idea of k-nearest neighbours.

k-nearest neighbours (k-NN) is a supervised learning method that predicts for a new example by finding the k training examples closest to it, using a distance such as Euclidean distance, and taking a majority vote of their labels for classification or the average of their values for regression. It does no real training: it stores the data and does the work at prediction time.

In simple words

Put every known example on a map. When a new point arrives, look at its k closest neighbours and let them vote. If most of the 5 nearest fruits are mangoes, the new fruit is probably a mango.

Overview

  • k-nearest neighbours (k-NN) predicts from the k training examples most similar to a new example.
  • Classification uses a majority vote; regression averages the neighbours' values.
  • It has no training phase beyond storing the data: it is a lazy, instance-based learner.
  • Small k follows noise; large k smooths too much; k is chosen by cross-validation.
  • Features must be scaled, because distances depend on units.
  • Prediction is slow for large data, since every prediction compares with many stored points.

Why it matters

k-NN is the simplest machine-learning method to understand, works surprisingly well for small problems, and teaches ideas that run through all of AI: distance, similarity, the importance of scaling and the trade-off between flexibility and stability.

Key terms

k
The number of neighbours that vote; a hyperparameter.
Distance metric
How closeness is measured, usually Euclidean or Manhattan.
Majority vote
Choosing the most common label among the neighbours.
Lazy learner
A method that does almost nothing at training time and all the work at prediction time.
Distance weighting
Giving closer neighbours a bigger say in the vote.
Curse of dimensionality
In very many dimensions, all points become roughly equally far apart, weakening distance-based methods.

Types

k-NN comes in several variants, differing in how neighbours are weighted, how distance is measured and how they are found.

1. k-NN classification (majority vote)

Assigning the class most common among the k nearest neighbours.

  • How it works: Compute distances to all training points, take the k closest and count their labels; odd k avoids ties in two-class problems.
  • Example: A new fruit near three mangoes and two guavas is classified as a mango with k = 5.
  • When to use it: Use it for small data sets where similar examples should share labels.

2. k-NN regression

Predicting a number as the average of the k nearest neighbours' targets.

  • How it works: The prediction is the mean (or median) of the neighbours' values, giving a step-like, flexible fit.
  • Example: Estimating a flat's rent from the five most similar flats in the same area.
  • When to use it: Use it when similar cases have similar values and a formula is hard to write.

3. Distance-weighted k-NN

Giving closer neighbours more say than farther ones.

  • How it works: weights="distance" weights each neighbour by 1 ÷ distance, so a very close neighbour can outweigh several distant ones.
  • Example: Predicting a house price where one almost identical house next door matters most.
  • When to use it: Use it when neighbours vary widely in distance; it often improves accuracy for free.

4. Choice of distance metric

Using Euclidean, Manhattan, Minkowski, cosine or Hamming distance.

  • How it works: The metric parameter changes what "near" means; cosine suits text vectors and Hamming suits binary features.
  • Example: Finding similar documents with cosine distance on TF-IDF vectors.
  • When to use it: Use the metric that matches the data type, and tune it if unsure.

5. Fast neighbour search (KD-trees, ball trees, approximate search)

Data structures that find nearest neighbours without checking every point.

  • How it works: KD-trees and ball trees split space so searches skip far regions; approximate methods such as HNSW trade a little accuracy for huge speed.
  • Example: Vector databases finding the nearest of millions of embeddings in milliseconds.
  • When to use it: Use them when the data set is large or predictions must be fast.

Explained in detail

Choosing k

With k = 1 the prediction copies the single nearest example, so one mislabelled or unusual point can flip the answer; the decision boundary is jagged and the model overfits. With a very large k, say the whole data set, every prediction becomes the majority class, and the model underfits. Values in between smooth out noise while keeping local detail. For two-class problems, an odd k avoids ties. The usual method is to try several values, such as 1, 3, 5, 7, 11 and 15, and choose the one with the best cross-validation score. A rough rule of thumb is k near the square root of the number of training examples, but validation should decide.

Strengths and weaknesses

StrengthsWeaknesses
No training time; new data can be added instantlySlow predictions on large data, since distances to every point must be computed
Handles any shape of decision boundarySensitive to feature scaling and irrelevant features
Easy to explain: "these are the similar cases"Struggles in high dimensions
Works for classification and regressionMust store the entire training set

History and modern relatives

The nearest-neighbour rule was introduced by Evelyn Fix and Joseph Hodges in a 1951 report and analysed by Thomas Cover and Peter Hart in 1967, who showed that with enough data its error rate is at most twice the best possible. The same idea powers modern systems at enormous scale. Recommendation engines find users or items with similar embedding vectors; semantic search and retrieval-augmented generation find the stored passages nearest to a query's embedding. Because comparing with millions of vectors is slow, these systems use approximate nearest-neighbour indexes, such as those in the FAISS library released by Meta in 2017, that trade a little accuracy for huge speed.

  • Always scale features before k-NN.
  • Remove features that carry no signal; with k-NN they add noise to every distance.
  • Use weights="distance" in scikit-learn to let closer neighbours count more.

k-NN also works for regression: the prediction is the average target of the k neighbours, so a flat's price can be estimated from the prices of the most similar flats sold recently, exactly as many property agents reason informally.

How it works

  1. Scale the features.
  2. For a new example, compute its distance to every training example.
  3. Take the k closest.
  4. Classification: majority vote. Regression: average of their values.
  5. Choose k by cross-validation.

In code

knn.py
from sklearn.datasets import load_iris
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_iris(return_X_y=True)

for k in [1, 3, 5, 11, 25, 75]:
    model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k))
    scores = cross_val_score(model, X, y, cv=5)
    print(f"k={k:>2}: mean accuracy {scores.mean():.3f}")

Output

k= 1: mean accuracy 0.947
k= 3: mean accuracy 0.953
k= 5: mean accuracy 0.960
k=11: mean accuracy 0.947
k=25: mean accuracy 0.940
k=75: mean accuracy 0.840

Try it yourself

Let the neighbours vote

Move the new point and change k. Watch how the vote, and the prediction, change.

What happens with this k?

Sort each effect.

  • One mislabelled point can change a prediction

  • A jagged decision boundary

  • Predictions drift towards the most common class

  • A very smooth boundary that misses local patterns

Common mistakes

  • Forgetting to scale features.
  • Choosing k by looking at test accuracy.
  • Using k-NN with hundreds of noisy features.

Check yourself

Question 1

1. How does k-NN classify a new example?

Question 2

2. What happens when k = 1?

Question 3

3. Why is k-NN called a lazy learner?

Summary

  • k-NN predicts from the k most similar training examples.
  • Small k overfits, large k underfits; choose k by cross-validation.
  • Scale features; the same idea powers modern similarity search.

Finished reading?

Sources: scikit-learn User Guide · An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani)