k-Nearest Neighbours

Learning by looking at neighbours

A doctor sees a new rash and remembers the most similar cases she has treated. A streaming service recommends films that people with similar tastes enjoyed. Judging a new case by its most similar known cases is perhaps the oldest form of reasoning there is, and k-nearest neighbours turns it into an algorithm.

What is it?

k-nearest neighbours (k-NN) classifies a new example by finding the k labelled examples closest to it and taking a majority vote of their labels. For a numeric target it averages them instead. Evelyn Fix and Joseph Hodges described the rule in a 1951 technical report for the US Air Force, and it is still a standard baseline today.

How does it work?

There is no training step in the usual sense. The “model” is the stored dataset, which is why k-NN is called a lazy or instance-based learner. All the work happens at prediction time:

1. Measure the distance from the query to every stored example.
2. Keep the k closest.
3. Return the most common label among them (or their average value).

Three choices decide how well it works, and each has a section below: the distance, the value of k, and the features, including how they are scaled and how many there are.

Why does it matter?

k-NN makes almost no assumptions about the shape of the boundary between classes, so it can follow curves that a linear model such as logistic regression cannot. Its modern form is everywhere: retrieval for language models, image search, recommendation and duplicate detection all find nearest neighbours among learned embedding vectors. And because it is so simple, it shows clearly the problems every learning method faces: choosing complexity, scaling features and coping with many dimensions.

Key takeaways

• k-NN predicts from the k most similar stored examples: a majority vote for classes, an average for numbers.
• It has no training step; the dataset is the model and the work happens at prediction time.
• Its success depends on three choices: the distance, the value of k and the features.

What “near” means: distance

Before you can find the nearest neighbours, you have to decide how to measure nearness. Different rulers give different neighbours.

What is it?

A distance (or metric) turns two feature vectors into one non-negative number, zero when they are identical. The two most common for numeric features are Euclidean distance, the straight-line length, and Manhattan distance, the sum of the differences along each axis, like walking a city grid.

For two points a and b with features a₁ … a_d and b₁ … b_d.

How does it work?

The set of points within a fixed Euclidean distance of the query is a circle (a sphere in 3D); within a fixed Manhattan distance, it is a diamond. So the two rulers rank candidates differently: a point that is far along one axis is penalised more by Euclidean distance, because the difference is squared. For text and embeddings, cosine similarity, which compares directions and ignores length, is often used instead.

Why does it matter?

The distance encodes what you believe “similar” means, and k-NN can only be as good as that belief. In the demo in the next section you can switch between the two rulers and watch the neighbourhood change shape from circle to diamond, and occasionally change the prediction.

Key takeaways

• Euclidean distance is straight-line length; Manhattan distance adds up the differences along each axis.
• Their neighbourhoods are circles and diamonds, so they can pick different neighbours.
• Choosing the distance is choosing what “similar” means; for embeddings, cosine similarity is common.

Choosing k and the decision regions

k is the one dial k-NN has. Turn it down and the model listens to every individual example; turn it up and it listens only to the crowd.

What is it?

k is the number of neighbours that vote. It is a hyperparameter: you choose it, the data does not. The decision regions are the areas of feature space that would be given each label; their borders are where the vote changes.

How does it work?

With k = 1 every training point owns the patch of space closer to it than to any other point, so the regions follow each example exactly, including mislabelled ones. As k grows each vote averages more points, and the regions become smoother. Push k all the way to the size of the dataset and every query gets the overall majority class. In the language of the bias-variance trade-off, small k means low bias and high variance; large k the reverse (Hastie and colleagues, chapter 2).

To choose k fairly you cannot use training accuracy, because at k = 1 every training point is its own nearest neighbour and scores perfectly. Use a validation set or leave-one-out accuracy: classify each point by all the others.

At k = 1 the two stray points carve out their own islands. By k = 7 those islands have gone and the borders follow the clusters. Look at the leave-one-out accuracy as you go: it is highest at small k here, then dips, because this data is cleanly clustered apart from the two strays. On noisier data the best k is usually larger. Ties happen more often than you might expect with three classes; this demo breaks them in favour of the class of the closest tied neighbour.

Why does it matter?

Choosing k is a small, visible version of the most important decision in machine learning: how flexible should the model be? Cover and Hart showed in 1967 that even the most flexible choice, k = 1, has at most twice the best achievable error rate as the data grows without limit. With finite, noisy data, a moderate k chosen by validation usually does better.

Key takeaways

• Small k follows every point, including noise; large k smooths the regions and eventually predicts the majority everywhere.
• Choose k by validation or leave-one-out accuracy, never by training accuracy.
• Use an odd k for two classes, and have a tie-break rule for more.

Scaling features

Measure income in pounds and age in years, and a £1,000 difference counts as much as a thousand years of age. k-NN will quietly ignore age.

What is it?

Feature scaling puts every feature on a comparable range before distances are computed. The most common version, standardisation, subtracts each feature’s mean and divides by its standard deviation, so every feature has mean 0 and standard deviation 1. Min-max scaling, which maps each feature to the range 0 to 1, is the other common choice.

Standardising feature x. μ and σ are its mean and standard deviation, computed on the training data only.

How does it work?

Distance adds up the differences across features, so whichever feature has the biggest numbers dominates. After standardisation a difference of one standard deviation counts the same in every feature. Compute μ and σ on the training data and apply the same numbers to new queries; computing them on the whole dataset leaks information from the test set.

In raw units the neighbours form a narrow vertical band of similar incomes, and leave-one-out accuracy is 48%, no better than a coin. After standardising, the same algorithm with the same k reaches 97%. Nothing about the model changed except the ruler. Decision trees do not care about scale at all, because each split looks at one feature; distance-based methods such as k-NN and k-means care a great deal.

Why does it matter?

Forgetting to scale is one of the most common reasons a k-NN, k-means or support-vector model underperforms. Scaling is also a modelling choice: if you believe one feature matters more, you can deliberately weight it, which is the same as stretching that axis.

Key takeaways

• Distances are dominated by whichever feature has the largest numbers.
• Standardise features (subtract the mean, divide by the standard deviation) using training-set statistics.
• In the demo, scaling alone lifts 5-NN from 48% to 97% leave-one-out accuracy.

The curse of dimensionality

In two dimensions, your nearest neighbour is usually much closer than a random point. In five hundred dimensions it is barely closer at all.

What is it?

The curse of dimensionality, a phrase coined by Richard Bellman, covers the ways that space behaves counter-intuitively as the number of features grows. For nearest neighbours the key effect is distance concentration: the nearest and farthest points end up at almost the same distance, so “nearest” stops carrying much information.

How does it work?

Neighbourhoods have to get huge

Suppose points are spread evenly in a unit cube and you want a small cube around the query that holds 10% of them. In one dimension its edge is 0.1. In d dimensions the edge must be 0.1^(1/d): 0.32 in two dimensions, 0.79 in ten, 0.98 in a hundred. Your “local” neighbourhood spans almost the whole range of every feature.

Distances concentrate

The squared distance is a sum of d independent terms, and sums of many independent terms cluster tightly around their average. Beyer and colleagues proved that under broad conditions the ratio of nearest to farthest distance tends to 1 as dimension grows.

In two dimensions the nearest of the 500 points is about 1% as far away as the farthest. In 100 dimensions it is about 73% as far; in 500, 86%. Real data is rarely uniform, which is why k-NN still works on many datasets with dozens of features: the points lie near a much lower-dimensional surface. But with thousands of raw features, such as pixels, it struggles.

Why does it matter?

The curse explains why k-NN on raw high-dimensional data disappoints, and why representation learning matters so much. It also reaches beyond k-NN: any method that relies on local neighbourhoods, from kernel density estimates to clustering, needs exponentially more data to fill a space as the dimension grows.

Key takeaways

• In high dimensions, nearest and farthest points become almost equally far away, so “nearest” means less.
• A neighbourhood holding 10% of uniform data needs an edge of 0.1^(1/d), close to the full range once d is large.
• Reduce dimensions or learn embeddings so that distance reflects real similarity.

k-NN in practice

Simple to state, k-NN still needs care to be fast and accurate at scale.

What are the main variations?

How fast is it?

Training is free, but a naive prediction compares the query with all n stored examples, d features each: n × d work per query, every time. Bentley’s k-d tree (1975) avoids most of those comparisons in low dimensions. For embeddings with hundreds of dimensions, approximate indexes such as HNSW are the standard tool. Memory is the other cost: the whole training set has to be kept.

Why does it matter?

k-NN is a strong first baseline when you have a good distance and a moderate number of well-scaled features, and it updates instantly: add a labelled example and the model has learned it. Its limits, slow predictions, sensitivity to scaling and the curse of dimensionality, are exactly what learned embeddings and approximate search address, which is why nearest-neighbour search sits at the heart of retrieval-augmented language models.

Key takeaways

• Distance-weighted votes and k-NN regression are simple, useful variations.
• Prediction costs n × d per query; k-d trees help in low dimensions and approximate indexes such as HNSW at scale.
• With good features, k-NN is a strong baseline; with learned embeddings, it powers modern retrieval.

Check your understanding

Six situations from real projects. Each one asks you to apply an idea, not just recall it.

A k-NN model for two classes uses k = 4. For some queries, two neighbours vote yes and two vote no. What is the simplest way to avoid these ties?

Next, compare a model that learns a boundary instead of storing examples in Logistic Regression, or see nearest-neighbour search in learned spaces in Embeddings and RAG.

References

Papers and textbooks behind the claims and methods in this lesson.

References

1. [1]

   Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties(opens in a new tab)

   Evelyn Fix & Joseph L. Hodges Jr., 1951

   USAF School of Aviation Medicine technical report, reprinted in International Statistical Review 57(3), 1989. The original nearest-neighbour rule.

2. [2]

   The Elements of Statistical Learning (2nd edition), chapters 2 and 13(opens in a new tab)

   Trevor Hastie, Robert Tibshirani & Jerome Friedman, 2009

   Springer. Nearest-neighbour methods, the bias-variance view of k, and the curse of dimensionality. Free PDF from the authors.

3. [3]

   Nearest Neighbor Pattern Classification(opens in a new tab)

   Thomas Cover & Peter Hart, 1967

   IEEE Transactions on Information Theory 13(1). With unlimited data, 1-nearest-neighbour error is at most twice the best possible error.

4. [4]

   Dynamic Programming(opens in a new tab)

   Richard Bellman, 1957

   Princeton University Press. Where the phrase “curse of dimensionality” comes from.

5. [5]

   When Is “Nearest Neighbor” Meaningful?(opens in a new tab)

   Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan & Uri Shaft, 1999

   ICDT 1999. Shows that for many data distributions the nearest and farthest points become almost equally far away as dimension grows.

6. [6]

   Multidimensional Binary Search Trees Used for Associative Searching(opens in a new tab)

   Jon Louis Bentley, 1975

   Communications of the ACM 18(9). Introduced the k-d tree for fast nearest-neighbour search in low dimensions.

7. [7]

   Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs(opens in a new tab)

   Yu A. Malkov & Dmitry A. Yashunin, 2018

   IEEE TPAMI. The HNSW graph index behind many vector databases.