K-Nearest NeighborsOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

K-Nearest Neighbors (KNN)

KNN is the simplest machine learning algorithm: no training at all. To classify a new point, just find the kk closest training examples and take a majority vote. In project-loop terms it is a pure hypothesis-space choice — a non-parametric model family whose only dial, kk, trades capacity against smoothness (the bias–variance story of lesson 03).

Deep dive
The ML Project Loop
Includes runnable notebook

Real-world examples: Recommendation systems (users similar to you also liked...), anomaly detection (points far from any cluster are suspicious), handwritten digit recognition.

The algorithm

  1. Choose kk (the number of neighbors)
  2. Compute the distance from the new point to every training point
  3. Find the kk nearest points
  4. Return the most common label among them

For regression, return the average of the kk neighbors' values instead of the majority vote.

Intuition

Imagine you move to a new city and want to know if a neighborhood is safe. You ask the 5 closest neighbors — if 4 say "safe" and 1 says "dangerous", you'd probably feel safe. That's KNN with k=5k=5.

Worked example

Training data:

PointFeatures (x1,x2x_1, x_2)Label
A(1, 2)Red
B(2, 3)Red
C(6, 5)Blue
D(7, 7)Blue
E(8, 6)Blue

We want to classify the new query point xnew=(3,4)\mathbf{x}_{\text{new}} = (3, 4).

Step 1: compute the Euclidean distance to every training point. For each point we take the gap in x1x_1, the gap in x2x_2, square both, add, and square-root:

d(A)=(3−1)2+(4−2)2=4+4=8≈2.83d(B)=(3−2)2+(4−3)2=1+1=2≈1.41d(C)=(3−6)2+(4−5)2=9+1=10≈3.16d(D)=(3−7)2+(4−7)2=16+9=25=5.00d(E)=(3−8)2+(4−6)2=25+4=29≈5.39\begin{aligned} d(A) &= \sqrt{(3-1)^2 + (4-2)^2} = \sqrt{4 + 4} = \sqrt{8} \approx 2.83 \\ d(B) &= \sqrt{(3-2)^2 + (4-3)^2} = \sqrt{1 + 1} = \sqrt{2} \approx 1.41 \\ d(C) &= \sqrt{(3-6)^2 + (4-5)^2} = \sqrt{9 + 1} = \sqrt{10} \approx 3.16 \\ d(D) &= \sqrt{(3-7)^2 + (4-7)^2} = \sqrt{16 + 9} = \sqrt{25} = 5.00 \\ d(E) &= \sqrt{(3-8)^2 + (4-6)^2} = \sqrt{25 + 4} = \sqrt{29} \approx 5.39 \end{aligned}

Step 2 — sort by distance (nearest first):

RankPointDistanceLabel
1B1.41Red
2A2.83Red
3C3.16Blue
4D5.00Blue
5E5.39Blue

Step 3: keep the kk nearest and vote. With k=3k=3, the neighbors are B (Red), A (Red), C (Blue).

votes={Red:2, Blue:1}  ⇒  predict Red\text{votes} = \{\text{Red}: 2,\ \text{Blue}: 1\} \;\Rightarrow\; \boxed{\text{predict Red}}

This is the exact query point and result reproduced in the companion notebook. Notice that the answer can flip with kk: at k=5k=5 the votes become {Red:2, Blue:3}\{\text{Red}: 2,\ \text{Blue}: 3\}, so the prediction would change to Blue. The choice of kk is not a detail. It can decide the class.

Python
import numpy as np

# Training data
X_train = np.array([[1,2], [2,3], [6,5], [7,7], [8,6]])
y_train = np.array(['Red', 'Red', 'Blue', 'Blue', 'Blue'])

def knn_predict(X_train, y_train, x_new, k=3):
    distances = np.sqrt(np.sum((X_train - x_new)**2, axis=1))
    k_nearest = np.argsort(distances)[:k]
    labels = y_train[k_nearest]
    # Majority vote
    values, counts = np.unique(labels, return_counts=True)
    return values[np.argmax(counts)]

print(knn_predict(X_train, y_train, np.array([3, 4]), k=3))  # 'Red'

Distance metrics

Everything in KNN depends on the word "close." The Euclidean distance (∑i(xi−yi)2\sqrt{\sum_i(x_i-y_i)^2}) is the default for continuous features. The Manhattan distance (∑i∣xi−yi∣\sum_i|x_i-y_i|) works better for high-dimensional sparse data. Both are special cases of the Minkowski distance dp(x,y)=(∑i∣xi−yi∣p)1/pd_p(\mathbf{x},\mathbf{y}) = (\sum_i|x_i-y_i|^p)^{1/p}, which also covers Chebyshev (p→∞p\to\infty) and Hamming for categorical features.

Deep dive
Minkowski Distance Family
Includes runnable notebook

Feature scaling is critical

KNN uses distances, so features with larger ranges dominate. A feature measured in millimeters (range 0-10000) will completely overwhelm one measured in meters (range 0-10). Always normalize or standardize features before applying KNN.

Python
# The idiom (for your own X_train / X_test):
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)   # fit on training data only
X_test_scaled = scaler.transform(X_test)         # reuse the SAME scaler — never refit

Choosing k: the bias–variance tradeoff

The hyperparameter kk controls how much you smooth. Think of it as a dial between trusting one neighbor versus averaging a whole crowd.

Small kk (e.g. k=1k=1): low bias, high variance. The prediction copies the single closest point. The model bends around every individual example, so it fits the training data perfectly, but a single mislabeled or noisy point creates its own little island of wrong predictions. Move the query a hair and the answer can flip. The decision boundary is jagged.

Large kk (e.g. k=nk=n): high bias, low variance. Every query averages over a huge neighborhood, so noise washes out and predictions are stable. But the model can no longer represent fine structure: in the extreme k=nk=n it ignores the query entirely and always returns the global majority class. The boundary is over-smoothed and underfits.

We want the kk that minimizes total error = bias² + variance + irreducible noise. As kk grows, variance falls but bias rises, so the test error typically traces a U-shape — too small overfits, too large underfits, and the bottom of the U is the sweet spot.

You don't guess it — you measure it with cross-validation: try a range of kk, score each on held-out folds, and pick the best. A useful starting point is the heuristic k≈nk \approx \sqrt{n}. For binary classification, prefer an odd kk so a two-way vote can never tie.

Python
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score

# Find best k
for k in range(1, 21):
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)
    print(f"k={k:2d}: accuracy={scores.mean():.3f} ± {scores.std():.3f}")

Decision boundaries

KNN creates complex, non-linear decision boundaries. With k=1k=1, the boundary is the Voronoi tessellation of the training points — each region is the set of points closest to one training example.

As kk increases, the boundary becomes smoother. This is the bias-variance tradeoff in action:

kBiasVarianceBoundary
1LowHighVery jagged
n\sqrt{n}MediumMediumBalanced
nnHighLowAlways majority class

k-NN decision boundary

feature x₁feature x₂
k1
fit accuracy100%

Every background cell is labelled by majority vote of its k nearest training points. k=1 fits every point (even noise) with a jagged boundary; larger k averages over neighbours and smooths it.

The curse of dimensionality

KNN's whole premise is that "nearest" means "most similar." In high dimensions that premise quietly breaks. As you add dimensions, all pairwise distances bunch together — the nearest and farthest neighbors become almost equally far away:

dmax⁡−dmin⁡dmin⁡→0as d→∞\frac{d_{\max} - d_{\min}}{d_{\min}} \to 0 \quad \text{as } d \to \infty

Why it happens (worked intuition)

Suppose each coordinate contributes a small, roughly independent squared gap of size ss to the distance. With dd dimensions the squared distance is a sum of dd such gaps, so it grows like d⋅sd \cdot s, and the distance grows like d⋅s\sqrt{d \cdot s}. By the law of large numbers, that sum concentrates tightly around its mean: the spread of distances grows much slower than the distances themselves. So every point ends up sitting at roughly the same distance from every other point.

Concretely, draw 500 random points in the unit cube and measure how far the farthest neighbor is versus the nearest:

Dimension ddTypical dmax⁡/dmin⁡d_{\max} / d_{\min}
2≈ 40–60× (nearest is clearly nearest)
10≈ 3–4×
100≈ 1.5×
1000≈ 1.1× (everything is "equally far")

By d=1000d = 1000 the closest neighbor is only about 10% nearer than the farthest one — the ranking that KNN relies on is almost pure noise. The companion notebook computes this exact ratio. In high dimensions, "nearest" loses meaning. KNN works well in low dimensions (2–10) but degrades rapidly beyond that.

Practical tip: KNN is a great baseline but rarely competitive with trained models on high-dimensional data. It's most useful for: (1) quick prototyping, (2) low-dimensional problems, and (3) as a component in other algorithms.

When to use KNN

✅ Small datasets (< 10K samples)
✅ Low-dimensional features (< 20)
✅ Non-linear decision boundaries
✅ Quick baseline before trying complex models
❌ High-dimensional data (use SVM or neural networks)
❌ Large datasets (slow prediction: O(n⋅d)O(n \cdot d) per query)

Complexity

OperationTime
TrainingO(1)O(1): just store the data
PredictionO(n⋅d)O(n \cdot d): compute all distances

This is why KNN is called a lazy learner — all the work happens at prediction time.

Exercise

What happens to KNN's decision boundary as k increases?

Need a hint?

Think about what k=n (the largest possible k) would predict.

Exercise

For a training set of 500 points in 2D, set k (number of neighbors) for a balanced KNN classifier.

1neighbors50.50neighbors100neighbors
Need a hint?

Too small = memorizes training data (high variance); too large = over-smooths. Rule of thumb: start around √n ≈ 22.

Exercise

Why must you standardize features before using KNN?

Need a hint?

Think about how distance is computed.

Exercise

In high dimensions (d → ∞), what happens to the ratio (d_max - d_min) / d_min for KNN?

Need a hint?

Think about what 'nearest' means when all distances are similar.

Common mistakes

  1. Forgetting to scale features: The #1 KNN mistake. Always standardize.
  2. Using even k for binary classification: Can result in ties. Use odd k.
  3. Ignoring the curse of dimensionality: KNN degrades badly above ~20 features. Use dimensionality reduction first.

Key takeaways

  • KNN is lazy — it stores the data and votes among the kk nearest points at query time.
  • Small kk is flexible/noisy; large kk is smooth/biased.
  • The distance metric and feature scaling dominate results — always standardize.
  • It degrades in high dimensions (curse of dimensionality) and is slow to predict.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
K-Nearest NeighborsLinear & Logistic Regress…Decision TreesK-Means ClusteringPrincipal Component Analy…The Bias–Variance TradeoffThe Recommendation ProblemThe ML Project LoopMinkowski Distance FamilyBias-Variance Decompositi…