K-nearest neighbors

Every other model learns a function. k-nearest neighbors learns nothing — it just memorizes the training set and, when a new point arrives, looks at its k closest neighbors and takes a majority vote. It’s the simplest classifier in ML, and a perfect vehicle for seeing decision boundaries and the bias-variance tradeoff in action.

Store, then vote

There is no training phase. To predict a new point: compute its distance to every training point, take the k nearest, and return their majority class (for regression, their average). That’s it.

The picture below is one prediction: a new point (the ?) and the dashed circle holding its 5 nearest neighbors. Three belong to class A, two to class B — so the vote, and the prediction, is A.

k is the bias-variance dial

The choice of k is the whole game, and it maps directly onto bias and variance:

• Small k (k=1) — the boundary wraps every single point. Zero training error, but it memorizes noise — high variance, overfit, jagged.
• Large k — each prediction averages over many points, smoothing the boundary. Too large and far-away points outvote the locals — high bias, underfit.

You tune k by cross-validation, and an odd k avoids ties in binary classification.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import cross_val_score
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=800, n_features=10, n_informative=5, random_state=0)

print(f"{'k':>3} {'CV accuracy':>12}")
for k in [1, 3, 5, 11, 25, 101]:
    clf = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k))
    print(f"{k:3d} {cross_val_score(clf, X, y, cv=5).mean():12.3f}")

print("\nk=1 overfits; very large k underfits; the best k is in between.")

In one breath

• k-NN is a lazy learner: no training — it stores the data and, at prediction time, finds the k nearest points and takes their majority vote (average for regression).
• k is the bias-variance dial: small k (k=1) wraps every point → overfit / high variance; large k averages too widely → underfit / high bias; tune by cross-validation (an odd k avoids ties).
• It’s pure distance, so you must standardize — an unscaled big-range feature dominates the distance and the rest contribute nothing.
• It breaks in high dimensions (distance concentration — the curse), where “nearest” stops being meaningful.
• A great baseline for small, low-dimensional, locally-irregular problems; but prediction is slow (scans all points) and memory-heavy — trees usually win at scale.

Quick check

Next

k-NN votes by distance; Naive Bayes votes by probability — a fast, surprisingly strong probabilistic baseline, especially for text.