k-nearest neighbours, and why distance stops meaning anything

The model with no training

Store the data. To predict, find the k closest training rows and take their average or their majority vote.

from sklearn.neighbors import KNeighborsClassifier
KNeighborsClassifier(n_neighbors=15, weights="distance")

There is no fitting step: fit just stores the array. All the work happens at prediction time, which inverts the usual cost profile: instant training, slow predictions, and the entire training set has to live in memory forever.

k-NN is worth understanding for three reasons beyond its own use. It is the clearest possible illustration of the curse of dimensionality; it is the mechanism underneath every embedding search in module 7; and it makes the assumption behind most machine learning explicit: that things close together in feature space have similar targets. Every model assumes some version of that. k-NN says it out loud.

Choosing k

k = 1 memorises: training error is zero and the decision boundary is a jagged shape drawn around individual points. High variance.

Large k smooths: at k = n every prediction is the global average. High bias.

Something between 5 and 50 is usually right, chosen by cross-validation. weights="distance" makes nearer neighbours count more, which usually helps and lets you use a larger k without over-smoothing.

Scaling is not optional here

With age in years and income in rupees, the distance between two people is essentially the difference in their incomes. Age contributes nothing measurable. Standardise, always, before any distance-based method: this is the model where forgetting it produces the most obviously wrong answer.

Categorical features are a genuine problem. What is the distance between Mumbai and Chennai? One-hot encoding makes every pair of distinct cities exactly the same distance apart, which at least is not misleading, but it also inflates dimensionality, which brings us to the real issue.

The curse of dimensionality, with numbers

In high dimensions, everything is far away and, worse, everything is roughly equally far away.

Generate 1,000 random points uniformly in a unit cube and look at the distance from one point to its nearest and farthest neighbours:

• 2 dimensions: nearest about 0.02, farthest about 1.2. The ratio is around 60. “Near” and “far” are clearly different.
• 10 dimensions: nearest about 0.5, farthest about 2.0. Ratio 4.
• 100 dimensions: nearest about 3.5, farthest about 5.5. Ratio 1.6.
• 1,000 dimensions: nearest about 12.4, farthest about 14.8. Ratio 1.2.

By 1,000 dimensions, your nearest neighbour is barely nearer than your farthest. The word “neighbour” has stopped picking anything out, and a method built entirely on that word has nothing to work with.

The geometric reason: in d dimensions, distance is a sum of d squared differences. As d grows, that sum concentrates around its expectation (the law of large numbers applied to coordinates) and the spread between the smallest and largest sums shrinks relative to their size.

What this means beyond k-NN

This is not a k-NN problem; it is a geometry problem, and it affects every method that relies on distance or density: k-means, DBSCAN, RBF-kernel SVMs, Gaussian mixtures, and any anomaly detector built on distance.

Two qualifications keep it from being paralysing.

Real data usually has lower intrinsic dimension than its column count. Photographs of faces occupy a tiny, curved region of pixel space; the features are heavily correlated, so the effective dimensionality is far below the nominal one. This is why nearest-neighbour search over 768-dimensional embeddings works well in practice, and it is the reason the manifold idea in module 7 matters.

Learned representations are built to make distance meaningful. An embedding is trained so that similar things land close together. That is precisely what raw high-dimensional coordinates fail to give you, and it is why the pairing of embeddings with nearest-neighbour search is so effective.

When k-NN is the right answer

Small datasets. Low dimensions. Genuinely irregular decision boundaries that a parametric model would smooth over. Recommendation by similarity. As a baseline, because it takes one line and sometimes surprises you.

And when the dataset is large, exact search becomes too slow, at which point you want approximate nearest neighbour indexes (FAISS, HNSW, Annoy, all free) which trade a small amount of recall for enormous speed. Module 7 covers them, because that is where they earn their keep.