K-Nearest Neighbors: Local Learning

K-nearest neighbors stores the training examples and predicts from the labels or targets of nearby cases. Training can be almost trivial. Inference performs the expensive search and aggregation.

The model therefore lives in the feature representation and distance metric as much as in the value of k.

The rule also comes with a bound, and the bound is older than most of what it competes with. Cover and Hart proved it in 1967. In the large-sample limit, “for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error”. They draw the consequence themselves: “in this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.” Half, from one stored example. And no further, which is the other half of the sentence.

The same paper names its ancestor. The first formulation of a rule of this type “appears to have been made by Fix and Hodges”. Theirs were two unpublished USAF School of Aviation Medicine reports, from February 1951 and August 1952.

Every new row goes through the same query-time sequence. Encode the query with the fitted preprocessing. Measure distance against the stored training examples. Keep the k closest eligible ones. Aggregate their labels or targets by vote, weight or average. Then return the prediction, together with the supporting cases when those are useful.

Changing any one can alter the prediction even when the stored data is fixed.

A larger k is not automatically a better k, and the 1967 paper says so formally. Cover and Hart show that the single nearest-neighbour rule is admissible within the class of k-NN rules. For the n-sample problem there exists no k-NN rule with k other than 1 “which has lower probability of error against all distributions”. They prove it by exhibiting such a distribution. It has two categories with equal prior probabilities: one uniform on the unit disk centred at (−3, 0), the other uniform on the unit disk centred at (3, 0). On that data, 1-NN is strictly better than every larger neighbourhood. Neighbourhood size is a claim about the data in front of you. It is not a dial with a correct setting.

The metric is the same kind of choice, and the record on it is an argument rather than a default. A 2001 paper on high-dimensional data mining recommended the Manhattan L1 norm over L2 — “consistently more preferable”, its authors wrote — and the recommendation travelled. Two decades later a paper in Entropy put it on trial, under the title Fractional norms and quasinorms do not help to overcome the curse of dimensionality. Its authors ran 37 binary classification problems drawn from 25 UCI databases at k = 3, 5, 7 and 11. They found kNN under l0.5, l1 and l2 statistically indistinguishable. The 2020 abstract states it without hedging: “A systematic comparison shows that the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant.” Two published papers, one recommendation, one refutation. Which metric wins on your data is a measurement you run inside your own folds. It is not a setting you inherit from either of them.

Three dials remain. Neighborhood size: small k follows fine detail and noise, large k smooths across broader regions, and it is tuned only within valid splits, sometimes under class-aware constraints. The distance metric: Euclidean for scaled numeric geometry, Manhattan for coordinate-wise differences, cosine for direction in sparse spaces, domain metrics for structured data. Neighbor weighting: a uniform vote treats selected cases equally, inverse-distance emphasizes close cases, either can amplify duplicate or noisy points, and zero distances need explicit handling.

KNN is compelling when analog cases are meaningful and the search space is controlled. When it breaks, it is rarely subtle.

Zillow Group ran comparable-case valuation as a balance sheet. Zillow Offers bought homes and resold them, pricing them from comparable local properties. On 2 November 2021 the company announced that it would wind the business down. The same Q3 2021 results carried a $304.4 million inventory write-down, guidance of a further $240–265 million of losses on homes already under contract, $175–230 million of impairment, restructuring and other associated costs over the course of the wind-down, and a workforce reduction of approximately 25%.

The failure mode is named in the operator's own words. Rich Barton, Zillow Group co-founder and CEO, said in that day's earnings release: “We’ve determined the unpredictability in forecasting home prices far exceeds what we anticipated and continuing to scale Zillow Offers would result in too much earnings and balance-sheet volatility,”. The comparable homes were real. What was not survivable was the variance of the target inside the neighbourhood.

Ties, class imbalance, duplicate rows and mixed-label neighborhoods all require explicit behavior. Probability-like vote fractions are local frequencies under the chosen representation. They are not guaranteed calibrated probabilities.

Class priors, distance weighting, or separate retrieval constraints can change the answer. These choices should be evaluated. They should not be hidden in defaults.

Do not tune k before validating the geometry. Define which rows are eligible to become neighbors at all. Fit scaling, encoding, imputation or a learned representation inside the folds. Read the actual supporting cases returned for a diverse set of queries. Tune k and weighting on held-out decisions rather than training accuracy. Compare crowded, sparse, boundary and minority regions separately. And measure index memory, latency, update cost and deletion behavior before anything is served.

Exact search can become expensive as rows and dimensions grow. Tree-based spatial indexes help mainly in lower-dimensional settings, while approximate nearest-neighbor indexes trade exactness for speed and memory.

How expensive is not a matter of opinion; it is scored in public. NeurIPS ran a Billion-Scale Approximate Nearest Neighbor Search Challenge in 2021, across three hardware tracks: a limited-DRAM Azure VM with FAISS as the baseline, DRAM-plus-SSD with DiskANN as the baseline, and unrestricted hardware. Entrants were ranked by recall at a query-throughput threshold. The organisers state the scope: “We compiled six diverse billion-scale datasets, four newly released for this competition, that span a variety of modalities, data types, dimensions, deep learning models, distance functions and sources.” Index memory, latency and recall are the competition's scoring rule because they are the deployed model's specification.

Updates, privacy deletion, deduplication and stale examples are production concerns, because the training set remains part of the live predictor. A regulator can be the one to say so. In the FTC's Everalbum matter, the proposed consent order published in the Federal Register on 25 January 2021 reached past the data into what had been built from it: “Part III of the proposed order requires Respondent to delete (A) photos and videos of Ever app Users who requested deactivation of their accounts, (B) face recognition data that it created without obtaining Users' affirmative express consent, and (C) models and algorithms it developed in whole or in part using images from Users' photos.” The Commission finalised the settlement on 7 May 2021 by a 4-0 vote. For a lazy learner, clause (A) and clause (C) name the same deletion. The stored examples are the model.