📊 k-Nearest Neighbours

KNN computes the distance from the new point to every training point, identifies the k closest ones, and takes a majority vote of their labels to assign the class. For regression, it averages the k neighbours' target values. The choice of k controls the trade-off between underfitting (large k, very smooth boundary) and overfitting (small k, noisy boundary).

Choose k by cross-validation: train on a subset of data, test on a held-out validation set, and evaluate accuracy for different values of k. Typically k is odd to avoid ties, and k=√n (where n is training set size) is a common rule of thumb. The optimal k balances bias (too large k oversmoothes) and variance (too small k is noisy).

Euclidean distance (straight-line distance) is the default. Manhattan distance (sum of absolute differences) is useful when features have different units or when the data has a grid-like structure. Minkowski distance generalises both. For text or categorical data, Hamming distance or cosine similarity may be more appropriate. Feature scaling (normalisation or standardisation) is essential before computing distances.

In high-dimensional spaces, all data points become approximately equidistant from each other, making the concept of nearest neighbours meaningless. As dimensions increase, the volume of space grows exponentially while the data stays the same size, so neighbourhoods must expand enormously to include any points. KNN degrades rapidly in performance beyond roughly 10–20 dimensions without dimensionality reduction.

KNN is a supervised classification or regression algorithm: it uses labelled training data to predict labels for new points. K-means is an unsupervised clustering algorithm: it finds natural groupings in unlabelled data. Despite sharing the letter k (and both involving distances and neighbours), they solve entirely different problems with different assumptions and methods.