🎯 What You'll Learn
- Understand the intuition of KNN as a lazy, non-parametric learner that memorises training data
- Compute and compare distance metrics: Euclidean, Manhattan, Minkowski, and cosine
- Understand the bias-variance tradeoff as K varies — why K=1 overfits and large K underfits
- Implement KNN for both classification and regression with scikit-learn
- Understand why feature scaling is mandatory and how to select K using cross-validation
1 The Intuition
K-Nearest Neighbors is one of the most intuitive algorithms in machine learning. The idea: to classify a new data point, find the K training examples closest to it in feature space, and predict the most common class among those K neighbors. It's the algorithmic version of "a person is judged by the company they keep."
KNN has two important properties that distinguish it from models like logistic regression (Lesson 15) and most other models you'll meet in this phase:
- Non-parametric: KNN doesn't learn a fixed set of parameters (like coefficients). It makes no assumption about the shape of the underlying distribution. The "model" is literally the entire training dataset.
- Lazy learner: There is no training phase in the traditional sense. The algorithm simply stores the training data. All the computation happens at prediction time — for each new query, it searches the training set for the K nearest points.
This laziness has real consequences: KNN is fast to "train" (just store data), but can be slow to predict when the training set is large. And since it stores all training data, it can also be memory-intensive.
To classify the query point, KNN finds its K=3 closest training points by distance (dashed lines) and takes a majority vote among them — here, 2 of the 3 nearest neighbors are Class A, so the query is predicted Class A, even though it sits closer to the overall cluster of Class B on the right.
Unlike parametric models that compress data into a fixed number of parameters, KNN makes every prediction by looking directly at the training data. This means: (1) adding new training data is trivial — just append it; (2) predictions become slower as your dataset grows; and (3) the model can represent arbitrarily complex decision boundaries given enough data and the right K.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
# Simple demonstration
X, y = make_classification(n_samples=200, n_features=2, n_redundant=0,
n_informative=2, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# KNN "training" = just storing the data
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train) # nearly instant — just stores X_train, y_train
acc = knn.score(X_test, y_test)
print(f"Accuracy with K=5: {acc:.4f}")2 Distance Metrics
KNN's behavior depends entirely on how "closeness" is defined. Different distance metrics capture different notions of similarity. Choosing the right one for your data matters.
Euclidean Distance (p=2)
The straight-line distance between two points in n-dimensional space. This is the default for KNN and is the most commonly used. It treats all dimensions symmetrically.
d(x, y) = √(Σᵢ (xᵢ − yᵢ)²)
Manhattan Distance (p=1)
The sum of absolute differences across dimensions — like navigating a city grid where you can only move north/south/east/west. Less sensitive to outliers in individual dimensions than Euclidean.
d(x, y) = Σᵢ |xᵢ − yᵢ|
Minkowski Distance (general)
Generalization: p=1 gives Manhattan, p=2 gives Euclidean, p→∞ gives Chebyshev (maximum difference along any dimension).
Cosine Similarity (for text)
Measures the angle between two vectors rather than the absolute distance. Two documents with the same words in the same proportions will have cosine similarity = 1.0, regardless of document length.
import numpy as np
def euclidean(a, b):
return np.sqrt(np.sum((a - b) ** 2))
def manhattan(a, b):
return np.sum(np.abs(a - b))
def minkowski(a, b, p):
return np.sum(np.abs(a - b) ** p) ** (1 / p)
def cosine_similarity(a, b):
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
# Two example points
x = np.array([1.0, 2.0, 3.0])
y = np.array([4.0, 0.0, 6.0])
print(f"Euclidean: {euclidean(x, y):.4f}") # 3D straight-line distance
print(f"Manhattan: {manhattan(x, y):.4f}") # Sum of absolute diffs
print(f"Minkowski(p=3): {minkowski(x, y, 3):.4f}")
print(f"Cosine sim: {cosine_similarity(x, y):.4f}")
# Text example: two document vectors (word counts)
doc1 = np.array([3, 0, 2, 1, 0]) # "buy cheap meds online"
doc2 = np.array([2, 0, 1, 1, 0]) # shorter version of same doc
doc3 = np.array([0, 1, 0, 0, 5]) # completely different doc
print(f"\nCosine(doc1, doc2) = {cosine_similarity(doc1, doc2):.4f}") # very similar
print(f"Cosine(doc1, doc3) = {cosine_similarity(doc1, doc3):.4f}") # very different
# sklearn supports these via metric parameter
from sklearn.neighbors import KNeighborsClassifier
knn_manhattan = KNeighborsClassifier(n_neighbors=5, metric='manhattan')
knn_cosine = KNeighborsClassifier(n_neighbors=5, metric='cosine')For most structured tabular data with scaled features, Euclidean is a solid default. Use Manhattan if features have outliers (it's more robust). Use cosine similarity for text/document data or high-dimensional sparse vectors (word frequencies, TF-IDF). When in doubt, cross-validate across a few options.
3 The K Parameter: Bias-Variance Tradeoff
K is the most important hyperparameter in KNN. Its effect on the model's behavior perfectly illustrates the bias-variance tradeoff:
- K=1 (low bias, high variance): Every prediction is made by the single nearest training point. The decision boundary follows the training data extremely closely — including all its noise. Perfect training accuracy but poor generalization. This is classic overfitting.
- K=n (high bias, low variance): Use all training points. Every test sample gets the same prediction: the majority class in the entire training set. This completely ignores feature values. Extreme underfitting.
- Sweet spot (K≈3–15): Large enough to average out noise, small enough to remain sensitive to local structure. Found by cross-validation on your specific dataset.
For binary classification, always choose an odd K to prevent ties in majority voting (e.g., 2 votes for class 0, 2 votes for class 1 when K=4). Ties are broken arbitrarily, which is a source of instability.
The chart below shows this tradeoff directly. It's a small synthetic 2-class, 2-feature dataset (40 points per class, two overlapping blobs — similar in spirit to make_classification from Section 1). The shaded background is the decision region: for every point in feature space, it shows which class a KNN classifier with the chosen K would predict, computed by majority vote among that point's K nearest training neighbors (plain Euclidean distance, no scikit-learn involved — just the same logic as the from-scratch SimpleKNN class in the practice section). Drag the slider and watch the boundary behave exactly as the bullets above describe:
K = 1 — the decision boundary is jagged and wraps tightly around individual training points (low bias, high variance — classic overfitting).
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
import numpy as np
import pandas as pd
# Non-linear dataset to visualize decision boundaries
X, y = make_moons(n_samples=300, noise=0.3, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)
k_values = [1, 3, 5, 10, 20, 50]
train_accs, test_accs = [], []
for k in k_values:
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_train_s, y_train)
train_accs.append(knn.score(X_train_s, y_train))
test_accs.append(knn.score(X_test_s, y_test))
# Collect into a DataFrame rather than hand-formatting f-strings --
# this is what you'd actually do in a notebook, and it renders as a
# proper table instead of monospaced text.
results = pd.DataFrame({
'K': k_values,
'Train Acc': [round(a, 4) for a in train_accs],
'Test Acc': [round(a, 4) for a in test_accs],
})
results| K | Train Acc | Test Acc | |
|---|---|---|---|
| 0 | 1 | 1.0000 | 0.8222 |
| 1 | 3 | 0.9238 | 0.8444 |
| 2 | 5 | 0.9190 | 0.8556 |
| 3 | 10 | 0.8905 | 0.8556 |
| 4 | 20 | 0.8714 | 0.8444 |
| 5 | 50 | 0.8333 | 0.8000 |
4 KNN for Classification
In classification, KNN predicts the class that appears most frequently among the K nearest neighbors — a majority vote. sklearn also supports distance-weighted voting: closer neighbors get higher voting weight, proportional to 1/distance. This generally improves accuracy when the K neighbors span a region with mixed classes.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.25, random_state=42, stratify=y)
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)
# Uniform weights: majority vote
knn_uniform = KNeighborsClassifier(n_neighbors=7, weights='uniform', metric='euclidean')
knn_uniform.fit(X_train_s, y_train)
print("Uniform weights:")
print(classification_report(y_test, knn_uniform.predict(X_test_s), target_names=iris.target_names))
# Distance weights: closer neighbors vote more
knn_dist = KNeighborsClassifier(n_neighbors=7, weights='distance', metric='euclidean')
knn_dist.fit(X_train_s, y_train)
print("Distance weights:")
print(classification_report(y_test, knn_dist.predict(X_test_s), target_names=iris.target_names))
# Inspect the nearest neighbors for a single test point
distances, indices = knn_uniform.kneighbors(X_test_s[:1])
print(f"\nFor the first test sample:")
print(f" Neighbor indices: {indices[0]}")
print(f" Distances: {distances[0].round(3)}")
print(f" Neighbor labels: {y_train[indices[0]]}")
print(f" Predicted class: {knn_uniform.predict(X_test_s[:1])[0]}")5 KNN for Regression
KNN can also predict continuous values. Instead of a majority vote, it takes the average of the K nearest neighbors' target values. Distance-weighted averaging is also supported.
from sklearn.neighbors import KNeighborsRegressor
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np
X, y = make_regression(n_samples=500, n_features=5, noise=20, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.2, random_state=42)
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)
for k in [1, 5, 15, 30]:
knnr = KNeighborsRegressor(n_neighbors=k, weights='distance')
knnr.fit(X_train_s, y_train)
y_pred = knnr.predict(X_test_s)
rmse = np.sqrt(mean_squared_error(y_test, y_pred))
r2 = r2_score(y_test, y_pred)
print(f"K={k:2d} RMSE={rmse:.2f} R²={r2:.4f}")
# How prediction works: average of K neighbor targets
knnr5 = KNeighborsRegressor(n_neighbors=5)
knnr5.fit(X_train_s, y_train)
distances, indices = knnr5.kneighbors(X_test_s[:1])
neighbor_targets = y_train[indices[0]]
prediction = neighbor_targets.mean()
print(f"\nNeighbor targets: {neighbor_targets.round(2)}")
print(f"Average (prediction): {prediction:.2f}")
print(f"Model prediction: {knnr5.predict(X_test_s[:1])[0]:.2f}")6 Why Feature Scaling is Critical
This is arguably the most important practical lesson about KNN. Because KNN computes distances in feature space, features measured on large scales will completely dominate the distance calculation.
Consider a dataset with two features: age (range: 20–80) and income (range: 20,000–200,000). The Euclidean distance between two points is dominated almost entirely by the income difference because income values are thousands of times larger. Age becomes nearly irrelevant to the distance calculation — even though it might be highly predictive.
Apply StandardScaler (or MinMaxScaler) before fitting KNN. This is not optional. Forgetting to scale is one of the most common mistakes when using KNN, and it can silently produce terrible results that are hard to diagnose.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
import numpy as np
np.random.seed(42)
n = 500
# Deliberately different scales
age = np.random.uniform(20, 80, n)
income = np.random.uniform(20000, 200000, n)
X = np.column_stack([age, income])
# Ground truth: young OR low income → class 1
y = ((age < 40) | (income < 80000)).astype(int)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# Without scaling
knn_unscaled = KNeighborsClassifier(n_neighbors=7)
knn_unscaled.fit(X_train, y_train)
acc_unscaled = knn_unscaled.score(X_test, y_test)
# With scaling
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s = scaler.transform(X_test)
knn_scaled = KNeighborsClassifier(n_neighbors=7)
knn_scaled.fit(X_train_s, y_train)
acc_scaled = knn_scaled.score(X_test_s, y_test)
print(f"Accuracy WITHOUT scaling: {acc_unscaled:.4f}")
print(f"Accuracy WITH scaling: {acc_scaled:.4f}")
print(f"\nImprovement from scaling: {(acc_scaled - acc_unscaled)*100:.1f} percentage points")7 Choosing K with Cross-Validation
There is no universally optimal K. The right value depends on the noise level, data density, and number of classes. Use k-fold cross-validation to find the K that generalises best to unseen data. A good starting range is K=1 to K=30 (or K=√n as a rule of thumb for n training samples).
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.datasets import load_digits
import numpy as np
import matplotlib.pyplot as plt
# Digits dataset: 8x8 images of handwritten digits, 10 classes
digits = load_digits()
X, y = digits.data, digits.target
k_range = range(1, 31)
cv_scores = []
for k in k_range:
pipe = Pipeline([
('scaler', StandardScaler()),
('knn', KNeighborsClassifier(n_neighbors=k, weights='distance'))
])
scores = cross_val_score(pipe, X, y, cv=5, scoring='accuracy')
cv_scores.append(scores.mean())
best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k} (CV accuracy: {max(cv_scores):.4f})")
# Plot K vs accuracy
plt.figure(figsize=(10, 4))
plt.plot(k_range, cv_scores, 'b-o', markersize=4)
plt.axvline(x=best_k, color='red', linestyle='--', label=f'Best K={best_k}')
plt.xlabel('Number of Neighbors (K)')
plt.ylabel('5-Fold CV Accuracy')
plt.title('KNN: Finding Optimal K via Cross-Validation')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()8 Computational Cost and Speedups
For a training set with n samples and d features, predicting one new sample requires computing the distance to all n training points — an O(n·d) operation. For large datasets, this makes KNN very slow at inference time.
sklearn offers faster algorithms for finding nearest neighbors:
- Brute force: Compute all n distances. Works well for small datasets or high-dimensional data.
- KD-Tree: Builds a binary tree partitioning feature space. Queries run in O(d·log(n)) average case. Efficient for low-dimensional data (d ≲ 20).
- Ball Tree: Generalises KD-tree to work better in higher dimensions. Supports more distance metrics. Often better than KD-tree for d > 20.
- auto (default): sklearn chooses the best algorithm based on data characteristics.
import time
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_classification
from sklearn.preprocessing import StandardScaler
import numpy as np
# Large dataset to measure timing
X_large, y_large = make_classification(n_samples=50_000, n_features=20, random_state=42)
scaler = StandardScaler()
X_large_s = scaler.fit_transform(X_large)
# Test query (100 samples)
X_query = X_large_s[:100]
algorithms = ['brute', 'kd_tree', 'ball_tree']
for algo in algorithms:
knn = KNeighborsClassifier(n_neighbors=5, algorithm=algo)
knn.fit(X_large_s, y_large)
start = time.time()
for _ in range(10): # run 10 times for stable timing
knn.predict(X_query)
elapsed = (time.time() - start) / 10
print(f"algorithm='{algo:10s}' avg prediction time for 100 samples: {elapsed*1000:.2f}ms")For very large-scale applications (millions of items), exact KNN is replaced by Approximate Nearest Neighbor (ANN) methods like FAISS (Facebook), ScaNN (Google), or HNSW. These trade a small amount of accuracy for massive speed gains. Modern recommendation systems, image retrieval, and semantic search all rely on ANN.
Real-World Spotlight: Movie Recommendations
One of the earliest recommendation approaches is user-based collaborative filtering using KNN. Represent each user as a feature vector of their movie ratings. To recommend movies to user A: find the K most similar users (using cosine similarity to handle users who've rated different numbers of movies), then recommend movies those users loved that A hasn't seen yet.
Note that modern production recommenders (Netflix, YouTube, Spotify) use dense embedding vectors + approximate nearest neighbor search (FAISS/ScaNN), which is conceptually the same idea operating at hundred-million scale.
import numpy as np
from sklearn.neighbors import NearestNeighbors
# User-movie ratings matrix (5 users, 8 movies), 0 = not rated
ratings = np.array([
[5, 4, 0, 0, 1, 0, 3, 5], # user 0: sci-fi fan
[4, 5, 1, 0, 0, 0, 4, 4], # user 1: sci-fi fan
[0, 0, 5, 4, 0, 1, 0, 0], # user 2: romance fan
[0, 0, 4, 5, 1, 0, 0, 0], # user 3: romance fan
[3, 0, 0, 0, 5, 4, 2, 3], # user 4: action fan
], dtype=float)
# Cosine similarity via NearestNeighbors
nn = NearestNeighbors(n_neighbors=3, metric='cosine', algorithm='brute')
nn.fit(ratings)
# Find 2 most similar users to user 0 (excluding self)
target_user = ratings[0:1]
distances, indices = nn.kneighbors(target_user, n_neighbors=3)
print("User 0 (sci-fi fan) — nearest neighbors:")
for dist, idx in zip(distances[0], indices[0]):
if idx != 0:
sim = 1 - dist # cosine similarity = 1 - cosine distance
print(f" User {idx} similarity={sim:.3f} ratings={ratings[idx]}")
# Find movies user 0 hasn't rated (rating=0) but neighbors liked
unrated_mask = ratings[0] == 0
recommendations = {}
for idx in indices[0][1:]: # skip self
for movie_id in np.where(unrated_mask)[0]:
if ratings[idx, movie_id] > 0:
recommendations[movie_id] = recommendations.get(movie_id, 0) + ratings[idx, movie_id]
print("\nRecommendations for User 0:")
for movie, score in sorted(recommendations.items(), key=lambda x: -x[1]):
print(f" Movie {movie}: neighbor rating sum = {score}")Quick Check
✍️ Practice Exercises
- Load the
load_wine()dataset (3 classes, 13 features). Train KNN with and withoutStandardScalerfor K=5. Print the accuracy difference and explain why scaling matters for this dataset. - Using
make_moons(noise=0.3), sweep K from 1 to 30 and plot both training and test accuracy. Identify the K where overfitting starts (training acc >> test acc). - Compare
weights='uniform'vsweights='distance'on the Iris dataset using 5-fold cross-validation. Which performs better for K=7? - Implement a from-scratch KNN classifier using only NumPy. It should implement
fit(X, y)andpredict(X). Verify its predictions match sklearn's KNN on a small dataset. - On the digits dataset, compare
metric='euclidean'vsmetric='manhattan'for K=5. Which gives higher 5-fold CV accuracy?
▶ From-Scratch KNN Hint
class SimpleKNN:
def __init__(self, k=5):
self.k = k
def fit(self, X, y):
self.X_train = X
self.y_train = y
def predict(self, X):
preds = []
for x in X:
dists = np.sqrt(np.sum((self.X_train - x) ** 2, axis=1))
k_idx = np.argsort(dists)[:self.k]
k_labels = self.y_train[k_idx]
# Majority vote
counts = np.bincount(k_labels)
preds.append(np.argmax(counts))
return np.array(preds)📚 Primary Sources
sklearn: Nearest Neighbors — covers KD-tree, ball tree, distance metrics, and all parameters.
Wikipedia: K-nearest neighbors algorithm — good mathematical background and history.