k-Nearest Neighbors

What this chapter covers

Most classifiers spend a training phase boiling the data down to a few parameters, then throw the data away. k-nearest neighbors refuses. It keeps every training point and, to label something new, just looks at what sits closest and copies the local majority. There is no model to fit — the training set is the model. That makes it the most literal machine learning there is: "things near each other tend to be alike," turned into code.

We build it by hand in NumPy, one function at a time — a distance, a sort, a vote — then let scikit-learn build the same thing and check the numbers line up. Along the way you get to watch it decide: for each test flower we circle its k nearest neighbors, draw the votes, and color the point by whichever class wins. You'll see exactly where it's confident and exactly where it guesses, because the two look different on screen.

The data is Iris — 150 flowers, three species, and we keep two measurements (petal length and petal width) so the whole thing lives on a plane you can actually see.

A bit of history

The idea is old and the proof is famous. In 1951 Evelyn Fix and Joseph Hodges, working on a technical report for the US Air Force School of Aviation Medicine, wrote down nonparametric discrimination by nearest neighbors — no assumed distribution, just distances. It sat mostly unread for years. Then in 1967 Thomas Cover and Peter Hart published "Nearest Neighbor Pattern Classification" in the IEEE Transactions on Information Theory and gave it the result that made people pay attention: as the training set grows without bound, the error rate of the single nearest neighbor is never worse than twice the Bayes error — the best any classifier could possibly do. One neighbor, no training, and you're already within a factor of two of optimal. That's a startling thing to be able to prove about a rule this simple.

What kept kNN from being just a theoretical curiosity is that it never went away. It's the workhorse behind recommendation ("users like you also bought"), the baseline in every image-retrieval paper, and the honest reference point for anything that claims to have learned structure. Modern vector databases — the ones holding the embeddings behind semantic search and retrieval-augmented generation — are, underneath the marketing, fast nearest-neighbor search over millions of points. The algorithm Fix and Hodges sketched in 1951 is running in production right now, just with a better index.

The intuition

Look at the two petal measurements plotted against each other, one dot per flower, colored by species. Setosa sits off by itself in the bottom-left corner — small petals, no argument. Versicolor and virginica are stacked in the upper right and they bleed into each other along a fuzzy seam. That seam is the whole story of this dataset.

Now imagine dropping a new, unlabeled flower onto that plane. Where does it land? If it lands deep in the cyan cloud, everything around it is setosa and the call is obvious. If it lands in the seam where purple and orange overlap, its neighbors disagree, and the label you give it depends on which ones happen to be closest. That's kNN in one picture: find the k closest points, take a vote. No line, no equation of a boundary — the boundary is wherever the votes happen to flip, and it bends around the data as tightly or as loosely as k lets it.

The math

Give each training flower a feature vector $x_i \in \mathbb{R}^{D}$ and a label $y_i$. Here $D = 2$ and $y_i$ is one of three species. To classify a query point $q$, first measure how far it is from every training point. The default metric is plain Euclidean distance:

Sort those $N$ distances and take the $k$ smallest. Call that set of indices $N_k(q)$ — the k nearest neighbors. The prediction is the label that appears most often among them:

The inner sum counts how many of the k neighbors carry class $c$; the $\arg\max$ keeps the class with the most votes. That's the entire algorithm. There is no parameter estimated from data anywhere in those two lines — the only thing you choose is $k$, and $k$ is a knob you set, not something the data hands you. Small $k$ trusts the single closest points and follows every wiggle; large $k$ averages over a wider crowd and smooths the boundary out.

One detail the formula hides: when two classes tie, you need a rule to break it. We sort the class labels and keep the smallest, which is arbitrary but fixed — the same query always resolves the same way. Odd values of $k$ avoid ties in the two-class case for exactly this reason.

What it's good at, what it isn't

The appeal is that there's nothing to fit. No training loop, no loss, no convergence to babysit — you load the data and you can predict. The decision surface can be any shape at all, because it's stitched together locally from whatever points are around, so kNN handles curved, blobby, non-linear boundaries that a single straight cut can't touch. And it's an honest baseline for the same reason the threshold was: if your elaborate model can't beat "copy the nearest few," the elaborate model isn't earning its complexity.

The costs are equally blunt. It does no work at fit time and all of it at predict time — every single prediction scans the whole training set, so a model that was instant to "train" is slow to use, and it gets slower the more data you feed it. It has to hold all that data in memory, forever. It's sensitive to feature scale: distance sums over dimensions, so a feature measured in thousands drowns out one measured in tenths unless you standardize first. And it rots in high dimensions — the curse of dimensionality — because when you have hundreds of features every point is roughly equidistant from every other, "nearest" stops meaning anything, and the vote is noise. kNN is wonderful in two dimensions and treacherous in two hundred.

The data

Iris is the "hello world" of classification, and for once the cliché earns it — it's small, clean, and the structure is visible to the naked eye. Edgar Anderson measured the flowers; Ronald Fisher used them in his 1936 discriminant-analysis paper, which is why you'll also see it called Fisher's Iris. Three species, fifty flowers each, four measurements per flower. We drop two of the measurements and keep petal length and petal width, because those two carry almost all the separating signal and, more to the point, two features fit on a screen. The scatter above is the whole dataset — there's nothing hidden in a third dimension we're not showing you.

The catch that matters later: versicolor and virginica genuinely collide. A handful of flowers from the two species share the exact same petal length and petal width down to the recorded precision. No classifier can pull those apart on these two features — the information simply isn't there — so there's a ceiling below 100% baked into the data, and kNN bumps into it right where you'd expect, in the seam.

Build it, one function at a time

Six short functions, and the first three are the whole algorithm. This is the order I'd write it at a terminal: the distance first, because everything hangs off it.

Start with the distance from one query point to every training point at once. The subtraction broadcasts the query across all rows, so there's no loop — one expression returns all N distances:

def euclidean(X, q):
    """Straight-line distance from a query point q to every row of X.

    X is (N, D) — N training points in D dimensions. q is (D,). The
    subtraction broadcasts q across all N rows, so one call gives back all N
    distances at once, no loop.
    """
    return np.sqrt(((X - q) ** 2).sum(axis=1))     # shape (N,)

With distances in hand, "find the neighbors" is a sort. argsort orders every training point by how close it is; we keep the first k indices. This is where kNN spends its entire compute budget, and it's why prediction is the expensive half:

def k_nearest(X, q, k):
    """Indices of the k training points closest to q, nearest first.

    argsort orders every point by distance; we keep the first k. That's the
    whole "search" — kNN spends all its effort here, at predict time.
    """
    d = euclidean(X, q)
    return np.argsort(d)[:k]

Then the vote. Count the labels among those k neighbors and return the most common one. np.unique hands the labels back in sorted order, so taking the argmax of the counts breaks ties toward the smaller label — a fixed rule rather than an accident of ordering:

def majority_vote(labels):
    """The label that appears most among the neighbors.

    np.unique returns the labels in sorted order, so argmax on the counts
    breaks ties toward the smaller label — a fixed, reproducible rule rather
    than whatever order the neighbors happened to arrive in.
    """
    vals, counts = np.unique(labels, return_counts=True)
    return vals[np.argmax(counts)]

Those three compose into a prediction for a single point: nearest neighbors, then vote.

def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])

To label a whole test set you just run that per point. kNN has no shared work to amortize across queries — each one is an independent search — so this is honestly a loop, and no amount of cleverness changes that:

def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])

Last piece, the same accuracy we've used all along: what fraction of predictions match the truth.

def accuracy(y_true, y_pred):
    """Fraction of predictions that match the truth."""
    return float((np.asarray(y_true) == np.asarray(y_pred)).mean())

Watch it work

This is the part worth slowing down for. We take the held-out test flowers one at a time and let the classifier do its thing in the open. The faint dots are the 105 training flowers, colored by their true species. For each query we circle it, draw a dashed ring whose radius reaches exactly to the fifth-nearest neighbor, connect the query to each of its five neighbors, and then color the query by whichever species wins the vote. If the vote is wrong, the point gets a red ring. The caption reads out the tally.

Press play and watch the query sweep from left to right across the plane.

The first few queries land deep in setosa and virginica territory and the vote is unanimous — five for one class, a tight little circle, nothing to argue about. Then the query walks into the seam between versicolor and virginica and the whole character changes. The circle stays small but the five neighbors inside it stop agreeing: four to one, then three to two. Three of these contested points get a red ring, and if you read their tallies they're all the same kind of mistake — a flower sitting on the wrong side of a boundary that doesn't really exist, because the two species overlap there. That's not a bug in kNN. That's kNN faithfully reporting that the data is ambiguous exactly where the data is ambiguous.

Now the knob. Here's test accuracy and training accuracy as k grows from 1 to 25. The two curves are close and both are flat, which is itself the lesson: when the classes are this well separated, k barely matters — you can average over one neighbor or fifteen and get essentially the same answer.

Look at the left edge. At k = 1 the training accuracy isn't a perfect 1.0 — it sits at 0.991 — and that's not a rounding quirk. A training point's own nearest neighbor should be itself, at distance zero, which would make training accuracy exactly one. The gap is that collision I warned about: a versicolor and a virginica sit on the identical petal coordinates, so one of them finds a zero-distance neighbor of the wrong class and votes itself wrong. The data caps you below perfection even on the points you trained on. On a messier dataset this chart would tell the usual story — k = 1 memorizes and overfits, larger k smooths and generalizes — but Iris is too clean to dramatize it, and pretending otherwise would be dishonest.

To actually see k smoothing, look at the decision surface instead of the accuracy. Here's the map of what the classifier predicts at every point on the plane, at k = 1. Every training point rules a little territory of its own, so the boundary is jagged and there are stray islands where one outlier stamps its class onto the surrounding area:

Now the same surface at k = 15. Averaging over fifteen neighbors erases the islands, straightens the seam, and leaves three clean regions. This is the picture the flat accuracy curve couldn't show you — k didn't change the score much, but it changed the shape of the decision a lot, and on noisier data that shape is the difference between a model that generalizes and one that memorizes:

The full implementation

The whole classifier, no library, top to bottom. This is the file the animation above actually ran:

"""k-Nearest Neighbors, built from scratch.

To label a new point, look at the k training points closest to it and let
them vote. There is no training step at all — the "model" is the training set
itself, kept around and searched at predict time. Pure NumPy, no ML library
anywhere in this file.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: euclidean
def euclidean(X, q):
    """Straight-line distance from a query point q to every row of X.

    X is (N, D) — N training points in D dimensions. q is (D,). The
    subtraction broadcasts q across all N rows, so one call gives back all N
    distances at once, no loop.
    """
    return np.sqrt(((X - q) ** 2).sum(axis=1))     # shape (N,)
# endregion


# region: k_nearest
def k_nearest(X, q, k):
    """Indices of the k training points closest to q, nearest first.

    argsort orders every point by distance; we keep the first k. That's the
    whole "search" — kNN spends all its effort here, at predict time.
    """
    d = euclidean(X, q)
    return np.argsort(d)[:k]
# endregion


# region: majority_vote
def majority_vote(labels):
    """The label that appears most among the neighbors.

    np.unique returns the labels in sorted order, so argmax on the counts
    breaks ties toward the smaller label — a fixed, reproducible rule rather
    than whatever order the neighbors happened to arrive in.
    """
    vals, counts = np.unique(labels, return_counts=True)
    return vals[np.argmax(counts)]
# endregion


# region: knn_predict_one
def knn_predict_one(X, y, q, k):
    """Predict q's label: find its k nearest neighbors, let them vote."""
    idx = k_nearest(X, q, k)
    return majority_vote(y[idx])
# endregion


# region: knn_predict
def knn_predict(X, y, Q, k):
    """Predict a label for every query row in Q by running the vote per point.

    X, y are the training set; Q is (M, D) of points to classify. kNN has no
    shared work to amortize across queries, so this is honestly just a loop.
    """
    return np.array([knn_predict_one(X, y, q, k) for q in Q])
# endregion


# region: accuracy
def accuracy(y_true, y_pred):
    """Fraction of predictions that match the truth."""
    return float((np.asarray(y_true) == np.asarray(y_pred)).mean())
# endregion


def load_data(path="../data/iris2d.csv"):
    """Iris, reduced to two features: petal length and petal width.

    Returns (X, y, names): X is (N, 2) float, y is (N,) int class ids
    0/1/2, names maps id -> class name.
    """
    df = pd.read_csv(path)
    X = df[["petal_length", "petal_width"]].to_numpy(float)
    y = df["class_id"].to_numpy(int)
    names = dict(sorted(df[["class_id", "class"]].drop_duplicates().itertuples(index=False)))
    return X, y, names

The library version

Nobody hand-rolls the neighbor search in production, and once you understand it you shouldn't either. scikit-learn's KNeighborsClassifier is the same algorithm — distance, k nearest, majority vote — with the defaults set to match what we built: uniform (unweighted) votes and the plain Euclidean metric. Fitting it just stores the training set:

def knn_sklearn(X_train, y_train, X_test, k):
    """Fit a k-NN classifier and predict the test points. Returns predictions.

    n_neighbors is our k. The defaults match our scratch version: uniform
    (unweighted) votes and the plain Euclidean metric.
    """
    clf = KNeighborsClassifier(n_neighbors=k)
    clf.fit(X_train, y_train)
    return clf.predict(X_test)

The one thing it does that our version doesn't is the search itself. Our k_nearest sorts all N distances on every query, which is fine for 105 flowers and hopeless for a million. sklearn quietly builds a spatial index — a KD-tree or ball tree — at fit time, so it can find the k nearest without looking at every point. Same answer, dramatically better scaling, and it's the reason the "fit" step exists at all in a library where fit does no learning.

Sweeping k to draw a curve is the same idea, once per value:

def knn_curve_sklearn(X_train, y_train, X_test, y_test, ks):
    """Test accuracy for each k in ks — the library's version of the curve."""
    out = []
    for k in ks:
        clf = KNeighborsClassifier(n_neighbors=k)
        clf.fit(X_train, y_train)
        out.append(float(clf.score(X_test, y_test)))
    return out

Scratch versus library

Split the 150 flowers into 105 for training and 45 held out, fit both versions at k = 5, and score them on the held-out set:

Both land on 0.9333 — identical, not close, identical: all 45 test predictions agree flower for flower. That's the result you want, and with kNN it's almost guaranteed, because there's no random initialization, no optimizer, nothing to diverge. Given the same data, the same k, and the same tie-break, the vote is the vote. The three flowers we miss are the three sitting in the versicolor– virginica overlap, and no setting of k fixes them, because the ceiling is in the data, not the model.

Two honest notes on that 0.9333. First, it's a small test set — 45 flowers, so each mistake is worth about two points and you shouldn't read the third decimal as gospel; a different split lands anywhere from about 0.91 to 0.96, which is the real range for this problem. Second, setosa is free money. It's perfectly separated, so a third of the test set is trivially correct and props the number up; all the actual difficulty lives in the other two classes. The number the face-off produces lives in results.json, regenerated whenever the code changes, so the prose and the picture can't drift from what the code did.

Takeaways

Reach for kNN when you want a strong baseline with zero training ceremony, your data is low-dimensional, and you can afford to be slow at predict time. It is genuinely hard to beat on small, well-scaled, low-dimensional problems, and it'll tell you fast whether there's any local structure worth modeling at all — if copying the nearest few already scores well, your classes cluster, and that's worth knowing before you reach for anything heavier.

Walk away from it when any of three things is true, and one of them almost always is. When you have lots of features, distances stop discriminating and the whole method quietly stops working — that's the curse of dimensionality, and it's the reason kNN is a two-dimensional hero and a two-hundred-dimensional liability. When you have lots of rows, the no-training-all-prediction bargain turns against you: every query scans everything, and "instant to train" becomes "too slow to serve." And when your features live on wildly different scales, the distance is a lie until you standardize — which is exactly why the next stretch of this course is about scaling features and choosing them well, because kNN is the algorithm that punishes you hardest for skipping that work. Two things it still hands you for free are worth keeping: it never assumes a shape for the boundary, and its errors point straight at where your classes actually overlap. That's not a bad thing to have in your pocket, even in the age of billion-vector indexes that are, underneath, this exact idea.