k-Nearest Neighbors

Suppose you move to a new city and need to decide whether a neighborhood is safe. The simplest strategy: find the k nearest residents who look similar to your situation and ask what they think. If most say safe, you go with safe. No statistics textbook required.

k-Nearest Neighbors (k-NN) works exactly that way. Given a set of labeled training points and a new query point, it finds the k closest training examples, counts which class appears most often among them, and assigns that class to the query. No parameters to optimize, no model to fit, no training phase at all — just store the data and measure distances when a query arrives.

Formally proven by Thomas Cover and Peter Hart in 1967, k-NN carries a beautiful theoretical guarantee: as the number of training points grows to infinity, its error rate is never worse than twice the optimal Bayes error rate. That theoretical anchor, combined with near-zero setup cost, made k-NN one of the foundational tools in machine learning — and a benchmark that fancier algorithms still have to beat on small datasets.

The price you pay comes at query time. Every prediction requires scanning (or smartly indexing) the entire training set, making k-NN a deceptively expensive algorithm once data grows large.

Place labeled points on the canvas — click to add a blue point, then switch class and add red points. Drop a query (the star) anywhere and watch the k nearest neighbors vote on its class.

<div class="controls">
  <label>{{add_points_as}}
    <select id="classSelect">
      <option value="0">● {{class_a_label}}</option>
      <option value="1">● {{class_b_label}}</option>
    </select>
  </label>
  <label>k = <span id="kVal">3</span>
    <input type="range" id="kSlider" min="1" max="9" value="3" step="2">
  </label>
  <button id="resetBtn" type="button" class="ghost">{{clear_all}}</button>
</div>
<canvas id="canvas" width="460" height="300"></canvas>
<div class="result" id="result">{{initial_hint}}</div>
<div class="legend">
  <span class="dot blue"></span> {{legend_class_a}} &nbsp;
  <span class="dot red"></span> {{legend_class_b}} &nbsp;
  <span class="star">★</span> {{legend_query}}
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .8rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; font-size: .88rem; }
label { display: flex; gap: .4rem; align-items: center; }
select, input[type=range] { font-size: .88rem; }
#canvas { display: block; width: 100%; border: 1px solid #cdd9e3; border-radius: 8px;
          background: #f6f9fc; cursor: crosshair; touch-action: none; }
.result { font-weight: 600; font-size: .95rem; margin: .5rem 0 .3rem; min-height: 1.4em; }
.result.a { color: #1a73e8; }
.result.b { color: #e8311a; }
.result.tie { color: #7d5a00; }
.legend { font-size: .8rem; color: #555; display: flex; gap: .3rem; align-items: center; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.blue { background: #1a73e8; }
.dot.red  { background: #e8311a; }
.star { color: #d4a017; font-size: 1rem; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Change k with the slider. Notice how k = 1 follows training points exactly (zero training error, but prone to noise), while larger k smooths the boundary and can flip the prediction entirely. The colored lines show the exact distances from the query to each neighbor considered.

k-NN looks simple. Its hidden costs are not.

• Training cost: $O(1)$. There is nothing to train. k-NN simply stores all n labeled examples — memory proportional to the dataset, compute proportional to nothing.
• Query cost (naïve): $O(n \cdot d)$. Every prediction scans all n training points and computes a distance in d dimensions. For millions of points and thousands of features, that is painfully slow.
• With a KD-tree: $O(d \cdot \log n)$ per query in low dimensions. A KD-tree partitions space along alternating axes, letting the algorithm prune whole branches without checking every point. It works well when d is small (say, below 20).
• The curse of dimensionality. As d grows, all points become roughly the same distance from the query — the ratio of the farthest to the nearest neighbor approaches 1. At that point KD-trees degenerate to brute force, and nearest-neighbor itself loses meaning. This is the fundamental wall that makes k-NN brittle in high-dimensional spaces like raw images or text.
• No free guarantee. The Cover–Hart theorem gives k-NN at most 2× Bayes error as n → ∞, but real datasets are finite. Choosing k too small leads to overfitting (noisy boundaries); too large leads to underfitting (over-smooth boundaries).

This combination — zero training cost, linear query cost, and dimensional fragility — defines k-NN's niche. It remains the gold standard for small d, modest n, and situations where you cannot afford to retrain a model every time the data changes.

For related ideas on how distance and dimensionality interact, see dimensionality reduction.

"Find the closest examples and vote" turns out to be a surprisingly general primitive:

• Image classification baselines: before deep learning, k-NN on pixel histograms or SIFT features was a competitive benchmark. It is still used as a sanity-check baseline.
• Medical diagnosis: a patient's test results can be compared against a database of past patients; the k most similar cases cast votes on the likely diagnosis.
• Anomaly detection: if a new point has no close neighbors it is an outlier — k-NN distance to the k-th neighbor is a direct anomaly score.
• Recommendation systems: collaborative filtering finds the k users most similar to you and recommends what they liked. This is literally k-NN in user-preference space.
• Imputing missing data: replace a missing feature value with the average of that feature across the k nearest complete neighbors — a widely used preprocessing trick.
• Regression: instead of voting on a class, average the k neighbors' numeric targets. k-NN regression needs no distributional assumptions and adapts locally to whatever shape the data takes.

The algorithm's weakness — scaling to large n and high d — has spawned an entire field of approximate nearest-neighbor search (Annoy, HNSW, FAISS), which trades a small accuracy loss for orders-of-magnitude speed-up. Modern recommendation and PAC learning systems both build on these ideas.

k-Nearest Neighbors is the algorithm that refuses to learn anything in advance. It stores every training example raw, waits for a query, then solves the problem on the spot by asking its closest neighbors to vote. The result is a classifier with no hyperparameters to tune during training, a beautiful theoretical error guarantee, and a query cost that scales linearly — or logarithmically with the right data structure, until dimensions make that structure useless.

That tension — trivial to implement, treacherous to scale — is k-NN's enduring lesson. It shows that "intelligence" can emerge from pure memory and geometry without any optimization. And the curse of dimensionality it exposes is not a quirk of k-NN alone; it haunts every algorithm that relies on distances in high-dimensional space, making it one of the most important phenomena in all of PAC learning and machine learning.