K-Nearest Neighbours: Local Prediction, Distance Weighting and Dimensionality

A model stored in the training examples

KNN does little parameter fitting beyond storing the transformed training data and possibly building a search index. At prediction time, it retrieves neighbours and aggregates their outcomes. This shifts much of the computational and statistical work into representation, distance and query-time search.

The assumption is local regularity: similar feature vectors tend to have similar responses. That can be reasonable for meaningful physical measurements and poor for arbitrary category codes. A simple prediction rule can still rest on a complicated feature pipeline.

Classification and regression use different aggregations

Let \(N_k(x)\) be the selected k training neighbours. Unweighted regression predicts

Classification estimates local class frequencies and chooses a class according to those frequencies or an explicit decision cost. A weighted form uses nonnegative weights \(w_i(x)\):

These local frequencies are not automatically well-calibrated probabilities, particularly with small k, imbalanced sampling or shifted deployment data. Check calibration if decisions depend on numeric probabilities.

Work through a prediction

Suppose the three neighbours have targets 10, 20 and 40 at distances 1, 2 and 4. Unweighted regression predicts \(70/3\approx23.33\). Inverse-distance weights are 1, 0.5 and 0.25, giving

The nearest observation now has greater influence. For classification with labels A, B, B at those same distances, unweighted voting chooses B, but inverse-distance voting gives A total weight 1 and B total 0.75, so it chooses A.

Weighting changes the estimator, not just the implementation speed. Zero-distance matches need a deliberate rule: one common choice uses only exact matches rather than dividing by zero. Conflicting labels among duplicate feature vectors expose uncertainty that no distance metric can resolve without extra information.

Neighbourhood size controls smoothing

With k=1, predictions can change abruptly near individual observations. Increasing k reduces local sampling noise but reaches farther into feature space. A broad neighbourhood can cross a genuine decision boundary or average away a rare local response pattern.

As dataset size grows, a fixed k and a growing k describe different asymptotic procedures. Classical consistency results require conditions such as k growing while k/n tends to zero, together with assumptions on the problem. They do not guarantee that a convenient finite-data setting is best.

Choose k and distance weighting through validation. An odd k reduces some binary-vote ties but does not eliminate multiclass ties or distance ties. Store the tie-breaking policy for reproducibility.

Distance is the main modelling decision

Euclidean distance gives scale and rotation their usual geometric meaning. Manhattan distance changes neighbourhood shape. Cosine dissimilarity emphasises direction and ignores overall magnitude after normalisation. Mixed numerical and categorical data may need a more specialised representation or dissimilarity.

Fit scaling only on training data. Adding irrelevant features can make genuinely similar observations far apart, while duplicate or highly correlated features can effectively count one property several times. Feature selection or dimensionality reduction can help, but must be fitted inside the same validation boundary.

A learned embedding may make local prediction effective, yet its training data and objective are then part of the KNN system. Reporting “no training required” would omit the work that created the geometry.

Why high dimensions are difficult

As dimension increases, a local neighbourhood can occupy a large fraction of the feature range before containing enough observations. Distances may become less discriminative, and the sample requirement for local estimation can grow sharply.

For an idealised uniform unit cube, a side-length fraction r occupies volume \(r^d\). Capturing one percent of the volume requires \(r=0.01^{1/d}\): approximately 0.1 in two dimensions and 0.794 in twenty. This simplified geometry illustrates why “local” can become surprisingly broad; it is not a universal quantitative law for structured real datasets.

Search cost and approximation

Brute-force Euclidean prediction costs roughly \(O(nd)\) per query before selecting neighbours. KD-trees and ball trees can help in favourable dimensions and data distributions, while approximate indexes trade exact neighbour recovery for speed and memory choices.

Evaluate approximation through final predictive quality as well as neighbour recall. Missing the nearest observation may be harmless when nearby labels agree and harmful near a rare boundary. Include index construction, stored vectors and query latency in the resource report.

A practical evaluation checklist

Use a constant or class-prior baseline, compare several neighbourhood sizes, inspect exact matches and evaluate rare classes. Exclude the query’s own training row when measuring leave-one-out behaviour; evaluating training points with themselves as neighbours makes k=1 look deceptively perfect.

KNN cannot extrapolate ordinary regression targets beyond the convex range of the neighbours under nonnegative averaging. Its usefulness comes from local examples, so inspect which examples actually drive important predictions. That makes failure analysis concrete rather than attributing every error to an opaque model.

References

1. scikit-learn. Nearest Neighbors.
2. James, Witten, Hastie, Tibshirani and Taylor. An Introduction to Statistical Learning with Applications in Python. Springer, 2023.