K-Nearest Neighbors (KNN)
KNN is the simplest machine learning algorithm: no training at all. To classify a new point, just find the 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, , trades capacity against smoothness (the bias–variance story of lesson 03).
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
- Choose (the number of neighbors)
- Compute the distance from the new point to every training point
- Find the nearest points
- Return the most common label among them
For regression, return the average of the 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 .
Worked example
Training data:
| Point | Features () | 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 .
Step 1: compute the Euclidean distance to every training point. For each point we take the gap in , the gap in , square both, add, and square-root:
Step 2 — sort by distance (nearest first):
| Rank | Point | Distance | Label |
|---|---|---|---|
| 1 | B | 1.41 | Red |
| 2 | A | 2.83 | Red |
| 3 | C | 3.16 | Blue |
| 4 | D | 5.00 | Blue |
| 5 | E | 5.39 | Blue |
Step 3: keep the nearest and vote. With , the neighbors are B (Red), A (Red), C (Blue).
This is the exact query point and result reproduced in the companion notebook. Notice that the answer can flip with : at the votes become , so the prediction would change to Blue. The choice of is not a detail. It can decide the class.
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 () is the default for continuous features. The Manhattan distance () works better for high-dimensional sparse data. Both are special cases of the Minkowski distance , which also covers Chebyshev () and Hamming for categorical features.
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.
# 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 controls how much you smooth. Think of it as a dial between trusting one neighbor versus averaging a whole crowd.
Small (e.g. ): 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 (e.g. ): 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 it ignores the query entirely and always returns the global majority class. The boundary is over-smoothed and underfits.
We want the that minimizes total error = bias² + variance + irreducible noise. As 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 , score each on held-out folds, and pick the best. A useful starting point is the heuristic . For binary classification, prefer an odd so a two-way vote can never tie.
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 , the boundary is the Voronoi tessellation of the training points — each region is the set of points closest to one training example.
As increases, the boundary becomes smoother. This is the bias-variance tradeoff in action:
| k | Bias | Variance | Boundary |
|---|---|---|---|
| 1 | Low | High | Very jagged |
| Medium | Medium | Balanced | |
| High | Low | Always majority class |
k-NN decision boundary
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:
Why it happens (worked intuition)
Suppose each coordinate contributes a small, roughly independent squared gap of size to the distance. With dimensions the squared distance is a sum of such gaps, so it grows like , and the distance grows like . 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 | Typical |
|---|---|
| 2 | ≈ 40–60× (nearest is clearly nearest) |
| 10 | ≈ 3–4× |
| 100 | ≈ 1.5× |
| 1000 | ≈ 1.1× (everything is "equally far") |
By 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: per query)
Complexity
| Operation | Time |
|---|---|
| Training | : just store the data |
| Prediction | : 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.
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
- Forgetting to scale features: The #1 KNN mistake. Always standardize.
- Using even k for binary classification: Can result in ties. Use odd k.
- 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 nearest points at query time.
- Small is flexible/noisy; large 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
- Decision Trees: the other classic non-parametric baseline
- K-Means Clustering: another distance-based, centroid method
- Principal Component Analysis: fighting the curse of dimensionality before KNN