Foundations / Instance-Based
verifiedk-Nearest Neighbors
To classify something, find the most similar examples already seen and let them vote. There is no training step at all — the data is the model. It is the baseline every other method ought to have to beat, and on small, low-dimensional problems it is embarrassingly hard to beat.
All the cost moves to prediction time: every query is compared against every stored example. The choice of k trades sensitivity to noise against blurring the boundary, and the distance metric usually matters more than k does. In high dimensions the distances between all pairs concentrate, so "nearest" stops meaning very much — which is the problem every vector index is quietly fighting.
Predict the majority label among the k smallest ‖x − x sub i ‖, at Θ(nd) per query and Θ(1) to train. As d grows, the ratio of the farthest to the nearest distance in a random sample tends toward 1, so a neighbourhood carries less and less information the more features it is measured over.
k holds 1% of the budget; rest holds the remaining 99%.
Stored examples one prediction consults against those it ignores. Drag k to watch the vote widen and the boundary blur.
Reviewed by opendroid · 2026-08-13
- arXiv:1603.09320 — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
Origin · not linkable
- Cover & Hart 1967 — Nearest Neighbor Pattern Classification · IEEE Transactions on Information Theory 13(1) · doi:10.1109/TIT.1967.1053964
- Beyer et al. 1999 — When Is “Nearest Neighbor” Meaningful? · ICDT 1999 · doi:10.1007/3-540-49257-7_15