k-nearest neighbours (kNN)

k-nearest neighbours has no training at all: the model is the training data. To classify a new point:

1. Compute the distance to every training point.
2. Take the k closest.
3. Let them vote (classification) or take the mean (regression).

A small k (1–3): follows the data closely, sensitive to noise and outliers. A large k (50+): a smoother boundary, but the detail is blurred away. At k = the number of points the model always answers the majority class.

Scaling is compulsory. If one feature is in kronor (0–50 000) and another in years (0–50), the kronor dominate the distance entirely.

import numpy as np
from collections import Counter

def knn_predict(X_tr, y_tr, x, k=3):
    d = np.linalg.norm(X_tr - x, axis=1)        # the distance to all of them
    nearest = np.argsort(d)[:k]
    return Counter(y_tr[nearest]).most_common(1)[0][0]

X = np.array([[1, 1], [1.5, 2], [2, 1], [8, 8], [9, 9], [8.5, 9]])
y = np.array([0, 0, 0, 1, 1, 1])
print(knn_predict(X, y, np.array([2, 2]), k=3))   # 0
print(knn_predict(X, y, np.array([7, 8]), k=3))   # 1

The cost: every prediction requires distances to all n training points — O(n·d). With a million points in 768 dimensions that becomes too slow, and then approximate indices (HNSW) are used instead. That is exactly what a vector database does: kNN at scale.

The curse of dimensionality: in high dimensions all the points end up roughly equally far from each other, and «nearest» stops meaning anything. That is why the dimensions are often reduced first.