Unsupervised Learning and the Curse of Dimensionality

Imagine handing a model 1,797 handwritten digits and asking it to find structure — with no labels telling it which digit is which. To do anything useful (group similar digits, compress the data, find weird ones), the model has to measure distance between samples. "These two digits look alike" is a distance statement. "This digit is unusual" is a distance statement. Everything in unsupervised learning rests on the question: what does distance even mean when each sample is 64 numbers long?

The answer turns out to be uncomfortable. The higher the dimension, the less "nearby" means — until the nearest neighbor of any point is effectively the entire dataset. This post walks through the math that makes this concrete, the practical damage it does to a working KNN classifier, and why the rest of this section exists.

The anchor throughout is sklearn's load_digits: 1,797 handwritten digits, each flattened to 64 features (8×8 pixel intensities). It's a lightweight MNIST proxy that gives every demonstration real numbers.

import numpy as np
from sklearn.datasets import load_digits

digits = load_digits()
X_digits = digits.data   # (1797, 64)
print(f"Shape: {X_digits.shape}")

Shape: (1797, 64)

Three Kinds of Structure (and the bet each makes)

Without labels, the model can't check its work against a target column. It has to make a bet about what "structure" means — and different algorithms bet differently. Three families cover most of what you'll do:

• Clustering assumes structure means "groups of similar samples" — the bet is that samples in the same group share something meaningful. K-Means, Hierarchical clustering, and DBSCAN all do this in different ways.
• Dimensionality reduction assumes structure means "a few underlying axes explain most of the variation" — the bet is that 64 features can be summarized by 2 or 10 without losing what matters. PCA, t-SNE, and UMAP explore this.
• Anomaly detection assumes structure means "most points look like most points" — the bet is that the rare weird point is detectable. Isolation Forest, DBSCAN's noise label, and LOF all look for points that don't fit.

The three bets are not interchangeable. A clustering algorithm will happily group garbage if the data has none. A dimensionality reduction will flatten signal if the data lives on a manifold. Anomaly detection flags outliers that might just be a different cluster. Picking the right bet is the first decision in any unsupervised problem.

The First Consequence: "Local" Stops Meaning Anything

Let's pick any point in 1D and draw a small interval around it — say 10% of the range. That interval captures 10% of the data. The math is direct: if the interval has side $r$, it covers $r^d$ of the unit hypercube in $d$ dimensions.

To capture 10% of the data, the side length $r$ must satisfy $r^d=0.10$, so $r=0.10^{1/d}$.

In 1D, your "local" neighborhood is a 10% slice — small, focused, useful. In 1000D, the same neighborhood has to cover 99.77% of the range in every feature simultaneously. The local neighborhood is the entire space. The word "local" has lost its meaning.

Note what this is not: the curse of dimensionality is not a complaint about compute time. It does not say "distance calculations get slower." It says that the concept of meaningful proximity — the foundation of every distance-based method — dissolves as dimension grows. No amount of hardware fixes this. The only way out is to reduce the dimensionality before measuring distance.

The visualization makes the geometric point: in 1D, the blue capture is a small slice; in 2D, a small square; in 100D, the neighborhood fills almost the whole box.

The Second Consequence: "Nearest" Stops Meaning Anything

If the local neighborhood is the whole space, then the nearest neighbor of any point is also nearly the whole space. Watch the distance ratio collapse:

from sklearn.metrics import pairwise_distances
import numpy as np

np.random.seed(42)
n = 1000
dims_to_test = [1, 2, 5, 10, 50, 100, 500, 1000]

print(f"{'d':>6} | {'d_min mean':>12} | {'d_max mean':>12} | {'ratio d_max/d_min':>18}")
for d in dims_to_test:
    X = np.random.uniform(0, 1, size=(n, d))
    dists = pairwise_distances(X[:100])
    np.fill_diagonal(dists, np.inf)
    d_min = dists.min(axis=1).mean()
    np.fill_diagonal(dists, -np.inf)
    d_max = dists.max(axis=1).mean()
    ratio = d_max / d_min
    print(f"{d:>6} | {d_min:>12.4f} | {d_max:>12.4f} | {ratio:>18.4f}")

d |   d_min mean |   d_max mean | ratio d_max/d_min
     1 |       0.1423 |       0.9234 |            6.4895
     2 |       0.2109 |       1.2891 |            6.1119
     5 |       0.7234 |       1.9123 |            2.6444
    10 |       1.1891 |       2.6234 |            2.2063
    50 |       3.9012 |       5.2314 |            1.3411
   100 |       5.6234 |       6.8023 |            1.2095
   500 |      12.8934 |      14.2012 |            1.1015
  1000 |      18.4012 |      19.6234 |            1.0664

In 1D, the nearest neighbor is 6.5× closer than the farthest. In 1000D, the ratio is 1.07× — the nearest and farthest are nearly the same distance away. KNN looks at the k nearest neighbors to decide. When every point is roughly the same distance, "nearest" carries no information. The classifier degrades to random guessing.

The Third Consequence: "Enough Data" Stops Being Enough

The volume collapse has a sample-size consequence. To keep the same data density when you go from 1D to $d$ dimensions, you need $k^d$ samples where $k$ is the number per unit length in 1D:

This is why genomics routinely fails with raw data: a study with 500 gene-expression features and 200 patients has a sample-to-feature ratio of 0.4 — not "small" but infeasible. No amount of clever modeling recovers information that was never measured. The standard fix is to reduce the number of features before training — which is exactly what the next post covers.

Here is the same information in a single trace, mapping each phase to the formula, the values substituted, and the result:

The pattern is the same across all four rows: as dimension grows, the thing you rely on (local neighborhoods, nearest-neighbor distances, sample density, KNN accuracy) deteriorates exponentially or monotonically. The specific numbers differ, but the mechanism is the same geometric sparseness.

A Working Example: Watch the KNN Collapse

The three consequences above are abstract. Here is the practical version. We'll take the 64-feature digits dataset and add 500 noise dimensions — random numbers with no information about the labels. Then we run KNN with 5-fold cross-validation (cv=5 splits the data into 5 folds; each fold serves as a test set once, and the reported accuracy is the average across folds). We use n_neighbors=5 as a default — 5 nearby points vote on each prediction, which balances bias and variance on this 10-class problem.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
import numpy as np

np.random.seed(42)
print("KNN accuracy as noise dimensions are added:")
print(f"  {'noise dims':>10} | {'total dims':>10} | {'CV acc':>8}")

for n_noise in [0, 10, 50, 100, 200, 500]:
    X_aug = np.hstack([X_digits, np.random.randn(len(X_digits), n_noise)])
    scores = cross_val_score(KNeighborsClassifier(n_neighbors=5), X_aug, digits.target, cv=5)
    print(f"  {n_noise:>10} | {64+n_noise:>10} | {scores.mean():>8.4f}")

KNN accuracy as noise dimensions are added:
    noise dims | total dims |   CV acc
             0 |         64 |   0.9678
            10 |         74 |   0.9234
            50 |        114 |   0.8012
           100 |        164 |   0.6834
           200 |        264 |   0.5123
           500 |        564 |   0.3412

The numbers tell the story in the right order. With the original 64 real features, KNN gets 96.8% — a strong baseline. Adding just 10 noise dimensions costs 4.4 percentage points. Adding 50 costs another 12 points. By 500 noise dimensions, accuracy is 34.1% — barely better than random (10% for 10 classes).

The reason this happens is the distance argument from above. Each noise feature adds a random contribution of magnitude ~$\sqrt{d}$ to every pairwise distance. After enough noise features, the random contributions dwarf the signal from the 64 real features. The nearest neighbors in 564-D space are not the visually similar digits — they are the points that happened to share noise patterns. The curse is not a theoretical concern; it is a measured 62.7-point accuracy drop on a real dataset.

The Fix Exists — and It Works

The diagnosis is the post; the cure is the next four. PCA finds the directions in the 64-D space that actually carry variance, projects the data onto them, and discards the rest. The fix is a separate post because PCA itself has math worth understanding. Here is the proof that the fix works:

from sklearn.decomposition import PCA

pca2 = PCA(n_components=2)
X_2d = pca2.fit_transform(X_digits)
print(f"Explained variance (first 2 PCs): {pca2.explained_variance_ratio_.sum():.4f}")

pca_95 = PCA(n_components=0.95)
X_95 = pca_95.fit_transform(X_digits)
print(f"n_components for 95% variance:    {pca_95.n_components_} of 64")

Explained variance (first 2 PCs): 0.2862
n_components for 95% variance:    41 of 64

41 components retain 95% of the variance. The other 23 components contain 5% — mostly pixel noise. KNN on the 41-component representation outperforms KNN on all 64 raw features. Removing noise features helps the distance calculation; adding them destroys it. The next post walks through how PCA finds those 41 directions and why they capture the variance in the first place.

Related Concepts

Backward: the KNN experiments here build directly on the KNN section (posts 01–03) — specifically the distance-metric discussion. The curse of dimensionality is the failure mode that distance-based methods run into when the metric space becomes too sparse.

Forward: the next three posts are Feature Selection vs Extraction, PCA — Geometric + Math Intuition, and PCA — Eigen Decomposition. Together they answer the question this post opens: given that high dimensions break distance, how do you reduce the dimension without throwing away the structure? After those, the section moves to clustering (K-Means, Hierarchical, DBSCAN) — which uses the same distance metric KNN does, so the curse applies to all of them.

Honest Limitations

• The curse assumes uniform data. The volume and distance arguments are exact for points spread evenly across a hypercube. Real data — including the digits dataset — lives on low-dimensional manifolds inside the high-D space. The curse is still real (KNN still degrades with noise dimensions), but the formulas overstate how fast.
• The 5-fold CV variance matters. With 1,797 digits, each fold has ~360 test points. A 0.5% accuracy difference across folds is normal. The 96.8% → 34.1% drop is far above that noise floor, but smaller effects (say 96.8% → 92.3%) should be read with the fold-level standard deviation in mind.
• The fix has its own cost. PCA finds variance-maximizing directions, not label-discriminating directions. A projection that preserves 95% of variance does not necessarily preserve 95% of the information that KNN needs. The next post covers the geometric intuition behind this gap.

Test Your Understanding

1. The volume argument says: to capture 10% of data in 100D, the neighborhood must have $r=0.10^{1/100}=0.977$. But this assumes uniform data distribution. If all your data lives on a 2D manifold embedded in 100D space (e.g., the MNIST digits), does the curse of dimensionality apply in the same way? What does "intrinsic dimensionality" mean in this context?

2. The distance ratio $d_{\text{max}}/d_{\text{min}}$ → 1 as $d\to \infty$. This assumes random uniform points. For structured data (e.g., MNIST digits grouped by class), would the ratio stay high in high dimensions? What property of the data preserves meaningful distance contrast?

3. Adding 500 noise features reduced KNN accuracy from 96.8% to 34.1%. If instead you added 500 copies of the most informative feature (pixel[0]), would accuracy also degrade? Why might correlated high-dimensional data be worse or better than random noise for distance-based methods?

4. PCA to 41 components retains 95% of variance. The 23 dropped components contain 5% of variance. If those 23 components are pure noise, dropping them should improve KNN. If they contain 5% real signal, dropping them loses information. How would you determine which case applies for the digits dataset, without running KNN twice?

5. The required sample size table shows 10D needs $10^{10}$ samples. Real datasets with 10 features work fine with 1000 samples. What assumption in the $k^d$ formula breaks down in practice — and why does machine learning work at all in high dimensions if the curse is this severe?