knn

K-nearest neighbors predicts a new point's label by finding the K most similar examples already seen and letting them vote — if the five closest houses to yours sold for prices clustering around 425,000 dollars, KNN predicts your house is worth about the same, with no model ever fit to the data beforehand. Thomas Cover and Peter Hart formalized the method in their 1967 paper "Nearest Neighbor Pattern Classification," and it remains the clearest example of what's called lazy learning: training does nothing but store the data, and every bit of actual computation — measuring distance to every other point — happens at prediction time instead, the opposite of how a neural network or decision tree front-loads its work into training and predicts cheaply afterward.

Choosing K is a direct bias-variance trade, and the two extremes fail in opposite ways. K equal to 1 lets a single nearest point decide the prediction entirely, which is extremely sensitive to noise — one mislabeled or unusual training example can flip the prediction for every new point near it; K set as large as the entire training set just predicts the overall majority class every time, ignoring any local structure in the data at all. The practical sweet spot for many problems sits around K equal to 3 through 7, found the same way any other hyperparameter is — by checking performance against a validation set, not by guessing.

Feature scaling isn't optional for KNN, it's load-bearing, because the whole algorithm is built on distance. A dataset with age ranging 0 to 100 and salary ranging 0 to 100,000 will have its nearest-neighbor distances almost entirely determined by salary, for no reason other than its raw numbers being thousands of times larger — this is the exact same distortion covered under normalization, except here it doesn't just bias a side calculation, it silently decides which neighbors count as "near" and which don't, corrupting every single prediction.

The curse of dimensionality is the specific reason KNN, which works well in low dimensions, quietly stops working as feature count grows. Beyer and colleagues' 1999 paper "When Is Nearest Neighbor Meaningful?" showed that as dimensionality increases, the distance to the nearest point and the distance to the farthest point converge toward each other — in high enough dimensions, every point ends up roughly equidistant from a given query, which destroys the entire premise that "nearest" means anything useful. This is why KNN is routinely paired with dimensionality reduction (PCA, or the UMAP-style projections covered under dimensionality-reduction) before being applied to high-dimensional data like raw embeddings, rather than run directly on hundreds of unreduced features.

Brute-force KNN's biggest practical flaw — scanning every stored point for every single prediction — is exactly what approximate nearest neighbor search exists to fix. Facebook AI's FAISS library (2017) and the HNSW algorithm described by Malkov and Yashunin (2016) both trade a small amount of accuracy for a massive speedup, organizing stored vectors so that a query only needs to check a small, promising subset of points instead of all of them; this is the same underlying nearest-neighbor idea, scaled to the billion-vector collections that power modern recommendation systems and the retrieval step in semantic search, rather than the thousands-of-rows datasets where exact KNN is still perfectly practical.

KNN earns its place as the field's standard teaching algorithm precisely because it has no hidden machinery: there is no loss function being minimized, no gradient being followed, just a direct claim that similar things tend to have similar labels — and every one of its weaknesses, from scaling sensitivity to the curse of dimensionality to slow inference, is a direct, traceable consequence of taking that one claim completely literally.