17 · K-Nearest Neighbors classification
The laziest algorithm — it memorises training data, then classifies new points by voting among their k nearest neighbors.
KNN is the laziest algorithm — it 'trains' instantly by memorizing all the data, then classifies a new point by voting among its k nearest neighbors.
Without this:
Without KNN you'd miss the canonical instance-based learner and the simplest possible non-linear classifier.
Every model we have seen so far — linear regression, logistic regression, SVM, Naive Bayes — fits a compact set of parameters during training. At inference time, only those parameters matter; the original data can be discarded.
K-Nearest Neighbors (KNN) throws that idea away. There is no explicit training step: the algorithm simply memorises the entire training set. To classify a new point x:
- Compute the distance from x to every training point.
- Find the K nearest training points (the "neighborhood").
- Let them vote: the majority class wins.
This is called lazy learning — all the work happens at prediction time, not training time.
Distance metrics
The vote is only meaningful if "nearest" is well-defined. Common choices:
- Euclidean (L2): d(x, y) = √Σ(xᵢ − yᵢ)² — the default. Assumes all features are on the same scale and the space is isotropic.
- Manhattan (L1): d(x, y) = Σ|xᵢ − yᵢ| — more robust to outliers in individual features; prefer for sparse data.
- Cosine: d(x, y) = 1 − (x · y)/(||x|| ||y||) — measures angle, not magnitude; popular for text embeddings.
The role of K
k = 1 : Each new point is assigned the class of its single nearest neighbor. The boundary is maximally flexible — every training point creates its own "island." High variance, low bias.
k = n (all samples) : Every new point gets the global majority class. Totally flat boundary. Zero variance, very high bias.
As k increases, the decision boundary smooths out. The optimal k is found by cross-validation.
The scaling imperative
Distance is physically meaningful only when features share a common scale. A feature measured in dollars (range 0–100 000) will completely swamp a feature measured in kilograms (range 0–200). Always apply StandardScaler before KNN.
Computational note: lazy ≠ free
Training: O(1) — just store the data. Prediction for one query: O(n·d) — scan all n training points. For large n, this becomes prohibitively slow. The next lesson introduces tree-based acceleration.
Python (in browser)
KNN (k=5) produces a smooth Voronoi-like boundary that perfectly follows the moon shapes — something a linear model could never achieve. The boundary smoothness is controlled entirely by k. Notice that `StandardScaler` was applied first — without it, the distance calculation would be meaningless if the two features had different ranges.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
As k increases, the boundary smooths monotonically — high k = high bias. k=1 memorizes the training data perfectly (100% training accuracy) but will generalize poorly. k=5 and k=25 show the practical sweet spot for this dataset. k=99 (about half the data) is almost fully smoothed out — ignoring the non-linear structure entirely.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Always tune k via cross-validation, not by evaluating on the test set. The `Pipeline` wrapping is critical: fitting the `StandardScaler` inside each fold prevents the validation fold's distribution from leaking into the scaler's fit, which would inflate CV scores. `n_jobs=-1` parallelises the grid search across available cores.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
On low-dimensional, well-scaled continuous data the distance metric rarely changes accuracy dramatically. The real difference emerges in high-dimensional or domain-specific settings: Euclidean for images, Manhattan for tabular data with outliers, Cosine for TF-IDF text vectors (KNN text classifiers almost always use cosine). `metric='minkowski'` with `p=2` is Euclidean; `p=1` is Manhattan.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
The curse of dimensionality is the single biggest reason KNN fails in production ML — features from real datasets are almost always correlated, redundant, or scale-mismatched in ways that pollute Euclidean distances. Always apply dimensionality reduction before deploying KNN on high-dimensional data.
Why must you scale features before KNN?
- KNN memorizes training data; prediction finds the K nearest neighbors by distance and returns the majority vote. Training is O(1), prediction is O(n·d).
- Small k = high variance (wiggly boundary); large k = high bias (flat boundary). Pick k by cross-validation, always inside a Pipeline with StandardScaler.
- Always StandardScaler before KNN — large-range features dominate Euclidean distance and render the neighborhood meaningless.
- KNN degrades in high dimensions (curse of dimensionality) — the concept of 'nearest neighbor' loses meaning above ~50 features. Apply PCA first.
Recommendation systems (find similar users/items); image retrieval; outlier scoring; quick prototype classifier before committing to a more complex model.
If you remove it: You'd lose the simplest non-parametric classifier and the conceptual base of similarity-based methods.