k-Nearest Neighbors Classification

Your interviewer asks a deceptively simple question: "what does k-nearest neighbors learn during training?" The correct answer is almost a trick: nothing — fit stores the training data. Every kNN model is the dataset plus a distance metric and a value of k. All the work happens at prediction time, and walking through that machinery once makes every other kNN interview question easy.

For a query point x, predict does exactly this:

1. Compute the distance from x to every one of the n training rows, using the configured metric (default: Minkowski with p=2, i.e. Euclidean).
2. Keep the k rows with the smallest distances — the neighborhood.
3. Let those neighbors vote. For classification, the majority class wins; with weights='distance', each vote is weighted by inverse distance.

The voting math, with a concrete example. Suppose k = 5 and the neighborhood votes come back labels [1, 1, 0, 1, 0] → class 1 wins 3–2 under uniform voting. Now suppose the same five neighbors sit at distances [0.10, 0.20, 0.40, 0.60, 1.20]:

uniform vote:    class 0: 2,  class 1: 3                 → predict 1
distance-weight: w = 1/d = [10.0, 5.0, 2.5, 1.67, 0.83]
                 class 0: 2.5 + 0.83 = 3.33
                 class 1: 10.0 + 5.0 + 1.67 = 16.67      → predict 1 (94% of weight)

The close neighbors now swamp the far ones. weights='distance' is the practical answer whenever your neighborhoods are of uneven quality — dense clusters vote reliably, but a query landing in a sparse region gets distant, unreliable neighbors, and inverse-distance weighting mutes them. (Points at distance exactly 0 — duplicate rows with conflicting labels — get effectively infinite weight, which is one reason duplicate handling matters.)

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

knn = Pipeline([
    ("scale", StandardScaler()),          # non-negotiable — see the previous topic
    ("model", KNeighborsClassifier(
        n_neighbors=5,
        weights="distance",               # 1/d voting instead of equal votes
        metric="minkowski", p=2,          # Euclidean; p=1 gives Manhattan
        algorithm="auto",
    )),
])
knn.fit(X_train, y_train)                 # no optimization: it stores the arrays

Two variants round out the API. For regression, kNN predicts the (weighted) mean of the neighborhood's targets — the identical rule with a number instead of a class — and it therefore can never predict outside the range of targets it saw in the neighborhood, echoing the extrapolation limit you met in Random Forests. For classification, scikit-learn's tie rule is documented rather than random: when classes tie in the vote, the class with the smallest label wins. Deterministic is not the same as correct, which is why odd k on a binary problem sidesteps the whole question.

The two ends of the k spectrum define the bias–variance story you will be asked to tell. With k = 1, every training point is its own nearest neighbor: the model scores 100% on training data and carves an erratic boundary that wraps around every noisy label — maximum variance, memorization of noise. As k grows, the boundary smooths: it must average more votes, local quirks disappear, and the decision surface drifts toward the majority class — falling variance, rising bias, until at k = n the model predicts the majority class everywhere and has learned nothing. Somewhere between the two is a validation-tuned sweet spot, which is the next chapter.

Underneath it all sits an assumption worth saying aloud in interviews: kNN works only if nearby points tend to share labels — the smoothness assumption. Points from two classes interleaved at random at fine granularity defeat it entirely, no matter what k you choose, because there is no neighborhood structure to exploit.

"You set k = 5 — why?" is the standard follow-up, and "it's common" ends the conversation. The defensible answer walks through a validation curve and shows where the minimum landed:

import numpy as np
from sklearn.model_selection import cross_val_score

ks = list(range(1, 51, 2))                 # odd k dodges binary ties
train_err, val_err = [], []

for k in ks:
    clf = Pipeline([("scale", StandardScaler()),
                    ("model", KNeighborsClassifier(n_neighbors=k))])
    tr = 1 - cross_val_score(clf, X_train, y_train, cv=5,
                             scoring="accuracy", n_jobs=-1).mean()
    val_err.append(tr)

best = ks[int(np.argmin(val_err))]
print(f"best k = {best}, error = {min(val_err):.4f}")

The curve you get has a recognizable shape: k = 1 starts at zero training error (each point votes with itself), validation error falls as neighbors smooth out label noise, bottoms out somewhere in the middle, then climbs again as the vote is diluted toward the global majority. Read the three regions as variance, balance, and bias:

Heuristics to mention but not to hide behind: k ≈ √n is a rough starting point (n = 10,000 → try k ≈ 100), and odd k avoids ties in binary problems — though with 3+ classes ties remain possible, and scikit-learn then breaks them deterministically by picking the class with the smallest label. Always cross-validate; k is cheap to tune because each candidate reuses the same stored data.

k is not the only knob worth sweeping in that loop — the metric pair costs nothing to add:

from sklearn.model_selection import GridSearchCV

grid = {
    "model__n_neighbors": [3, 5, 11, 25],
    "model__weights": ["uniform", "distance"],
    "model__p": [1, 2],                   # Manhattan vs Euclidean
}
gs = GridSearchCV(pipe, grid, cv=5, scoring="roc_auc", n_jobs=-1).fit(X_train, y_train)
print(gs.best_params_)

Interpret the combination you win with, not just the winner: p=1 beating p=2 is evidence about your data (heavy-tailed noise or high-dimensional sparsity — exactly the case argued in Distance and Similarity Metrics), and weights='distance' winning over uniform signals uneven density across the feature space. A best-params dict is a diagnosis of your data's geometry, not a lucky draw.

Two interactions matter more than the search range. First, class imbalance punishes large k directly: if positives are 3% of rows, almost every wide neighborhood is majority-negative, so the model suppresses exactly the enclaves you care about — smaller k and weights='distance' both counteract this, and so does class-resampled training data (see Class Imbalance Remedies for the broader toolkit). Second, irrelevant features degrade kNN before they degrade anything else: with 100 columns of which 60 are noise, each distance sum accumulates 60 noise terms, and neighbors get selected mostly by noise. Scaling settles the unit problem — the point made in Distance and Similarity Metrics — but only feature selection or a metric that ignores coordinates (cosine on sparse text, for instance) settles the dilution problem.

Note what not to tune: kNN has no regularization strength, no learning rate, no depth. Its entire capacity is controlled by three things — k, the metric, and the feature set — which is simultaneously why it is so easy to set up and why tuning it feels shallower than tuning a gradient-boosted model. When validation stalls after sweeping k, the problem is upstream: the features or the metric, not the neighborhood size.

Choosing k is the last modeling decision. Then the model ships, and the bill arrives at query time.

kNN's training step is a memory copy, which makes it delightful in notebooks and dangerous in production. A single prediction in scikit-learn's brute-force mode costs O(n · d) — one distance computation per training row per query — plus the selection of the k smallest:

10,000 rows × 128 features  →   1.28 M multiply-adds per query     (~sub-ms, fine)
10,000,000 rows × 128 dims  →   1.28 B multiply-adds per query     (hundreds of ms, dead on arrival)

The memory side is equally blunt: 10M vectors × 128 dims × 4 bytes = 5.1 GB just to hold the "model", before any index structure. In other words, kNN converts training cost into serving cost — you pay once upfront, or you pay on every request.

Scikit-learn offers index structures that dodge part of the bill via algorithm=:

The unifying failure: as d grows, a query's distance to a branch boundary becomes uninformative, pruning stops cutting anything, and the tree quietly collapses back to scanning everything — you keep the index's memory overhead and lose the speedup. algorithm="auto" picks a structure from heuristics on your fitted data, which is fine for prototyping but worth pinning explicitly in production: an index whose pruning ratio you have measured is an asset, one you inherited silently from a default is a liability you discover under load.

At millions of rows, production systems switch to approximate nearest neighbor (ANN) indexes and accept a recall/latency trade-off:

import faiss
import numpy as np

d, xb = 128, np.random.rand(10_000_000, 128).astype("float32")
index = faiss.IndexFlatL2(d)        # exact: same O(n·d) scan, but SIMD-optimized
# index = faiss.IndexHNSWFlat(d, 32)   # approximate: graph traversal, orders of magnitude faster
index.add(xb)

xq = np.random.rand(1, 128).astype("float32")
dist, ids = index.search(xq, k=10)  # top-10 neighbors with distances

IndexFlatL2 is exact brute force in optimized C++; IndexHNSWFlat (graph-based), IVF partitions, or product quantization trade recall@k — the fraction of true neighbors the approximate search returns — for latency. The design conversation to have ready for "how would you serve 10M vectors under 10 ms?": normalize and prune features first, choose the metric deliberately, pick an ANN index sized to your RAM, measure recall@k against exact search on a sample, and cap the candidate pool (e.g., retrieve top-500 by coarse partition, then re-rank with the exact metric).

Operational realities round it out: updates are cheap and expensive at once — inserting a row is O(1) for brute force but may trigger costly index rebuilds for trees and graphs; a "refit" in kNN is reindexing, not retraining. Class imbalance and label noise surface directly in neighborhoods, so keep a dedup/label-cleaning pass upstream — one contradictory duplicate at distance 0 can hijack a query under distance-weighted voting. And the conceptual bookend for your interview: kNN carries every training point into production to keep its options open, while Support Vector Max-Margin Classifiers compresses the same idea to the few points that actually pin down the boundary — two opposite answers to "how much of the training data does a decision rule need?"