k-Nearest Neighbors

The k-nearest-neighbour (kNN) classifier is the simplest non-trivial supervised model: to label a new example, look at the $k$ training points closest to it in feature space, take a majority vote over their labels, and return the winner. There is no parameter to fit, no cost function to minimise, no gradient to take — the "training" step is just storing the data, and every prediction is a fresh scan over the stored rows. This lesson builds the algorithm from the bottom up: the two distance metrics (Euclidean and Manhattan), the bias-variance knob hidden inside the choice of $k$, the lazy-learning paradigm and its $O(n)$ prediction cost, the curse of dimensionality that kills the model as features pile up, the mandatory feature-scaling step that keeps it sane, a comparison table against the decision tree from the previous lesson, and a worked scikit-learn implementation.

Learning Objectives

1. Compute Euclidean and Manhattan distances between two points in $d$-dimensional feature space, and explain the geometric intuition that separates the two metrics and the data shapes for which each one wins.
2. Predict the label of a new example by majority vote over its $k$ nearest neighbours and explain why ties are broken by reducing $k$ to an odd number or by weighting votes.
3. Choose $k$ by reasoning about the bias-variance knob, the $\sqrt{n}$ rule of thumb, and cross-validated grid search, and explain why too-small $k$ gives high variance while too-large $k$ collapses to the class prior.
4. Describe lazy learning as deferred computation with no model artefact at "fit" time, and account for the $O(n)$ prediction cost and the storage requirement that distinguish it from parametric models.
5. Explain the curse of dimensionality with the distance-concentration argument, and explain why kNN degrades as feature count rises even with arbitrarily many training rows.
6. Apply feature scaling (standardisation or min-max) before fitting kNN, and explain with a numeric example why a 0-1000 column dominates a 0-1 column if the features are not rescaled.
7. Distinguish kNN from decision trees along the inductive/deductive, training cost, prediction cost, interpretability, and data-requirement axes, and pick the right one for a given problem.

1. The Nearest-Neighbour Idea

The simplest possible classifier is the 1-nearest-neighbour rule: to label a new point $x$, find the training point nearest to it (in some metric) and copy its label. This is the nearest-neighbour classifier, sometimes attributed to Fix and Hodges (1951). It has no parameters to fit and, remarkably, its asymptotic error rate is at most twice the Bayes error — a proof due to Cover and Hart (1967) — yet the decision boundary it produces is jaggy, sensitive to noise, and prone to memorising single mislabelled rows.

The generalisation to $k$ neighbours is the k-nearest-neighbours classifier: find the $k$ training points closest to $x$, count how many of them belong to each class, and return the majority. With $k > 1$ the rule smooths over the local noise that makes 1-NN brittle.

1.1 The algorithm

def knn_predict(x, X_train, y_train, k, distance_fn):
    # 1. Compute the distance from x to every training point.
    distances = [distance_fn(x, xi) for xi in X_train]

    # 2. Find the indices of the k smallest distances.
    k_idx = argsort(distances)[:k]

    # 3. Majority vote over the labels at those indices.
    votes = Counter(y_train[i] for i in k_idx)
    return votes.most_common(1)[0][0]

Three things matter and three things don't: the metric, the value of $k$, and how ties and distance-weighted votes are handled. The model has nothing else to tune.

1.2 A tiny numeric example

Imagine five training points in two classes (filled = class A, hollow = class B) on a 1D line at positions 1, 2, 3, 10, 12, with labels A, A, B, B, B.

A new point $x = 4$ sits between the two clusters. With $k = 1$, its nearest neighbour is the point at 3 (distance 1, label B), so 1-NN predicts B. With $k = 3$, the three nearest neighbours are at positions 3 (B), 2 (A), and 10 (B) — distances 1, 2, 6 — and the majority vote is B. With $k = 5$, every training point votes, and the result is 2 A's vs 3 B's, still B. As $k$ grows toward $n$, the prediction converges to whatever class has the plurality in the training set — the class prior.

2. Distance Metrics: Euclidean and Manhattan

The distance function is the only piece of geometry in the model. Two metrics dominate in practice.

2.1 Euclidean distance

For two points $x = (x_1, \ldots, x_d)$ and $y = (y_1, \ldots, y_d)$ in $d$-dimensional feature space, the Euclidean (or $\ell_2$) distance is

This is the ordinary straight-line distance: it is what a ruler measures between the two points. The unit "circle" (the set of points at distance 1 from the origin) is a true circle in 2D and a true sphere in higher dimensions.

2.2 Manhattan distance

The Manhattan (or $\ell_1$, or "taxicab") distance is

This is the distance a taxi would drive on a grid of streets, where it can only travel along the axes. The unit "circle" is a rotated square in 2D and a rotated octahedron in higher dimensions.

2.3 When each metric wins

The choice depends on the data shape, not on which one is "more correct".

A useful rule of thumb: if your features are continuous, roughly normally distributed, and measured on a similar scale, Euclidean is the default. If your features are sparse, mixed-unit, or stretched along axes (think: high-dimensional bag-of-words vectors where most entries are zero), Manhattan often wins because its unit ball has corners that touch the axes, making it easier for a sparse point to find a close neighbour.

A worked 2D example makes the geometry concrete. Take $x = (0, 0)$ and $y = (3, 4)$.

• Euclidean: $\sqrt{3^2 + 4^2} = \sqrt{9 + 16} = \sqrt{25} = 5.0$.
• Manhattan: $|3| + |4| = 7.0$.

The Euclidean distance is the hypotenuse of the right triangle with legs 3 and 4; the Manhattan distance is the perimeter of the bounding box measured along its sides. Both satisfy the metric axioms (non-negativity, identity of indiscernibles, symmetry, triangle inequality), but they assign different distances to the same pair of points — and therefore produce different nearest-neighbour sets.

2.4 Minkowski generalisation

Both metrics are special cases of the Minkowski distance

with $p = 2$ giving Euclidean and $p = 1$ giving Manhattan. As $p \to \infty$ the metric converges to the Chebyshev distance $\max_i |x_i - y_i|$, which only cares about the single largest coordinate difference. In practice, kNN rarely needs anything outside $p = 1$ and $p = 2$.

3. Choosing k

The value of $k$ is the bias-variance knob for kNN. It is the only hyperparameter that matters in the simplest formulation.

3.1 Too small — high variance

With $k = 1$, the decision boundary tracks every training point. A single mislabelled row carves out a small island of wrong predictions around itself. Two resamples of the training set produce two completely different boundaries, because every point that disappears from the resample leaves a hole. The classifier has high variance: tiny changes in the data produce big changes in the prediction.

3.2 Too large — predicting the class prior

As $k \to n$, every prediction averages over the entire training set. The classifier ignores the location of $x$ entirely and returns the plurality class of the training set — the class prior. It has high bias: the model has thrown away all the information about where $x$ is.

3.3 The right operating point

The right $k$ lives between those extremes and is usually picked by cross-validation. A common starting heuristic is the square-root rule of thumb:

For $n = 1000$ this suggests $k \approx 32$; for $n = 100{,}000$ it suggests $k \approx 316$. The rule is a rough default — it does not adapt to class imbalance, feature noise, or intrinsic dimensionality — but it gives a sensible search-interval midpoint.

The principled procedure is a grid search over $k \in \{1, 3, 5, 7, \ldots, 2 \sqrt{n} + 1\}$ with 5-fold or 10-fold cross-validation. Two practical tweaks:

• Odd $k$ for binary classification. With $k$ even, ties at 50/50 are common; restricting to odd values removes them. For multiclass classification the issue is rarer but still worth checking.

• Distance-weighted votes. Replace the raw majority vote with

  $$\hat{y}(x) = \arg\max_{c} \sum_{i : y_i = c} \frac{1}{d(x, x_i)},$$

  so that closer neighbours count more. This lets $k$ be larger without the "all votes equal" degeneration.

A validation curve that plots cross-validated accuracy against $k$ has the canonical U-shape: accuracy rises as $k$ moves away from the noisy $k = 1$ extreme, plateaus around the optimal $k$, then falls again as $k$ drifts toward the class prior. The sweet spot is the smallest $k$ in the plateau, because smaller $k$ means a more local decision boundary and lower prediction cost.

4. Lazy Learning: Deferred Computation

kNN is the canonical lazy learner (or instance-based learner): training does nothing more than store the data. There is no parameter vector, no decision tree, no support-vector subset — the "model" is the training set itself.

4.1 No model artefact

When KNeighborsClassifier.fit(X, y) returns, the only state inside the estimator is the array X_train and the label vector y_train. There is nothing to serialise beyond those two arrays. A logistic-regression model fits a weight vector of length $d$; a decision tree fits a tree of $O(n)$ nodes; kNN fits a copy of the data.

This has two consequences.

• Memory cost is $O(n \cdot d)$. For a million-row dataset with a thousand features, the "model" is a billion-float matrix — about 8 GB at 8 bytes per float. kNN scales with the data; parametric models scale with features.
• No abstraction, no generalisation. A logistic regression fitted on $n = 10^6$ rows and a logistic regression fitted on $n = 10^9$ rows produce the same size weight vector. Two kNN classifiers fitted on the same two datasets differ in size by three orders of magnitude.

4.2 $O(n)$ prediction cost

Predicting one label is an $O(n \cdot d)$ operation — compute the distance from the query to every training row, sort, take the top $k$. There is no shortcut without an auxiliary index structure. The exact-data structures that speed up nearest-neighbour search — kd-trees, ball trees, the Approximate Nearest Neighbours (ANN) methods (HNSW, FAISS, Annoy) — exist, but they trade exactness or memory for speed and are configured by a separate set of parameters.

scikit-learn lets you choose the search algorithm:

from sklearn.neighbors import KNeighborsClassifier

clf = KNeighborsClassifier(
    n_neighbors=5,
    algorithm="auto",   # "brute", "kd_tree", "ball_tree", or "auto"
    metric="minkowski", # default Euclidean (p=2)
    p=2,
)

algorithm="auto" picks kd_tree for small $d$, ball_tree for larger $d$, and falls back to the brute-force scan when the data is too large to index efficiently. With algorithm="brute" the cost per prediction is exactly $O(n \cdot d)$ plus the $O(k \log n)$ cost of finding the top $k$.

4.3 Eager vs lazy

The asymmetry is the design point. Eager learners pay at fit time so that prediction is cheap and the model can be served from a small artefact. Lazy learners pay at prediction time, in exchange for being able to absorb new training rows without any retraining — adding a row literally means appending it to X_train.

5. The Curse of Dimensionality

As the number of features $d$ grows, kNN degrades. The reason is not algorithmic; it is geometric. Bellman called this the curse of dimensionality in 1961; for kNN the failure mode is the distance-concentration effect.

5.1 The distance-concentration argument

Suppose you draw $n$ points uniformly at random from the $d$-dimensional unit cube $[0, 1]^d$ and consider the ratio

where $d_{\min}$ and $d_{\max}$ are the distances from a fixed query point to its nearest and farthest neighbour. For low $d$ this ratio is small — the nearest neighbour is much closer than the farthest. For large $d$ the ratio collapses toward zero: the nearest and farthest neighbours are almost the same distance away. The query point cannot distinguish "close" from "far".

A concrete numeric illustration. Pick a query at the origin and 1000 random points in $[0, 1]^d$. The table below shows the mean ratio $R(d)$ over many random draws.

By $d = 100$ the nearest neighbour is on average only 1% closer than the farthest. Every training point is roughly equally relevant; the "nearest neighbours" are not meaningfully nearer than the rest. The classifier behaves like the $k = n$ prior-predicting degenerate.

The asymptotic statement is exact: in the limit $d \to \infty$ with $n$ fixed,

The concentration of distances is a property of high-dimensional space, not of the algorithm.

5.2 What the curse means in practice

Three practical consequences:

1. Exponentially many samples are needed. To keep the nearest-neighbour density constant, $n$ has to grow exponentially in $d$. With 100 points in 1D the nearest neighbour is a useful signal; with 100 points in 100D every point is alone.
2. Irrelevant features add noise. Adding a feature that carries no signal still increases the dimension, dilutes the contribution of signal-carrying features, and worsens the curse. Feature selection matters more for kNN than for almost any other classifier.
3. Euclidean and Manhattan both fail. The argument uses no metric property beyond norm concentration, so switching from $\ell_2$ to $\ell_1$ does not save you. The curse is geometric, not metric-specific.

The standard mitigations are dimensionality reduction (PCA, t-SNE for visualisation, UMAP for compression) and aggressive feature selection before fitting kNN. Both are routinely necessary on real data.

6. Mandatory Feature Scaling

A direct corollary of using distances: kNN requires feature scaling. Without it, a feature measured on a large numeric range dominates the distance and renders every other feature approximately irrelevant.

6.1 The textbook failure mode

Consider two features:

• age_years: range roughly $[0, 100]$.
• income_thousands: range roughly $[0, 1000]$ (in units of thousands of dollars, so the actual range is $[0, 1{,}000{,}000]$).

Without scaling, the squared income term in the Euclidean distance contributes up to $(1000)^2 = 1{,}000{,}000$ per dimension while the age term contributes at most $(100)^2 = 10{,}000$. The age feature is invisible to the distance function; the classifier behaves as if it did not exist.

A numeric example shows it explicitly. Take two query points $x$ and $y$ with

• $x = (30, 50)$, $y = (31, 51)$ — a one-unit difference in age, a one-unit difference in (scaled) income.
• Euclidean distance: $\sqrt{1^2 + 1^2} = \sqrt{2} \approx 1.41$.

Now unscaled:

• $x' = (30, 50{,}000)$, $y' = (31, 51{,}000)$ — same age difference, a one-unit difference in unscaled income.
• Euclidean distance: $\sqrt{1^2 + 1000^2} \approx 1000.0$.

The age feature contributes one ten-thousandth of the distance. Two points that differ by a year of age but the same income are at essentially the same distance as two points that differ by a year of age and 1000 units of income — kNN cannot tell them apart.

6.2 Standardisation and min-max scaling

Two scalings dominate.

Standardisation (z-score):

where $\mu$ and $\sigma$ are the per-feature mean and standard deviation estimated on the training set. After standardisation each feature has mean 0 and standard deviation 1. It is the default in scikit-learn's StandardScaler and is appropriate when the feature distribution is roughly Gaussian.

Min-max scaling (normalisation):

which compresses every feature to $[0, 1]$. It is appropriate when the feature has hard bounds, when the distribution is far from Gaussian, or when the downstream model assumes non-negative inputs.

The scaler is fit on the training set only and then applied to both training and test data. Fitting on the joint data leaks test information into the training step and produces over-optimistic validation scores.

6.3 What scaling does and does not fix

Scaling fixes the units problem: features measured on different scales contribute proportionally. It does not fix the curse of dimensionality. A high-dimensional dataset with all features in $[0, 1]$ still suffers from distance concentration. Scaling is necessary but not sufficient.

7. When kNN Works vs Fails

A clear-eyed list of when to reach for kNN and when to put it back on the shelf.

7.1 kNN works well when

• The training set is small to medium — tens of thousands of rows or fewer. Beyond that, the per-prediction cost becomes a bottleneck.
• The feature space is low-dimensional — fewer than ~20 features, ideally fewer than 10. Anything above that needs aggressive feature selection or dimensionality reduction first.
• Features are continuous and on a similar scale — natural for Euclidean distance.
• The decision boundary is highly irregular — kNN makes no parametric assumption about the shape of the boundary, so it can fit jagged manifolds that logistic regression or a single decision tree would miss.
• You need a non-parametric baseline — kNN with cross-validated $k$ is a strong, defensible baseline against which to compare fancier models. If kNN beats your fancy model on hold-out, the fancy model is not earning its complexity.

7.2 kNN fails when

• The feature space is high-dimensional — the curse of dimensionality kicks in, nearest-neighbour distances concentrate, and the model collapses toward the class prior.
• Features are on wildly different scales — without scaling, the largest-range feature dominates. With scaling, you may not need kNN.
• The training set is large — both memory and per-prediction cost scale linearly in $n$, so kNN becomes a throughput problem at scale.
• The classes are heavily imbalanced — majority vote pushes the prediction toward the majority class; distance-weighted voting helps but does not fix the imbalance.
• Features are categorical with many levels — distances between categorical features are not well-defined, and Hamming distance or one-hot encoding distorts the geometry.
• Interpretability matters — there is no model artefact to read, no feature importance, no decision path. The explanation is "these $k$ training points voted this way".

A useful diagnostic: after fitting kNN, plot the cross-validated accuracy against $k$. If the curve is essentially flat at the class prior level, kNN is not learning anything from the features at the given $d$. The fix is not a better $k$; the fix is fewer features or a different model.

8. kNN vs Decision Trees

The previous lesson built an eager, rule-based learner that asks yes/no questions about features. kNN is its lazy, geometry-based counterpart. The two algorithms occupy opposite corners of the design space, and the trade-offs between them are instructive.

The two axes most worth weighing are cost at prediction time and interpretability. A decision tree is the right pick when predictions will be made millions of times (the $O(\log n)$ cost dominates the $O(n)$ cost of kNN at scale) or when the model itself has to be defensible to a stakeholder. kNN is the right pick when $n$ is small, $d$ is low, the boundary is irregular, and you want a strong non-parametric baseline before reaching for something heavier.

A subtle point: a decision tree with no pruning is a 1-nearest-neighbour memoriser with one neighbour per leaf — it carves the feature space into $n$ tiny rectangles and labels each by the training point inside it. That is why an unconstrained tree overfits dramatically (Section 5 of the previous lesson); the cure is the same as for kNN — a smoothing hyperparameter (max_depth for the tree, $k$ for kNN) that prevents the model from memorising individual rows.

9. Implementation in scikit-learn

The full kNN pipeline in scikit-learn is short.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

#Load iris (150 rows, 4 features, 3 classes).
X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(
    X, y, test_size=0.25, random_state=0, stratify=y
)

#Scaling is mandatory for kNN — wrap it into a Pipeline so the scaler is
#fit on the training fold only, never on the test data.
pipe = Pipeline([
    ("scale", StandardScaler()),
    ("knn",   KNeighborsClassifier(n_neighbors=5, metric="minkowski", p=2)),
]).fit(X_tr, y_tr)

print(f"train accuracy: {pipe.score(X_tr, y_tr):.3f}")
print(f"test  accuracy: {pipe.score(X_te, y_te):.3f}")

Typical output (exact numbers depend on the split):

train accuracy: 0.964
test  accuracy: 0.947

The Pipeline enforces the right scaling discipline: StandardScaler.fit runs on the training data inside the cross-validation split, never on the test data, so the reported accuracy is honest.

A second snippet cross-validates over $k$ to pick the best value:

from sklearn.model_selection import GridSearchCV

grid = GridSearchCV(
    estimator=pipe,
    param_grid={"knn__n_neighbors": [1, 3, 5, 7, 11, 15, 21, 31]},
    cv=5,
    scoring="accuracy",
    n_jobs=-1,
).fit(X_tr, y_tr)

print(f"best k: {grid.best_params_['knn__n_neighbors']}")
print(f"best CV accuracy: {grid.best_score_:.3f}")

For iris the chosen $k$ is usually 5 or 7; both the $\sqrt{n}$ rule-of-thumb ($k \approx 12$ for $n = 112$) and the plateau from the validation curve point in the same direction.

A third snippet shows distance-weighted voting:

pipe_weighted = Pipeline([
    ("scale", StandardScaler()),
    ("knn",   KNeighborsClassifier(
        n_neighbors=15,        # larger k is fine with weights
        weights="distance",    # closer neighbours count more
        metric="minkowski", p=2,
    )),
]).fit(X_tr, y_tr)

With weights="distance", every neighbour's vote is divided by its distance to the query; very close neighbours dominate and far-away neighbours contribute almost nothing. This lets you use a larger $k$ without the "all votes equal" degeneration.

A final snippet illustrates what happens when you skip scaling:

from sklearn.preprocessing import StandardScaler
import numpy as np

#Add a feature on a 1000x larger scale than the others.
X_te_bad = X_te.copy()
X_tr_bad = X_tr.copy()
X_tr_bad[:, 0] *= 1000
X_te_bad[:, 0] *= 1000

pipe_bad = Pipeline([
    ("knn", KNeighborsClassifier(n_neighbors=5)),
]).fit(X_tr_bad, y_tr)

print(f"without scaling: {pipe_bad.score(X_te_bad, y_te):.3f}")

The accuracy here drops noticeably (the exact number depends on the random split, but the drop is consistent) because the first feature dominates every distance calculation. Wrapping the same kNN in a Pipeline with StandardScaler recovers the original accuracy.

These four snippets — fit-and-score, cross-validate over $k$, distance weighting, and the scaling-matters warning — are the complete kNN template for any tabular dataset.

Key Takeaways

• kNN labels a new point by majority vote over its $k$ nearest neighbours; the model is the training set, and there is nothing to fit. The two ingredients are the distance metric (Euclidean $\ell_2$ or Manhattan $\ell_1$, both special cases of the Minkowski $d_p$) and the value of $k$.
• Euclidean distance is the straight-line ruler distance; Manhattan is the grid-aligned taxi distance. Euclidean is the default for continuous, similarly-scaled features; Manhattan often wins for sparse or mixed-unit data because its unit ball has axis-aligned corners.
• $k$ is the bias-variance knob: $k = 1$ gives high variance and noisy boundaries; $k \to n$ collapses to the class prior. The $\sqrt{n}$ rule of thumb gives a starting point; cross-validation picks the operating point, and distance-weighted votes let a larger $k$ keep useful locality.
• kNN is the canonical lazy learner: training is $O(1)$, every prediction is $O(n \cdot d)$ brute-force, and the "model artefact" is the dataset itself. Memory and prediction cost scale with $n$, not with $d$, which is the opposite of a parametric model.
• The curse of dimensionality degrades kNN as features accumulate. Distance concentration makes the nearest and farthest neighbour almost equidistant in high $d$, the classifier behaves like a prior-predicting constant, and the only fixes are fewer features (selection) or lower-dimensional representations (PCA, etc.) — switching metric does not help.
• Feature scaling is mandatory. A feature on a 0-1000 range dominates a feature on a 0-1 range; without StandardScaler or MinMaxScaler fit on the training fold only, every other feature becomes invisible to the distance function.
• kNN vs decision tree is lazy-vs-eager, $O(n)$ vs $O(\log n)$ per prediction, no artefact vs interpretable rules, scale-sensitive vs scale-invariant. kNN is the right pick for small $n$, low $d$, irregular boundaries, and as a non-parametric baseline; decision trees are the right pick when predictions are made at scale or when the model must be read by a stakeholder.