k-Nearest Neighbors (k-NN)
No training phase, no density estimate — just the labels of the closest points.
On this page
Beginner: every classifier in this module so far has had a real "training" step — Naive Bayes (section 2.5.1) fits per-feature distributions, Gaussian Discriminant Analysis (section 2.5.2) fits class means and covariances. k-Nearest Neighbors has no training step at all. "Fitting" a k-NN model means literally copying the training set into memory and doing nothing else — this is often called lazy learning, because all the actual work is deferred until a prediction is asked for. To classify a new point, k-NN looks up the k stored training points closest to it and has them vote: whichever label is most common among those k neighbors becomes the prediction.
Intermediate: the deeper contrast with 2.5.1 and 2.5.2 is not just "no training" — it's a completely different strategy for getting at P(y|x). Naive Bayes and GDA both commit to a parametric family for the class-conditional density P(x|y) (independent 1-D distributions per feature, or a multivariate Gaussian) and estimate that family's parameters by MLE, only THEN combining with Bayes' rule to get P(y|x). k-NN never writes down a density for anything. It approximates P(y|x) directly and non-parametrically: "the probability of class c at this exact point x" is estimated as simply the fraction of x's nearest stored neighbors that happen to carry label c. No assumption about the shape of the data's distribution is made anywhere — which is both k-NN's greatest strength (it can represent decision boundaries of essentially any shape, given enough data) and, as this lesson will show precisely, the root of its greatest weakness in high dimensions.
Advanced: because k-NN's "model" is really just the raw training set plus a distance function, its effective capacity is not fixed the way a linear model's is — it grows with n, the amount of stored data (a genuinely nonparametric method, in the technical sense from section 2.1.5's learning theory: no finite-dimensional parameter vector bounds how complex the learned function can become). This lesson works through four things precisely: the family of distance metrics that make "nearest" a well-defined notion in the first place; the majority-vote decision rule and how k trades bias for variance; the classical Cover-Hart theorem bounding 1-NN's asymptotic error against the best possible classifier for the problem; and the curse of dimensionality, which explains exactly why "nearest neighbor" quietly stops meaning anything useful once the feature space gets large — a phenomenon that will resurface when Module 6 covers kernel methods.
The Minkowski family of distance metrics (of which Euclidean and Manhattan are special cases):
k-NN's non-parametric estimate of the posterior, and the resulting decision rule:
The Cover-Hart bound on 1-NN's asymptotic risk, for a K-class problem with Bayes-optimal risk R*:
For "nearest neighbor" to mean anything, we first need a notion of distance between two feature vectors x, x' ∈ ℝᵈ. The most general one in common use is the Minkowski distance of order p:
Two values of p recover the two most common metrics as special cases. Setting p = 2 gives ordinary straight-line (Euclidean) distance:
Setting p = 1 gives Manhattan (a.k.a. "taxicab" or L1) distance — you may already recognize this exact sum from the lasso penalty (section 2.3.3), which is no coincidence: both are the L1 norm, just applied to a difference vector here instead of a coefficient vector there:
Sending p → ∞ gives the Chebyshev distance, max_i |xᵢ−x'ᵢ| — the single largest per-feature gap, worth knowing exists even though it's rarely used in practice for k-NN.
Cosine distance is not a member of the Minkowski family at all — it measures something categorically different. Given two vectors x, x' (thought of as arrows from the origin, not as points to subtract), the cosine of the angle θ between them is:
Here is the key algebraic fact that makes cosine distance behave so differently from Euclidean or Manhattan: replace x' with any positive scalar multiple αx' (same direction, different length). Then:
The α cancels exactly. Cosine similarity — and therefore cosine distance — is completely blind to magnitude; it depends only on direction. Euclidean and Manhattan distance have no such invariance: scaling one vector changes both of them directly.
Worked example. Let Q = (2, 3) be a query vector, and compare it against two candidates: P1 = (4, 6) — exactly 2Q, same direction, double the length — and P2 = (3, 1), which points in a clearly different direction but is numerically closer to Q in the ordinary sense.
Euclidean and Manhattan both say P1 is farther from Q than P2 is (3.606 vs. 2.236; 5 vs. 3). Cosine says the exact opposite: P1 is identical in direction to Q (distance exactly 0), while P2 — despite being numerically closer — points somewhere genuinely different (distance ≈ 0.211). Neither answer is "wrong"; they are answering different questions. This is precisely why cosine distance is the standard choice for text represented as TF-IDF or bag-of-words vectors: a long document and a short document discussing the exact same topics in the same proportions point in the same direction but have very different magnitudes (more words → longer vector), and document length is rarely something you want influencing "how similar are these two documents." The interactive diagram below extends this exact comparison to six candidates and shows the predicted class itself flip depending on which metric is used.
Once "nearest" is defined by a chosen metric, let N_k(x) denote the set of indices of the k training points closest to a query x. The k-NN classifier's decision rule is a plurality vote among their labels:
For binary classification, choosing an odd k guarantees this vote can never end in an exact tie — one class always has strictly more votes than the other among an odd number of ballots. With more than two classes, an odd k no longer rules out ties (three classes could split 3-3-1 out of 7, for instance); a common, simple fallback is to shrink k by one until the tie resolves, or to break the tie by whichever tied class contains the single closest neighbor. A closely related and very common variant softens the rule even further with distance-weighted voting, letting closer neighbors count for more than farther ones instead of treating all k votes as equal:
The choice of k is the single most important knob k-NN has, and it is a direct, concrete instance of the bias–variance trade-off from section 2.1.3. With k = 1, the prediction at any point is decided by whichever single training point happens to be closest — including any mislabeled point or noisy outlier that happens to land nearby. The resulting decision boundary can wrap tightly around every quirk of the training sample: low bias (it can represent almost any local structure) but very high variance (a slightly different training sample, or a single moved point, can change predictions substantially) — the textbook picture of overfitting from section 2.1.4. As k grows, each prediction averages over more neighbors, so any one noisy point's influence shrinks: variance falls and the boundary smooths out, at the cost of rising bias, since real local structure at the finest scale gets averaged away too.
The two extremes make this precise. As k → n (using the entire training set for every prediction), N_k(x) stops depending on x at all — it's just "everyone" — so the estimated posterior collapses to a single constant, independent of the query's features entirely:
That is exactly the base-rate, majority-class prediction with zero dependence on the input — maximum bias, minimum variance, and precisely the definition of underfitting from section 2.1.4. Choosing k in practice (typically by cross-validation) is nothing more than picking a point on this same bias–variance curve that every other model in this course has to navigate, just parameterized very differently than a regularization strength like ridge or lasso's λ.
Cover and Hart's 1967 result is one of the most surprising facts in all of classification theory: as the training set grows without bound, the simplest possible classifier — "copy the label of whichever training point is closest, with zero training and zero assumptions about the data's distribution" — has an error rate that can never exceed twice the error rate of the best classifier theoretically possible for that exact problem. Here is the argument in full, at a query point x.
Step 1 — the nearest neighbor converges to the query itself. Suppose the feature distribution has positive density in a neighborhood of x. For any radius ε > 0, the probability that a single training point drawn i.i.d. lands inside the ε-ball around x is some fixed p_ε > 0. The probability that none of n independent training points land in that ball is (1 − p_ε)ⁿ, which shrinks to 0 as n → ∞. So for every ε, eventually some training point falls within ε of x — meaning the nearest neighbor's distance to x converges to exactly 0 as n → ∞.
Step 2 — its label is therefore a fresh draw from the true P(y|x) at x. The nearest neighbor's label y' is drawn from P(y | x'), where x' is its feature vector. Since x' → x and (assuming P(y|·) varies continuously) P(y|x') → P(y|x), in the limit y' behaves like an independent sample from exactly the same categorical distribution over labels, P(·|x), that generated the true label y at the query. The 1-NN prediction is, in the limit, literally a second, independent roll of the same dice that produced the truth.
Step 3 — translate that into a risk formula. Write the sorted class posteriors at x as p₁ ≥ p₂ ≥ … ≥ p_K (so p₁ is the Bayes-optimal choice's probability of being right). The Bayes risk at x is:
Two independent draws from the same K-way categorical distribution agree with probability Σ_c p_c² (sum, over each class, of "both draws land on c"). So the asymptotic 1-NN risk at x — the probability the fresh draw disagrees with the truth — is:
Step 4 — the lower bound. Since every p_c ≤ p₁, we have p_c² ≤ p₁ p_c for each c; summing over all c gives Σ p_c² ≤ p₁ Σ p_c = p₁ (because the posteriors sum to 1). Therefore:
As expected, 1-NN can never beat the Bayes-optimal classifier — this direction of the bound is the unsurprising half.
Step 5 — the upper bound. This is the interesting direction: how much worse than optimal can 1-NN possibly be? Fix p₁, and ask how the remaining probability mass 1 − p₁ should be distributed across the other K − 1 classes to make Σ p_c² as SMALL as possible (which makes R_1-NN(x), its complement, as LARGE as possible — the worst case). By the QM-AM inequality, a fixed sum of K − 1 nonnegative numbers has the smallest sum of squares when the numbers are all equal — i.e. when the remaining mass is spread perfectly evenly, (1−p₁)/(K−1) to each of the other classes:
Substituting this worst case (writing R* = R*(x) = 1 − p₁, so p₁ = 1 − R*) into R_1-NN(x) = 1 − Σ p_c²:
Since K/(K−1) · R* ≥ 0, the bracketed term is at most 2, giving the loosest but simplest form of the bound, R_1-NN(x) ≤ 2R*(x). Averaging both bounds over the marginal distribution of x turns these point-wise statements into the overall risks, giving exactly the Cover-Hart theorem stated above:
For binary classification (K = 2) this simplifies to the commonly quoted form R* ≤ R_1-NN ≤ 2R*(1 − R*) ≤ 2R*. Notice what the bound actually says: it isn't a fixed constant error rate — it scales with the Bayes error itself. When a problem is easy (classes barely overlap, R* near 0), 1-NN's error is squeezed toward 0 right along with it; the "twice as bad" slack only really opens up on genuinely hard, high-overlap problems. A classifier that fits nothing, assumes nothing, and just copies its nearest neighbor's label is, asymptotically, never catastrophically far from whatever the best possible classifier for that exact problem could achieve.
Everything above assumed the training set is dense enough that a genuinely nearby point exists to be found. That assumption quietly fails as the number of features d grows — this is the curse of dimensionality, and it is the single biggest practical limitation of k-NN (and, as will resurface in Module 6, of every purely local/kernel-based method).
The volume argument. Consider data spread uniformly across a d-dimensional unit hypercube, [0,1]ᵈ. To capture some fixed fraction f of the data using an axis-aligned neighborhood that reaches the same proportion r of the range along every one of the d axes, the neighborhood's volume is r^d, so capturing a fraction f requires:
Take f = 0.01 — a genuinely "local" 1% slice of the data — and watch what happens to the required edge length r as d increases:
At d = 100, capturing a mere 1% of the data locally requires a neighborhood spanning 95.5% of the range of every single feature. There is no such thing as a small, local neighborhood anymore — "nearest" and "far away" have stopped being meaningfully different concepts.
The distance-concentration argument. The same phenomenon shows up directly in the distances themselves. Squared Euclidean distance between two points is a sum of d per-coordinate squared differences:
If the coordinates are reasonably independent, this is a sum of d roughly i.i.d. terms — and by the same law-of-large-numbers logic that shrinks a sample mean's standard error, the sum concentrates ever more tightly around its expected value d·σ² as d grows, with relative fluctuation shrinking like 1/√d:
In plain terms: pick any two points at random in a high-dimensional space, and their distance is very nearly the same as the distance between any OTHER two random points. Nearest and farthest neighbor converge to roughly the same value — precisely the phenomenon the third diagram below lets you watch happen, live, as you drag d upward.
Why this means k-NN needs exponentially more data. To keep a fixed-size local neighborhood (radius r, for some small constant r < 1) containing roughly the same number of training points as d grows, the local point density has to stay constant — but the neighborhood's volume, as a fraction of the whole space, shrinks like r^d. Keeping the expected point count inside it constant therefore requires the total sample size n to grow like r^(−d) — exponentially in d. This is the formal content of "the curse of dimensionality": every additional feature doesn't just add a little more work, it multiplies the amount of data required to keep neighborhoods meaningfully local. In practice this is exactly why raw k-NN degrades badly on high-dimensional raw feature spaces (e.g. large numbers of weakly-informative measurements) unless preceded by dimensionality reduction, feature selection, or a learned embedding that concentrates the signal into far fewer effective dimensions.
Background shading is the majority-vote prediction across the whole plane at the current k. Drag the black point to see its own k nearest neighbors highlighted and its live prediction; watch the region boundary sharpen at small k and smooth out at large k.
All six candidates are drawn as vectors from the origin, so cosine's angle-based comparison is visually literal. Toggle metrics to see which three points count as nearest under each one — and note the vote can flip.
Same fixed set of points, more dimensions revealed as d increases. The nearest/farthest ratio climbs toward 1 and the bar heights (each point's distance, normalized) converge together — 'nearest neighbor' loses its meaning.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
double euclideanDistance(const std::vector<double>& a, const std::vector<double>& b) {
double sum = 0.0;
for (size_t i = 0; i < a.size(); ++i) {
double diff = a[i] - b[i];
sum += diff * diff;
}
return std::sqrt(sum);
}
int knnPredict(const std::vector<std::vector<double>>& X, const std::vector<int>& y,
const std::vector<double>& query, int k) {
int n = static_cast<int>(X.size());
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), 0);
// Brute-force: sort ALL n points by distance to the query -- O(n log n) per prediction.
// A k-d tree / ball tree (see "Going deeper") sidesteps visiting every stored point.
std::sort(idx.begin(), idx.end(), [&](int i, int j) {
return euclideanDistance(X[i], query) < euclideanDistance(X[j], query);
});
std::vector<int> votes(2, 0); // binary labels 0/1 for this example
for (int i = 0; i < k; ++i) votes[y[idx[i]]]++;
return votes[1] > votes[0] ? 1 : 0;
}
int main() {
std::vector<std::vector<double>> X = {{1, 1}, {1.5, 2}, {2, 1}, {6, 5}, {6.5, 6}, {7, 5.5}};
std::vector<int> y = {0, 0, 0, 1, 1, 1};
std::vector<double> query = {3.5, 3.5};
int k = 3;
std::cout << "Predicted class: " << knnPredict(X, y, query, k) << "\n";
return 0;
}- Recommender systems — "users who liked this also liked…" and item-to-item similarity lookups are frequently literal nearest-neighbor searches over learned embedding vectors.
- Image and audio retrieval — reverse image search and "find similar" features typically embed content into a vector space and run k-NN (often with an approximate index, see "Going deeper") over millions of stored embeddings.
- Anomaly / fraud detection — a point whose nearest neighbor is unusually far away (relative to how tightly-packed normal data usually is) is a natural and cheap outlier signal, with no need to fit a full density model.
- Fast baselines — because it requires no training and almost no modeling assumptions, k-NN is a common first thing to try on any new classification or regression problem, if only to have a sanity-check number to beat before reaching for something more sophisticated.
- Bioinformatics — classifying a new gene-expression or protein profile by the labels of the most similar previously-characterized profiles, when no clean parametric model of "what a healthy profile looks like" is available.
- Missing-value imputation — filling in a missing feature with the average (or majority) value from the k most similar complete records, the same local-averaging idea applied to imputation instead of classification.
- Forgetting to standardize features before computing distances. A feature measured in the tens of thousands (e.g. income in dollars) will completely dominate every distance calculation over a feature measured in single digits (e.g. age in years), regardless of which one is actually more predictive — every distance metric derived above treats a feature's raw numeric scale as meaningful.
- Applying raw k-NN to high-dimensional data without a second thought. Derivation 4 above isn't a theoretical curiosity — dozens or hundreds of raw features genuinely can make "nearest neighbor" nearly meaningless. Dimensionality reduction, feature selection, or a learned embedding should usually come first.
- Picking an even k for binary classification. An even
kreintroduces the exact tie problem the odd-kconvention in Derivation 2 exists to avoid, and different libraries break ties differently (often silently, by training-set order) — a frequent source of hard-to-reproduce prediction flips. - Assuming "no training phase" means "fast." k-NN pushes ALL of its cost to prediction time — a brute-force lookup costs
O(n)(orO(n log n)with a full sort) per single query, unlike a linear or Gaussian model whose prediction cost doesn't grow with the training-set size at all. At real production data volumes this is a genuine latency and infrastructure concern, not a minor implementation detail.
Going deeper
Two things worth knowing that go beyond this lesson's core scope. First: the naive O(n) brute-force query cost flagged in the Pitfall above is exactly what spatial index structures exist to fix. A k-d tree recursively partitions the feature space along alternating axes, letting a query prune away most of the training set without ever computing its distance, typically bringing average query cost down to roughly O(log n) in low dimensions; a ball tree generalizes the same idea with hyperspherical regions and holds up better as dimensionality grows. Both, however, degrade back toward brute-force behavior as d gets large — another face of the curse of dimensionality derived above. At the truly massive scale of modern retrieval and recommendation systems, exact nearest-neighbor search is often abandoned altogether in favor of approximate nearest neighbor (ANN) methods — locality-sensitive hashing (LSH) and graph-based indexes like HNSW — which trade a small amount of exactness for dramatic speed at billions of stored vectors.
Second: k-NN's posterior estimate, P̂(y=c|x) = (1/k)Σ 1[yᵢ=c], is a special case of a much broader idea called local averaging — estimate something about a query point using only the training points near it, weighted by proximity. Kernel density estimation, a preview of section 2.13.3, is the direct continuous-density cousin of exactly this idea: instead of a hard cutoff at the k-th neighbor, it uses a smooth kernel (weighting function) around the query and never needs to fix a count k at all. Seeing k-NN as "the K nearest points get an equal vote" and KDE as "every point gets a smoothly-decaying vote" is the cleanest way to understand both as two instances of the same underlying family of methods.
Cover-Hart's bound frames 1-NN's asymptotic error as R* ≤ R_1-NN ≤ 2R*, tied directly to the Bayes error R* of the SAME problem, rather than as some fixed universal error rate. Why is that framing — rather than a constant — the more meaningful (and reassuring) way to state the result?
Because the bound scales with how hard the problem itself is. The derivation shows R_1-NN(x) = 1 − Σp_c², bounded above by R*(x)·(2 − K/(K−1)·R*(x)) — an expression that shrinks toward 0 exactly as fast as R*(x) does. On an easy problem (classes barely overlap, R* near 0), 1-NN's asymptotic error is squeezed toward 0 right along with the Bayes error; the full 'twice as bad' slack only opens up on genuinely hard, high-overlap problems, where even the best possible classifier is already struggling. It's reassuring precisely because a classifier that fits zero parameters, makes zero distributional assumptions, and does nothing more sophisticated than copying its nearest neighbor's label still comes with a distribution-free guarantee: it is never catastrophically far from whatever the best conceivable classifier for that exact problem could achieve, no matter how easy or hard that problem happens to be.
k-NN doesn't fit neatly into the generative-vs-discriminative split the rest of this module is built around: it estimates P(y|x) directly like a discriminative model, but does so non-parametrically from local neighborhood frequencies rather than through any explicit functional form the way logistic regression (2.4.1) does — and it never touches a class-conditional density the way Naive Bayes (2.5.1) or GDA (2.5.2) do. That makes it a genuinely useful third data point — neither fish nor fowl — for section 2.5.4's rigorous comparison of the generative and discriminative philosophies that closes this module.