k-Nearest Neighbours: Learning by Similarity

Suppose you move to a new neighbourhood and want to guess whether a house is expensive. You look at the houses nearby. That is k-nearest neighbours (k-NN) — perhaps the most intuitive learning algorithm ever devised. It has no training phase at all: it simply remembers the data and makes predictions by consulting similar examples. Despite its simplicity it teaches deep lessons about distance, scale and dimensionality, and it is the ancestor of modern vector-search systems.

The algorithm#

To predict for a query $\mathbf{x}$:

1. Compute the distance from $\mathbf{x}$ to every training point.
2. Select the $k$ closest points $\mathcal{N}_k(\mathbf{x})$.
3. Classification: majority vote among their labels. Regression: average their targets.

Weighted k-NN gives closer neighbours more influence, e.g. weights $w_i = 1/d(\mathbf{x}, \mathbf{x}_i)$.

k-NN is non-parametric (the model grows with the data) and instance-based or lazy (all computation happens at prediction time).

The role of k#

• $k = 1$: the decision boundary follows every training point, forming a Voronoi tessellation. Training error is zero; variance is very high; noisy labels create islands of misclassification.
• Large $k$: smoother boundaries, lower variance, higher bias. With $k = n$ every prediction is the majority class.

Choose $k$ by cross-validation; odd values avoid ties in binary classification. A common starting point is $k \approx \sqrt{n}$, but always validate.

A surprising guarantee#

Cover and Hart (1967) proved that as the number of training examples grows to infinity, the error rate of the 1-NN classifier is at most twice the Bayes error (the best possible error). With $k \to \infty$ and $k/n \to 0$, k-NN is consistent: its error converges to the Bayes error. So this trivially simple method is, asymptotically, nearly optimal — given enough data. The catch is the phrase "enough data", which in high dimensions can mean astronomically much.

Distance and scaling#

k-NN is only as good as its notion of similarity.

• Euclidean distance is the default for continuous features.
• Manhattan distance is more robust to single large coordinate differences.
• Cosine distance suits text and embeddings.
• Hamming or Gower distances handle categorical or mixed data.

Irrelevant features also hurt: each adds noise to every distance. Feature selection or learned embeddings help. Metric learning methods (such as Large Margin Nearest Neighbours or Siamese networks) learn a distance in which same-class points are close.

Implementation from scratch#

import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=5):
        self.k = k
    def fit(self, X, y):
        self.X, self.y = np.asarray(X, float), np.asarray(y)
        return self
    def predict(self, Xq):
        Xq = np.asarray(Xq, float)
        # squared Euclidean distances via broadcasting: (q, n)
        d2 = ((Xq[:, None, :] - self.X[None, :, :]) ** 2).sum(-1)
        idx = np.argpartition(d2, self.k, axis=1)[:, :self.k]
        return np.array([Counter(self.y[row]).most_common(1)[0][0] for row in idx])

from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

X, y = load_wine(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
for scaled in [False, True]:
    A, B = (X_tr, X_te)
    if scaled:
        sc = StandardScaler().fit(X_tr); A, B = sc.transform(X_tr), sc.transform(X_te)
    acc = (KNN(5).fit(A, y_tr).predict(B) == y_te).mean()
    print(f"scaled={scaled}: accuracy={acc:.3f}")

On the wine dataset, scaling typically raises accuracy from around 70% to over 95% — a dramatic demonstration of why scaling matters.

Computational cost and fast search#

Naive prediction costs $O(nd)$ per query — fine for thousands of points, slow for millions. Solutions:

• KD-trees and ball trees partition space for exact search; efficient in low dimensions (roughly $d < 20$) but degrade in high dimensions.
• Approximate Nearest Neighbour (ANN) methods trade a little accuracy for massive speed: locality-sensitive hashing, product quantisation, and graph-based indexes such as HNSW. Libraries like FAISS and vector databases implement them.

Strengths and weaknesses#

Strengths: no training; naturally multiclass; adapts to complex boundaries; easy to update (just add points); predictions are explainable by showing the neighbours.

Weaknesses: slow and memory-hungry at prediction time; sensitive to scaling and irrelevant features; suffers badly from the curse of dimensionality; needs a meaningful distance.