K-Nearest Neighbors (KNN)

How KNN works

KNN is almost insultingly simple, and that's its charm. To classify a new point, you do three things: measure the distance from it to every labeled point you've stored, keep the k closest ones, and let those k neighbors vote on the label. The most common label among the neighbors becomes the prediction. For regression, you average their numeric values instead of voting.

There is no model fitting in the usual sense. A logistic regression learns coefficients; a neural network learns millions of weights; a decision tree carves the space into rules. KNN learns nothing. It memorizes the training set verbatim and pushes all computation to prediction time — which is why it's called a lazy learner or an instance-based method. The training set is the model.

The whole algorithm hinges on one choice: how do you measure "close"? The default is Euclidean (straight-line) distance, but Manhattan, Minkowski, cosine, and Hamming distances all show up depending on the data. And the second choice — the value of k — controls how smooth or jagged the decision boundary is. Those two knobs are the entire model.

Distance metrics and the role of k

For two points p and q in d dimensions, the common distances are:

Euclidean (L2):   d(p,q) = sqrt( Σ (pᵢ − qᵢ)² )
Manhattan (L1):   d(p,q) = Σ |pᵢ − qᵢ|
Minkowski (Lᵖ):   d(p,q) = ( Σ |pᵢ − qᵢ|ᵖ )^(1/p)   # generalizes both
Cosine distance:  d(p,q) = 1 − (p·q) / (‖p‖ ‖q‖)     # angle, ignores magnitude

Euclidean is the right default for dense numeric features on a comparable scale. Cosine wins for text and high-dimensional sparse vectors where the direction matters more than length — two documents about the same topic point the same way regardless of how long they are. Hamming distance counts mismatched positions and is the metric for categorical or binary features.

The parameter k trades bias against variance. With k = 1, every query takes the label of its single closest point — the decision boundary is maximally jagged, and a single mislabeled or noisy training point creates a wrong island around itself. As k grows, the boundary smooths out; at k = n (every point votes), KNN degenerates into "always predict the majority class." The sweet spot lives between those extremes, and you find it with cross-validation, not intuition.

When to use KNN — and when not to

• Small to medium datasets where O(n·d) per query is affordable — thousands to low millions of points, not billions.
• Low-dimensional feature spaces (roughly under 10–20 features) where the notion of "nearest" still carries signal.
• Irregular, non-linear decision boundaries that a linear model can't capture. KNN's boundary follows the data exactly.
• Quick baselines and prototypes. With near-zero setup, KNN is the fastest way to get a "what's even possible here" accuracy number before investing in a heavier model.
• Recommendation and similarity search — "find me items like this one" is literally a nearest-neighbor query.

Avoid KNN when prediction latency matters (each query touches the whole dataset), when you have hundreds of features (the curse of dimensionality erases the meaning of distance), or when the dataset is huge and you can't index it. In those cases reach for a tree ensemble, a linear model, or an approximate-nearest-neighbor index.

KNN vs other classifiers

	KNN	k-means	Decision tree	Logistic regression	Naive Bayes
Learning type	Supervised	Unsupervised	Supervised	Supervised	Supervised
Training cost	O(1) — store data	O(n·k·i)	O(n·d·log n)	O(n·d·i)	O(n·d)
Prediction cost	O(n·d) brute / O(d·log n) tree	O(k·d) per point	O(depth)	O(d)	O(d·c)
Memory at inference	O(n·d) — all data	O(k·d) centroids	O(nodes)	O(d) weights	O(d·c)
Decision boundary	Arbitrary, follows data	Voronoi cells	Axis-aligned rectangles	Linear hyperplane	Quadratic / linear
Sensitive to feature scale	Yes — must standardize	Yes	No	Yes (for regularization)	No
Handles non-linear data	Yes, natively	N/A (clustering)	Yes	No (needs features)	Limited
Interpretability	"Here are the k neighbors"	Cluster membership	High (readable rules)	Medium (coefficients)	Medium

The headline contrast is where the cost lives. KNN spends nothing at training and everything at inference; almost every other classifier is the reverse — pay once to fit, then predict cheaply forever. That makes KNN attractive when data arrives continuously (just append to the store) and unattractive when you serve many low-latency predictions.

What the numbers actually say

• Brute-force query is O(n·d). Classifying one point against 1,000,000 stored 50-dimensional examples is 50 million floating-point subtract-square-add operations per query. On a single core at roughly 10⁹ simple FLOPs/second that's about 50 ms per prediction — fine for one query, a disaster at 10,000 queries/second.
• KD-trees help only in low dimensions. They cut typical query cost to about O(d·log n), so the same million-point lookup drops to roughly 20 comparisons' worth of work in 2–3 dimensions. But by ~15–20 dimensions the tree prunes almost nothing and degrades back to brute force — the curse of dimensionality in action.
• Distances concentrate in high dimensions. In 1,000 dimensions of uniform random data, the nearest and farthest neighbors of a query are typically within a few percent of the same distance. "Nearest" loses meaning, and accuracy collapses.
• k ≈ √n is a starting point, not an answer. For n = 10,000 that suggests k ≈ 100, but the cross-validated optimum is often far smaller. Always sweep k; the heuristic just bounds the search.
• Memory is the data itself. KNN stores every training point at full precision: 1,000,000 × 50 features × 8 bytes ≈ 400 MB just to hold the model. There is no compression — that's the cost of laziness.

JavaScript implementation

// points: [{ features: [..], label: 'A' }, ...]
function euclidean(a, b) {
  let s = 0;
  for (let i = 0; i < a.length; i++) { const d = a[i] - b[i]; s += d * d; }
  return Math.sqrt(s);
}

function knnClassify(points, query, k) {
  // 1. distance to every stored point  (O(n·d))
  const scored = points.map(p => ({
    label: p.label,
    dist: euclidean(p.features, query),
  }));

  // 2. keep the k closest
  scored.sort((a, b) => a.dist - b.dist);     // O(n log n); a heap gives O(n log k)
  const neighbors = scored.slice(0, k);

  // 3. majority vote (distance-weighted: closer neighbors count more)
  const votes = new Map();
  for (const { label, dist } of neighbors) {
    const w = 1 / (dist * dist + 1e-9);       // inverse-square weighting
    votes.set(label, (votes.get(label) || 0) + w);
  }

  let best = null, bestW = -Infinity;
  for (const [label, w] of votes) if (w > bestW) { bestW = w; best = label; }
  return best;
}

Two production-grade touches are baked in. First, the full sort is O(n log n); for large n a max-heap of size k gives the k smallest in O(n log k) and avoids sorting points you'll throw away. Second, the vote is distance-weighted — a neighbor sitting almost on top of the query should outweigh one at the edge of the k-set. Plain unweighted majority is the textbook version, but weighting almost always helps and breaks ties naturally.

Python implementation

import numpy as np
from collections import Counter

def knn_classify(X_train, y_train, query, k=5):
    # X_train: (n, d) array, already standardized.  query: (d,) array
    # 1. squared Euclidean distance to all points, vectorized  (O(n·d))
    diffs = X_train - query                 # broadcast
    dists = np.einsum('ij,ij->i', diffs, diffs)   # sum of squares per row

    # 2. argpartition gets the k smallest in O(n), no full sort
    idx = np.argpartition(dists, k)[:k]

    # 3. majority vote among the k nearest labels
    return Counter(y_train[idx]).most_common(1)[0][0]


# --- choosing k by cross-validation (the part people skip) ---
def best_k(X, y, ks=range(1, 31), folds=5):
    n = len(X)
    fold = np.array_split(np.random.permutation(n), folds)
    scores = {}
    for k in ks:
        correct = 0
        for f in range(folds):
            test = fold[f]
            train = np.concatenate([fold[j] for j in range(folds) if j != f])
            for i in test:
                pred = knn_classify(X[train], y[train], X[i], k)
                correct += (pred == y[i])
        scores[k] = correct / n
    return max(scores, key=scores.get)

Note the np.argpartition trick: it rearranges the distance array so the k smallest values sit in the first k slots, in linear time, without paying for a full sort. The np.einsum call computes per-row squared norms in one fused pass. And crucially, the second function shows the part tutorials omit — KNN has a hyperparameter, and you pick it with cross-validation, not a guess. In practice, reach for sklearn.neighbors.KNeighborsClassifier, which wraps a KD-tree / ball tree and these optimizations.

Variants worth knowing

Weighted KNN. Instead of one-vote-per-neighbor, weight each neighbor by 1/distance (or a kernel). Closer points dominate, the choice of k becomes less sensitive, and ties vanish. Almost always a strict improvement over the plain vote.

Radius / fixed-radius neighbors. Rather than the k closest, take all points within a fixed radius r. This adapts to local density — dense regions vote with more neighbors, sparse ones with fewer — but you must handle queries that land in empty space with zero neighbors.

KD-trees and ball trees. Spatial indexes that prune branches that can't contain a nearer neighbor, dropping query cost to about O(d·log n) in low dimensions. Ball trees use hypersphere bounds and degrade more gracefully than KD-trees as d rises, but both collapse to brute force in very high dimensions.

Approximate nearest neighbors (ANN). When exact KNN is too slow, trade a little accuracy for huge speed: locality-sensitive hashing and HNSW graphs find probably the nearest neighbors in sub-linear time. This is how billion-scale vector search (image retrieval, semantic search) actually runs.

Condensed and edited KNN. Prune the stored set: condensed KNN keeps only the points needed to reproduce the decision boundary; edited KNN deletes noisy points that disagree with their neighbors. Both shrink memory and speed up queries while preserving accuracy.

Common bugs and edge cases

• Forgetting to scale features. The number-one KNN mistake. A feature in dollars (0–100,000) completely dominates a feature in years (0–40) under Euclidean distance. Always standardize or min-max scale first — fit the scaler on the training set only, then apply it to queries.
• Even k on a binary problem. With k = 4 you can get a 2–2 tie. Keep k odd for two classes, or use distance weighting to break ties deterministically.
• Leaking the query into its own neighbor set. When evaluating on the training set, a point's nearest neighbor is itself at distance 0 — giving a deceptively perfect k = 1 score. Exclude the point itself, or evaluate on held-out data.
• Trusting KNN in high dimensions. Past ~20 features, distances concentrate and "nearest" is noise. Reduce dimensions with PCA or pick another model — don't just crank k.
• Imbalanced classes silently win. If 95% of points are class A, large k makes nearly every prediction A regardless of the query. Use distance weighting, class-balanced voting, or resample.
• Ignoring ties in distance. When the k-th and (k+1)-th points are equidistant, which one is "in"? Different libraries break ties differently — decide deliberately rather than inheriting an arbitrary default.