K-nearest neighbors

1. Intuition

You move to a new city and want to guess whether a neighborhood is expensive. You look at the five closest houses that sold recently. If four of them were expensive, you guess "expensive." That is KNN with K = 5.

Three choices define the model:

1. What "close" means. You need a distance between two examples. With numeric features, the usual choice is straight-line (Euclidean) distance.
2. How many neighbors (K). One neighbor trusts a single, possibly unusual, example. Fifty neighbors average over a wide area and may blur real local differences.
3. How neighbors combine. Classification uses a majority vote; regression averages the neighbors' targets. Closer neighbors can be given more weight.

KNN does no work at training time; it just stores the data. All the work happens at prediction time, when it compares the new example against every stored one. That makes it a lazy or instance-based learner.

2. Visualization

Try it (predict first, then check):

1. Leave scaling off and drag the query left and right. Predict whether the prediction changes, then check.
2. Compare leave-one-out accuracy at K = 1 and K = 25 with scaling on. Which generalizes better here?

What to notice:

• K = 1 draws a region around every single point, including mislabeled or unusual ones. It fits the training data perfectly and generalizes worse (high variance).
• K = 15 produces a smooth boundary close to the true rule (buy if older than about 45).
• Raw units silently turn KNN into "find people with similar income." Nothing errors; the model is just wrong.

3. The math

Symbols

Distances

Euclidean is the straight line; Manhattan is the city-block path. Manhattan is less dominated by a single large difference because it does not square.

Prediction

Standardization

After standardizing, every feature has mean 0 and standard deviation 1 on the training set, so one unit means "one standard deviation" for every feature.

Worked example

Five past customers (age in years, income in thousand dollars) and whether they bought. Predict for query $q = (45, 56)$ with $K = 3$.

Step 1: raw differences and Euclidean distances.

Step 2: vote. The three nearest are E (15.03, bought), B (19.42, did not), A (23.09, did not). Votes: 2 to 1 for did not buy.

(Manhattan distances are A 25, B 23, C 35, D 28, E 16; same three neighbors, same answer.)

Step 3: standardize. On these five rows, age has $\mu = 39.8$, $\sigma = 14.03$ and income has $\mu = 58.2$, $\sigma = 19.12$ (population standard deviation). The query becomes

and customer D becomes $\left(\frac{47-39.8}{14.03}, \frac{30-58.2}{19.12}\right) = (0.513, -1.475)$, so its distance is $\sqrt{(0.513-0.371)^2 + (-1.475+0.115)^2} = \sqrt{0.020 + 1.850} = 1.367$. Doing the same for everyone:

Step 4: vote again. The three nearest are now E (1.070, bought), D (1.367, bought), B (1.370, did not). Votes: 2 to 1 for bought.

Same data, same K, opposite prediction. In raw units, income differences (up to 34) outweighed age differences; D was "far" only because of income. After scaling, D's nearly identical age counts for what it should.

Key distinction

Fit $\mu$ and $\sigma$ on the training split only, then apply them to validation, test, and production queries. Computing them on all data leaks information from the test set.

4. Implementation

Build it from scratch

The full script is code/05-instance-and-probabilistic/knn_scratch.py. It uses only NumPy for the model and scikit-learn only to check the answer.

Distances. Everything in KNN rests on one function: the distance from a query to every stored row. Broadcasting X - q subtracts the query from all $n$ rows at once, giving an $[n, p]$ array; summing over axis 1 gives one distance per row. Cosine distance is included because it is the default for text embeddings: it compares direction and ignores length.

def distances(X, q, metric="euclidean"):
    diff = X - q                                    # [n, p] by broadcasting
    if metric == "euclidean":
        return np.sqrt((diff**2).sum(axis=1))       # [n]
    if metric == "manhattan":
        return np.abs(diff).sum(axis=1)
    if metric == "cosine":                          # 1 - cos(angle); ignores length
        norms = np.linalg.norm(X, axis=1) * np.linalg.norm(q)
        return 1 - (X @ q) / np.maximum(norms, 1e-12)
    raise ValueError(metric)

Predict: two vectors point the same way but one is twice as long. What is their cosine distance, and what is their Euclidean distance?

Scaling. Section 3 showed that units can flip the prediction. The scaler is split into fit (learn $\mu$, $\sigma$ from training rows) and apply (reuse them on anything), so queries never leak into the statistics. The 1e-12 floor stops a constant feature from dividing by zero.

def fit_scaler(X_train):
    mu = X_train.mean(axis=0)
    sigma = np.maximum(X_train.std(axis=0), 1e-12)  # guard: constant feature
    return mu, sigma

def apply_scaler(X, mu, sigma):
    return (X - mu) / sigma                         # same mu, sigma for every query

Predict: if you called fit_scaler on the query alone, what would the standardized query be?

Find K nearest and vote. argsort orders the distances; the first k indices are the neighbors. A Counter tallies their labels. With weighted=True each neighbor's vote is $1/d$, so closer neighbors count more (the floor handles $d = 0$, an exact duplicate).

def knn_predict(X_train, y_train, q, k=3, metric="euclidean", weighted=False):
    d = distances(X_train, q, metric)
    nearest = np.argsort(d, kind="stable")[:k]      # indices of the k smallest
    votes = Counter()
    for i in nearest:
        votes[y_train[i]] += 1 / max(d[i], 1e-12) if weighted else 1
    return votes.most_common(1)[0][0], nearest

Predict: with $K$ equal to the number of training rows and weighted=False, what does this function return for every query?

The curse of dimensionality, measured. Draw 1,000 random points in a unit cube and one random query, then compare the nearest distance to the farthest. In 2 dimensions the nearest point is far closer than the farthest; as dimensions grow, the ratio climbs toward 1 and "nearest" stops meaning much.

rng = np.random.default_rng(0)
print("\ndims  nearest/farthest distance from a random query (uniform cube, 1000 points)")
for p in (2, 10, 100, 1000):
    pts = rng.uniform(size=(1000, p))
    d = distances(pts, rng.uniform(size=p))
    print(f"{p:5d}  {d.min() / d.max():.3f}")

Predict: roughly what ratio do you expect at 1,000 dimensions: 0.1, 0.5, or 0.9?

Use the library

scikit-learn's KNeighborsClassifier does the same search (with a KD-tree or ball tree when that is faster than brute force). Put the scaler in a pipeline so every cross-validation fold computes $\mu$ and $\sigma$ from its own training portion:

from sklearn.model_selection import GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

pipe = make_pipeline(StandardScaler(), KNeighborsClassifier())
search = GridSearchCV(pipe, {"kneighborsclassifier__n_neighbors": [1, 3, 5, 9, 15, 25]}, cv=5)
search.fit(X_train, y_train)          # scaler is refit inside every CV fold: no leakage
print(search.best_params_, search.best_score_)

The script trains both versions on the same synthetic split (K = 15, standardized) and checks that they agree.

Run it

From guide/:

uv run code/05-instance-and-probabilistic/knn_scratch.py

Key output:

raw units:     nearest ['E', 'B', 'A'] -> predict 0
standardized:  nearest ['E', 'D', 'B'] -> predict 1

dims  nearest/farthest distance from a random query (uniform cube, 1000 points)
    2  0.007
   10  0.223
  100  0.720
 1000  0.898

scratch vs scikit-learn on 60 test rows: agree on 100%, test accuracy 0.817

The first two lines reproduce the worked example: same data, same K, opposite prediction after scaling. The separate script code/05-instance-and-probabilistic/knn.py prints the worked example's distances step by step, the cross-validated raw versus standardized comparison, and draws the figure in section 2.

5. Engineering

Good use cases. Small to medium datasets with a meaningful distance; quick baselines; recommendation ("users like you"); anomaly scoring (distance to the k-th neighbor); and, at large scale, semantic search over embeddings.

Choosing K. Use cross-validation. Small K means low bias and high variance; large K means the reverse. With two classes, odd K avoids ties. weights="distance" lets closer neighbors count more.

Preprocessing. Standardize numeric features (or use a metric that suits the data, such as cosine for text embeddings). One-hot categorical features and think about how much each should count. Impute missing values; distances cannot use NaN.

Cost. Training is $O(1)$: store the data. A brute-force prediction costs $O(np)$ per query, since it measures the distance to all $n$ examples in $p$ dimensions. Memory holds the whole training set. KD-trees and ball trees speed this up in low dimensions. For millions of high-dimensional vectors, production systems use approximate nearest neighbor indexes (HNSW, IVF, product quantization) that trade a little recall for orders of magnitude in speed.

The curse of dimensionality. As dimensions grow, the distances between random points concentrate: the nearest and farthest neighbors end up almost equally far away, so "nearest" stops meaning "similar." KNN on hundreds of raw features usually needs feature selection or a learned lower-dimensional representation (PCA, embeddings).

Watch out

Failure modes. Unscaled features (the model quietly ignores small-range features); irrelevant features adding noise to every distance; class imbalance (the majority class wins votes near the boundary); slow, memory-heavy inference at scale; and data drift, because stored examples go stale.

Common mistakes

• Fitting the scaler on the full dataset before splitting.
• Choosing K by looking at test-set accuracy.
• Using K = 1 and reporting its perfect training accuracy.
• Using Euclidean distance on one-hot or text-count features without thinking about the metric.
• Forgetting that every prediction scans the training set, then being surprised by latency.

6. Knowledge check

Practice exercise. Training points: P1 = (1, 1) label 0, P2 = (2, 3) label 1, P3 = (4, 2) label 1, P4 = (0, 3) label 0. Query (2, 2). Compute Euclidean distances and predict with K = 1 and K = 3.

Implementation challenge. Extend knn_predict to regression (average the neighbors' targets) and to distance weighting (weight $1/d$, handling $d = 0$). Compare uniform and distance-weighted KNN regression on a synthetic $y = \sin(x) + \text{noise}$ dataset with cross-validation.

Summary

• KNN predicts from the K closest stored examples: majority vote for classes, average for numbers.
• K sets the bias-variance trade-off: small K is flexible and noisy, large K is smooth and can underfit.
• Distances are only meaningful if features are on comparable scales; standardize using training statistics.
• Training is free but prediction is $O(np)$ per query, and distances degrade in high dimensions.
• Nearest-neighbor search on embeddings is the core of modern semantic retrieval.

Next: Naive Bayes

Related: K-means · Word embeddings · Model card: KNN

Parts of this lesson are adapted from AI Engineering from Scratch by Rohit Ghumare (MIT license, notice): Norms and Distances, K-Nearest Neighbors and Distances.

Interview angle