Why Your KNN Model Fails in High Dimensions: Understanding the Curse of Dimensionality

Picture finding a neighbor on your street. You walk a few houses down, and there they are. Now picture finding that same neighbor in a skyscraper with a billion rooms. Even with thousands of people inside, the odds of someone being in the room right next to yours drop to near zero. For Sam at HomeMatch, that’s exactly the trap — every new feature he adds to his 30-day sellability model makes the “nearest neighbor” for each listing a little less meaningful.

Last time, Sam saw how Support Vector Machines build wide highways to separate data. So what happens with a simpler approach like K-Nearest Neighbors (KNN), when we keep piling on more features?

You’d think more features — height, weight, eye color, favorite food, zip code — would make finding a match easier. In data science, the opposite tends to hold. This is the “Curse of Dimensionality.”

1. The Pizza Topping Problem

Think of finding a neighbor on a 1D line. Drop 10 points on a 10-inch string, and someone is bound to be close. Now move to a 2D square — like a pizza. Those same 10 points start to feel further apart. In a 3D cube, they’re rattling around in a lot of empty space.

As we add dimensions, the room for things to hide grows exponentially. So what happens to the nearest-neighbor distance as we add dimensions? Let’s check in Python.

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist

def average_nearest_neighbor_distance(dims, n_points=100):
    # Create 100 random points in a unit hypercube of 'dims' dimensions
    points = np.random.rand(n_points, dims)
    # Calculate distances between all points
    distances = cdist(points, points)
    # Set diagonal to infinity so we don't pick ourselves as the neighbor
    np.fill_diagonal(distances, np.inf)
    # Return the average distance to the closest neighbor
    return np.mean(np.min(distances, axis=1))

dimensions = range(1, 101, 5)
avg_distances = [average_nearest_neighbor_distance(d) for d in dimensions]

With the metric computed at every dimension count, let’s plot the trend and read off the two extremes.

plt.plot(dimensions, avg_distances, marker='o')
plt.xlabel("Number of Features (Dimensions)")
plt.ylabel("Avg Distance to Nearest Neighbor")
plt.title("The Neighborhood Gets Lonely Fast")
plt.show()

print(f"Distance in 1D: {avg_distances[0]:.4f}")
print(f"Distance in 100D: {avg_distances[-1]:.4f}")

• np.random.rand(n_points, dims) generates 100 random points uniformly distributed in a dims-dimensional unit hypercube (each coordinate between 0 and 1) — as dims increases, the points spread further apart because the volume of the hypercube grows exponentially with each new dimension.
• cdist(points, points) computes the full pairwise distance matrix between all 100 points — the result is a 100×100 array where entry [i, j] is the Euclidean distance from point i to point j.
• np.fill_diagonal(distances, np.inf) sets the diagonal (each point’s distance to itself) to infinity — without this, the nearest neighbor of every point would be itself at distance 0, which defeats the purpose of the experiment.
• np.min(distances, axis=1) finds the smallest value in each row — that’s the distance from each point to its nearest neighbor.
• np.mean(...) averages those minimum distances across all 100 points — this single number is the metric we track as dimensions increase from 1 to 100.
• dimensions = range(1, 101, 5) produces dimension counts 1, 6, 11, …, 96 — stepping by 5 gives a smooth trend without running all 100 individual values.
• plt.plot(dimensions, avg_distances, marker='o') plots the trend with circle markers — the curve rises steeply, visually confirming that even your nearest neighbor gets further away as dimensions pile up.
• print(f"Distance in 1D: {avg_distances[0]:.4f}") prints the 1-dimensional average — this should be a small number (around 0.01), confirming that in 1D neighbors are genuinely close.
• print(f"Distance in 100D: {avg_distances[-1]:.4f}") prints the ~100-dimensional value — this should approach the theoretical maximum (close to 1.0 in a unit hypercube), showing that even your ‘closest’ neighbor is nearly as far as the entire space allows.

What this means in practice: in 1D, your neighbor was right next door — maybe 0.01 units away. By 100 dimensions, your closest neighbor is nearly 1.0 units away. That’s the entire width of our search space. Everyone has become a stranger.

2. What is KNN actually doing?

KNN is the “social” algorithm. It assumes things that are close are similar. Want to know if a house is “Red” or “Blue” (like our example from the SVM chapter)? KNN looks at the $K$ closest houses and takes a vote.

The catch: KNN depends entirely on the neighborhood being representative. An empty neighborhood, or a “closest” neighbor miles away, and the logic breaks. Here’s a standard KNN on a simple 2-feature dataset.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_blobs

# Create a simple 2D dataset
X, y = make_blobs(n_samples=100, centers=2, random_state=42, cluster_std=1.5)

# Train KNN with 3 neighbors
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X, y)

# Predict for a new point
new_point = [[0, 0]]
prediction = knn.predict(new_point)
print(f"Prediction for point at (0,0): {prediction[0]} (0=Blue, 1=Red)")

• from sklearn.neighbors import KNeighborsClassifier imports scikit-learn’s KNN classifier — this is the “lazy learner” that stores all training data and defers computation until prediction time.
• make_blobs(n_samples=100, centers=2, random_state=42, cluster_std=1.5) creates 100 points in 2 clusters with standard deviation 1.5 — random_state=42 ensures reproducibility; the moderate cluster_std means the clusters overlap slightly but remain distinguishable, which is the sweet spot where KNN works well.
• KNeighborsClassifier(n_neighbors=3) creates a KNN that looks at the 3 nearest training points — the predicted class is the majority vote among those 3 neighbors.
• knn.fit(X, y) “trains” the model — for KNN, this step simply stores the training data; no weights are learned until predict is called, which is why KNN is called a “lazy learner” (no learning happens at fit time).
• new_point = [[0, 0]] defines a single query point at the origin — the model will measure the Euclidean distance from (0, 0) to all 100 training points, select the 3 closest, and take a majority vote.
• knn.predict(new_point) returns the predicted label — prediction[0] extracts the scalar value from the returned array so it can be printed.

In 2D, this works fine — the points are packed tightly. But add more features, and “closeness” becomes a lie.

3. The ‘Empty Space’ Phenomenon

Here’s the tricky part: in high dimensions, most data points end up at the corners or the outer ‘crust’ of the space. The middle goes empty.

Think of an orange. In 3D, most of the orange is fruit, with a thin peel. But in 100 dimensions, that ‘mathematical orange’ is roughly 99% peel and 1% fruit. If your data is the fruit, it’s all pressed against the edges.

def volume_ratio(dims):
    # Ratio of a slightly smaller inner cube to the full unit cube
    inner_edge = 0.9
    return (inner_edge ** dims)

dimensions = [1, 2, 5, 10, 50, 100]
for d in dimensions:
    ratio = volume_ratio(d)
    print(f"In {d}D, the 'center' holds {ratio*100:.2f}% of the volume.")

• inner_edge = 0.9 defines the edge length of the “inner cube” — imagine shaving 5% off each side of the unit cube, leaving a smaller cube of edge 0.9 sitting in the center; the region between the inner cube and the outer boundary is the “peel.”
• inner_edge ** dims computes the volume ratio — in dims dimensions, the volume of a hypercube is edge^dims, so the ratio of the inner cube to the full cube is 0.9^dims; this shrinks exponentially because each new dimension multiplies the ratio by another 0.9.
• dimensions = [1, 2, 5, 10, 50, 100] samples a range of dimension counts — 1D through 100D, showing the dramatic collapse from 90% down to effectively 0%.
• print(f"In {d}D, the 'center' holds {ratio*100:.2f}% of the volume.") formats the ratio as a percentage — in 1D the center holds 90%, in 2D it’s 81%, by 10D it’s under 35%, and by 100D it rounds to 0.00%, visually proving the “empty middle” phenomenon.

By 100 dimensions, the center holds 0.00% of the volume. Your data points sit far apart from each other. So when KNN goes looking for a neighbor, it has to reach across a lot of empty space.

4. Let’s see what happens to the math

The Euclidean distance formula—our measure of ‘closeness’—loses its contrast in high dimensions. In 2D, there’s a clear gap between your best friend an inch away and a stranger ten miles down the road.

In 100D, the math stacks differently. Your ‘closest’ friend might sit 10.1 miles away while your ‘farthest’ enemy sits at 10.2. If everyone’s roughly the same distance away, how do you pick a ‘closest’ neighbor? The signal drowns in noise from too many features.

# Comparing distance distributions
def plot_dist_ratio(dims):
    points = np.random.rand(500, dims)
    dists = cdist(points, points).flatten()
    dists = dists[dists > 0] # Ignore distance to self
    plt.hist(dists, bins=50, alpha=0.5, label=f"{dims}D")

plt.figure(figsize=(10, 6))
plot_dist_ratio(2)
plot_dist_ratio(100)
plt.legend()
plt.title("Distance Concentration: Everyone becomes equally far away")
plt.xlabel("Distance")
plt.show()

• points = np.random.rand(500, dims) generates 500 random points in dims dimensions — we use 500 points (more than the 100 in the earlier experiment) so the histograms are smoother and the concentration effect is more visually obvious.
• cdist(points, points).flatten() computes the full 500×500 pairwise distance matrix and flattens it into a 1D array of 250,000 values — this includes all pairwise distances, not just nearest-neighbor distances, so we can see the entire distribution.
• dists[dists > 0] filters out the zero self-distances — the diagonal entries (where a point’s distance to itself is exactly 0) would create a misleading spike at 0 in the histogram; this mask removes them.
• plt.hist(dists, bins=50, alpha=0.5, label=f"{dims}D") draws a histogram with 50 bins and 50% transparency — alpha=0.5 lets both the 2D and 100D histograms be visible when overlaid on the same axes.
• plot_dist_ratio(2) and plot_dist_ratio(100) generate the two overlaid histograms — the 2D histogram will be wide and spread out (distances vary a lot, so “closeness” is meaningful), while the 100D histogram will be a tall narrow spike (all distances converge to nearly the same value, making “closeness” meaningless).
• plt.legend() adds a legend distinguishing the 2D and 100D curves — the visual contrast between the wide 2D spread and the narrow 100D spike is the key takeaway of the entire article.

The curse of dimensionality: distance concentration and volume collapse

The Euclidean distance between two points in $d$ dimensions:

$d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{d} (x_i - y_i)^2}$

As $d$ grows, the mean pairwise distance grows proportionally to $\sqrt{d}$, but its relative spread shrinks — so all distances converge toward the same value:

$\frac{d_{\max} - d_{\min}}{d_{\min}} \xrightarrow{d \to \infty} 0 \qquad \text{(distance concentration)}$

Meanwhile, the fraction of volume in the “center” of the hypercube collapses exponentially:

$\text{volume ratio} = \left(\frac{\text{inner edge}}{\text{full edge}}\right)^{d} = 0.9^{d} \xrightarrow{d \to \infty} 0$

Plain English	Statistical symbol	Python equivalent
Euclidean distance in $d$ dimensions	$d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{d} (x_i - y_i)^2}$	cdist(points, points)
Number of dimensions (features)	$d$	dims in average_nearest_neighbor_distance(dims)
Inner-to-full volume ratio	$0.9^{d}$	inner_edge ** dims in volume_ratio(dims)
Relative distance contrast ($\to 0$ means all distances are equal)	$\frac{d_{\max} - d_{\min}}{d_{\min}}$	(implicit — visualized via plt.hist)
Mean pairwise distance (grows as $\sqrt{d}$)	$E[d] \propto \sqrt{d}$	np.mean(np.min(distances, axis=1))

The 100D histogram is a tall, skinny spike—almost every pair of points sits at the exact same distance. At that point, the model is basically guessing.

5. The Fix: Feature Selection and PCA

So what do we do? Get selective. More data isn’t always better data. Dimensionality Reduction pulls those neighbors back together.

The goal is to find the ‘manifold’—the smaller, lower-dimensional space where the data actually lives. Here’s how Principal Component Analysis (PCA) helps a struggling KNN model.

from sklearn.decomposition import PCA
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Create a dataset with 2 useful features and 98 noise features
X_useful, y = make_blobs(n_samples=500, centers=2, n_features=2, random_state=42)
X_noise = np.random.rand(500, 98)
X_high_dim = np.hstack([X_useful, X_noise])

X_train, X_test, y_train, y_test = train_test_split(X_high_dim, y, test_size=0.2)

# KNN on high-dimensional noisy data
knn_noisy = KNeighborsClassifier(n_neighbors=5)
knn_noisy.fit(X_train, y_train)
pred_noisy = knn_noisy.predict(X_test)

That’s the naive baseline. Now let’s reduce the same training data to 2 dimensions with PCA before handing it to a fresh KNN model, and compare accuracy.

# KNN after PCA (reducing 100 dimensions to 2)
pca = PCA(n_components=2)
X_train_pca = pca.fit_transform(X_train)
X_test_pca = pca.transform(X_test)

knn_pca = KNeighborsClassifier(n_neighbors=5)
knn_pca.fit(X_train_pca, y_train)
pred_pca = knn_pca.predict(X_test_pca)

print(f"Accuracy with 100 features: {accuracy_score(y_test, pred_noisy):.2f}")
print(f"Accuracy after PCA (2 features): {accuracy_score(y_test, pred_pca):.2f}")

• make_blobs(n_samples=500, centers=2, n_features=2, random_state=42) creates 500 points with only 2 meaningful features — these 2 features carry the actual class-separating signal; the rest will be pure noise.
• X_noise = np.random.rand(500, 98) generates 98 columns of pure random noise — these features have no relationship to the labels; they’re the “empty rooms” in the skyscraper that drown out the signal.
• X_high_dim = np.hstack([X_useful, X_noise]) horizontally stacks the 2 useful features with the 98 noise columns — producing a 100-feature dataset where only 2 dimensions matter, simulating what happens when Sam throws every available listing attribute into the model.
• train_test_split(X_high_dim, y, test_size=0.2) splits 80/20 into train and test — 400 training points, 100 test points, all carrying the same 100 features.
• KNeighborsClassifier(n_neighbors=5) with 100 features will struggle — in 100D, the 5 nearest neighbors are essentially random because all distances are nearly equal.
• pca = PCA(n_components=2) creates a PCA object that will project the 100-dimensional data onto the 2 directions of maximum variance — ideally recovering the 2 useful dimensions and discarding the 98 noise dimensions.
• pca.fit_transform(X_train) fits PCA on the training data and transforms it in one step — the PCA components are learned from the training set only; calling fit_transform on the training data ensures the projection is not influenced by test data (no data leakage).
• pca.transform(X_test) applies the same projection to the test set — note we use transform (not fit_transform) so the test data is projected onto the same components learned from the training set.
• accuracy_score(y_test, pred_noisy) and accuracy_score(y_test, pred_pca) compare the two approaches — the PCA version should recover most of the signal by collapsing the noise, while the raw 100D KNN will degrade because the noise features overwhelm the distance metric.

The naive model was likely off by a significant margin—often 10-20% lower accuracy. Using PCA, we stripped away the 98 dimensions of ‘empty space’ and noise. Now KNN could focus on the 2 dimensions where the actual ‘neighborhoods’ existed.

When KNN degrades in high dimensions, Sam has three main strategies — each with different tradeoffs:

Dimensionality reduction (PCA) projects the data onto fewer axes of maximum variance, collapsing noise dimensions into a compact subspace where distances regain meaning. It’s unsupervised (doesn’t look at labels) and fast, but it assumes the directions of maximum variance are also the directions that carry class-discriminating signal — which isn’t always true. If the 98 noise features have larger variance than the 2 useful ones, PCA will keep the noise and discard the signal.

Feature selection (keeping only the most informative features) is more direct — use statistical tests, mutual information, or model-based importance to identify which features actually matter, then drop the rest. It’s interpretable (you know exactly which features survived) and preserves the original feature meanings, but it requires more manual tuning and may miss interactions that only matter in combination.

Switching to tree-based models (Random Forest, Gradient Boosting) sidesteps the distance problem entirely. Trees split on individual feature values, not on distances between points, so they’re immune to the curse of dimensionality’s distance-concentration effect. They handle mixed feature types natively and scale better to high-dimensional tabular data — but they sacrifice the intuitive “similar listings get similar predictions” logic that made KNN appealing in the first place.

Criterion	PCA + KNN	Feature selection + KNN	Tree-based model
Preserves distances?	Yes (in reduced space)	Yes (in selected features)	No (uses splits, not distances)
Handles correlated noise?	Risky (may keep high-variance noise)	Better (can drop noise by name)	Best (trees ignore unhelpful features)
Interpretability	Moderate (PCs are hard to name)	High (you know which features survive)	Moderate (feature importance available)
Effort level	Low (one call to PCA)	Medium (need selection strategy)	Low (just swap the model)
Best for Sam when	Noise is low-variance, signal is spread across many features	A few features clearly matter and the rest are noise	Many features matter, mixed types, interactions are complex

Rule of thumb for Sam’s HomeMatch problem: Start with feature selection if Sam knows which features should matter for sellability — it’s the most transparent fix. If the signal is spread across many correlated features and he can’t easily pick them by hand, PCA is the next step. If neither works because the data is just too messy and high-dimensional, switch to a tree ensemble — which is where Sam was already heading in P04 and P06.

6. Recap: Survival Guide for High Dimensions

As dimensions grow, our data points get lonely. The center of the space disappears, and the word “close” stops meaning much. Here’s a checklist for the next time you build a model:

• Check your ratio: 100 features but only 100 rows? KNN will almost certainly fail.
• Watch for distance concentration: If your model’s confidence scores are all nearly identical, the curse of dimensionality is likely at work.
• Simplify first: Try dimensionality reduction (like PCA) or feature selection before abandoning a distance-based model.

Next up in the series, Sam pivots to a side task — sorting spam leads from real listing inquiries in HomeMatch’s inbox. He meets a model that doesn’t care about distance at all: Naive Bayes. Its “naive” independence assumption often works better than you’d expect.

Check Your Understanding

Questions below move from simple recall up to open-ended design, roughly following Bloom’s Taxonomy.

Remember What is the “Curse of Dimensionality,” and what happens to the average distance between random points as dimensions increase?

Understand In your own words, explain the “mathematical orange” analogy—why does the center of a high-dimensional cube hold almost none of its volume?

Apply Using the article’s volume_ratio formula (inner_edge ** dims with inner_edge = 0.9), calculate what percentage of the volume the center holds at dims = 20, and compare it to the article’s reported value at dims = 100.

Analyze The article shows that in 100D, “your ‘closest’ friend might be 10.1 miles away and your ‘farthest’ enemy might be 10.2 miles away.” Walk through why this loss of “contrast” between near and far specifically breaks KNN’s voting logic, even though the distances themselves are still technically being calculated correctly.

Evaluate The article’s PCA fix reduces 100 dimensions (2 useful + 98 noise) down to 2 components. Critique this specific setup: PCA doesn’t know which 2 of the 100 original features were the “useful” ones—it just finds directions of maximum variance. What would go wrong with this fix if the 98 “noise” features had much larger variance than the 2 useful ones?

Create Design a diagnostic check a data scientist could run before training a KNN model to decide whether the Curse of Dimensionality is likely to be a problem for their specific dataset (some combination of row count, feature count, and/or a distance-distribution check like the article’s histogram). Describe what result would tell them to switch strategies.

---

Related articles

• P07: Support Vector Machines, Intuitively — Finding the Widest Margin) — the previous technique Sam explored: how SVMs build the widest possible buffer between classes, and why that margin-based confidence is a different philosophy from KNN’s neighborhood voting.
• P09: Naive Bayes — Why the Naive Independence Assumption Works) — the next technique Sam turns to: a probability-based classifier that doesn’t need distances at all, perfect for the spam-vs-real-leads inbox task where KNN’s dimensionality problems would be unnecessary overhead.

References & Further reading

• Cover, T. & Hart, P. (1967). “Nearest Neighbor Pattern Classification.” IEEE Transactions on Information Theory, 13(1), 21–27. — the foundational paper that formalized the k-nearest-neighbor rule and proved its error rate is bounded by twice the Bayes optimal rate, establishing KNN as a theoretically grounded lazy learner.
• Bellman, R. (1957). Dynamic Programming. Princeton University Press. — the book where the term “curse of dimensionality” was first coined, originally in the context of dynamic programming but adopted universally to describe the exponential blow-up of volume and distance concentration in high-dimensional spaces.
• Kaggle: House Prices — Advanced Regression Techniques — a tabular regression competition with 79 features where dimensionality reduction and feature selection are central strategies; a good playground for testing whether PCA or feature selection helps a KNN baseline compete with tree-based models.
• scikit-learn: Nearest Neighbors documentation — official docs covering KNeighborsClassifier, KNeighborsRegressor, distance metrics (euclidean, manhattan, minkowski), and guidance on choosing n_neighbors.
• scikit-learn: PCA documentation — official docs for sklearn.decomposition.PCA, including n_components, fit_transform, transform, and the explained_variance_ratio_ attribute for diagnosing how many components to keep.

---