Answer

Why Euclidean distance breaks down in high dimensions

Inspired by a question on Cross Validated · October 29, 2026

clusteringpcaclassification

What actually goes wrong: distances concentrate

Euclidean distance itself does not stop being a valid distance in many dimensions. The problem is that it stops telling points apart. Take a cloud of points and a reference point. In two dimensions, the nearest point may be fifty times closer than the farthest. Add more and more features of the same kind, and the ratio of nearest to farthest distance creeps towards 1. Once every point is roughly the same distance from every other, 'my nearest neighbour' and 'a random point' mean almost the same thing.

This is usually called the concentration of distances, one face of the curse of dimensionality. Anything built on ranking distances inherits it: hierarchical and k-means clustering, k-nearest-neighbour classification, kernel methods with a distance inside, and outlier detection based on how isolated a point is.

Why it happens

A squared Euclidean distance is a sum with one term per feature. If the features vary more or less independently, that sum behaves like any sum of many random pieces: its average grows in proportion to the number of features d, while its spread grows only like the square root of d. Taking the square root to get the distance itself, the typical distance grows roughly like the square root of d, but the standard deviation of the distances levels off at a constant. Relative to its size, the variation in distances therefore shrinks towards zero.

Put plainly, each extra feature adds about the same amount to every distance, and those shared additions swamp the few features where points genuinely differ. This is the same reason a sample mean steadies as the sample grows (see the central limit theorem page), only here the 'sample' is the list of per-feature differences.

Two conditions drive the effect, and both matter for real data. The features must be fairly independent, and many of them must be unrelated to the structure you care about. When features are strongly correlated, the data really live in far fewer dimensions than the column count, and distances keep much more of their contrast.

So how many features is too many?

There is no threshold, such as 10 or 100, above which Euclidean distance becomes unsafe. What matters is the ratio of signal to noise across features:

• Intrinsic dimension. One hundred measurements that mostly reflect three underlying traits behave like a three-dimensional data set with some noise. One hundred unrelated measurements behave like a genuinely 100-dimensional one.
• Share of uninformative features. If the groups differ on 2 features and the other 98 are noise, the noise contributes most of every distance and blurs the groups. If most features carry the group difference, distances stay informative even when there are many of them.
• Scaling. Euclidean distance adds raw squared differences, so a feature measured on a large numeric scale dominates. Standardize when the features are in different units (see how to normalize data).

A practical check for your own 100-feature clustering is to compute the distances and look at them. If the histogram of pairwise distances is a narrow spike far from zero, or the nearest-to-farthest ratio for typical points is close to 1, the distances are not discriminating much. Also check whether the clusters are stable when you resample cases or drop a random subset of features.

What to do about it

• Reduce dimension first. Cluster on the first few principal components or factor scores rather than all raw features (PCA explained). This discards directions that are mostly noise.
• Select features. Drop variables that you have no reason to think separate the groups. Fewer, relevant features beat many weak ones.
• Consider another distance. Manhattan (L1) distance loses contrast somewhat more slowly than Euclidean in theory, and correlation or cosine distance suits data where the profile shape matters more than its level. None of these escapes concentration if most features are noise.
• Use methods built for the setting. Model-based clustering on reduced data, or sparse clustering methods that weight features, are designed for many-variable problems.

The same issues apply to k-means, which also measures closeness with Euclidean distance.

See it in R and Python

Part 1 draws 500 points uniformly in a cube of dimension d and measures their distance to one random query point. Part 2 builds two groups of 100 that differ by 3 units on two features, then adds pure-noise features and checks how often each point's nearest neighbour is from its own group, and how well Ward hierarchical clustering recovers the groups. R uses base functions; Python uses NumPy and SciPy.

set.seed(99171)
# 1. Distance concentration: 500 random points in the unit cube, one query point
for (d in c(2, 10, 100, 1000)) {
  x <- matrix(runif(500 * d), ncol = d)
  q <- runif(d)
  dist_q <- sqrt(colSums((t(x) - q)^2))       # Euclidean distance to the query
  cat(sprintf("d = %4d  mean = %6.2f  SD = %.3f  nearest/farthest = %.3f  contrast = %.3f\n",
              d, mean(dist_q), sd(dist_q), min(dist_q) / max(dist_q),
              (max(dist_q) - min(dist_q)) / min(dist_q)))
}

# 2. Signal plus noise: two groups differ on 2 features; add pure-noise features
n <- 200
grp <- rep(1:2, each = n / 2)
signal <- cbind(rnorm(n, ifelse(grp == 1, 0, 3)), rnorm(n, ifelse(grp == 1, 0, 3)))
for (p in c(0, 10, 100, 1000)) {
  x <- if (p == 0) signal else cbind(signal, matrix(rnorm(n * p), ncol = p))
  dm <- as.matrix(dist(x))                    # Euclidean distances
  diag(dm) <- Inf
  nn <- apply(dm, 1, which.min)               # each point's nearest neighbour
  hc <- cutree(hclust(dist(x), method = "ward.D2"), k = 2)
  agree <- mean(hc == grp); agree <- max(agree, 1 - agree)
  cat(sprintf("noise features = %4d  nearest neighbour in same group = %.3f  hclust agreement = %.3f\n",
              p, mean(grp[nn] == grp), agree))
}

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.cluster.hierarchy import linkage, fcluster

rng = np.random.default_rng(99171)

# 1. Distance concentration: 500 random points in the unit cube, one query point
for d in [2, 10, 100, 1000]:
    x = rng.uniform(size=(500, d))
    q = rng.uniform(size=d)
    dist_q = np.sqrt(((x - q) ** 2).sum(axis=1))   # Euclidean distance to the query
    print(f"d = {d:4d}  mean = {dist_q.mean():6.2f}  SD = {dist_q.std(ddof=1):.3f}  "
          f"nearest/farthest = {dist_q.min() / dist_q.max():.3f}  "
          f"contrast = {(dist_q.max() - dist_q.min()) / dist_q.min():.3f}")

# 2. Signal plus noise: two groups differ on 2 features; add pure-noise features
n = 200
grp = np.repeat([1, 2], n // 2)
mu = np.where(grp == 1, 0.0, 3.0)
signal = np.column_stack([rng.normal(mu, 1), rng.normal(mu, 1)])
for p in [0, 10, 100, 1000]:
    x = signal if p == 0 else np.hstack([signal, rng.normal(size=(n, p))])
    dm = squareform(pdist(x))                      # Euclidean distances
    np.fill_diagonal(dm, np.inf)
    nn = dm.argmin(axis=1)                         # each point's nearest neighbour
    hc = fcluster(linkage(x, method="ward"), t=2, criterion="maxclust")
    agree = np.mean(hc == grp)
    agree = max(agree, 1 - agree)
    print(f"noise features = {p:4d}  nearest neighbour in same group = {np.mean(grp[nn] == grp):.3f}  "
          f"hclust agreement = {agree:.3f}")

d =    2  mean =   0.57  SD = 0.269  nearest/farthest = 0.018  contrast = 53.634
d =   10  mean =   1.27  SD = 0.229  nearest/farthest = 0.287  contrast = 2.481
d =  100  mean =   4.01  SD = 0.231  nearest/farthest = 0.712  contrast = 0.404
d = 1000  mean =  13.04  SD = 0.216  nearest/farthest = 0.909  contrast = 0.100
noise features =    0  nearest neighbour in same group = 1.000  hclust agreement = 0.985
noise features =   10  nearest neighbour in same group = 0.970  hclust agreement = 0.970
noise features =  100  nearest neighbour in same group = 0.915  hclust agreement = 0.935
noise features = 1000  nearest neighbour in same group = 0.655  hclust agreement = 0.690

The output above is from one seeded run of the R code. Python uses a different random number generator, so its figures differ slightly, but they show the same pattern.

• Concentration. The average distance climbs from 0.57 to 13.04 as d goes from 2 to 1000, but the SD of the distances stays between about 0.22 and 0.27. The nearest point goes from 0.018 of the farthest distance to 0.909 of it, and the relative contrast (farthest minus nearest, divided by nearest) falls from 53.6 to 0.10.
• Noise dilutes structure. With only the two informative features, every point's nearest neighbour is in its own group and Ward clustering recovers 98.5% of the labels. With 100 noise features, the nearest neighbour still matches 91.5% of the time and clustering recovers 93.5%. With 1000 noise features, these drop to 65.5% and 69.0%, not far above the 50% you would get by chance.

The second part is the more useful lesson: 100 features did not ruin the analysis, but adding enough features that carry no group information did. If you want to compare the clusters you find on other variables afterwards, the test chooser can help pick the test.

How to report a cluster analysis in APA style (7th edition)

In the method section, name the distance measure, say whether and how variables were standardized, describe any dimension reduction or feature selection done before clustering, and give the linkage method, software and rule for choosing the number of clusters. Using the 100-noise-feature example above, where the true groups were known:

"Cases (N = 200) were clustered on all 102 features using Euclidean distance and Ward's linkage (R hclust, method ward.D2). The two-cluster solution placed 93.5% of cases in their known group."

With real data and no known groups, replace the last sentence with the cluster sizes and a stability or fit index, for example "The two clusters (n = xx and n = xx) had an average silhouette width of x.xx." Give cluster means on each variable in a table.

Related tools and guides

• Which statistical test should I use?
• K-means clustering: assumptions and drawbacks
• PCA, eigenvectors and eigenvalues explained
• Curse of dimensionality (Wikipedia)

More answered questions

• Does k-means make assumptions? Its drawbacks explained
• Factor analysis vs PCA: what is the difference?
• Why is accuracy a poor way to judge a classification model?

Written by AskStats with AI assistance. This is general information, not advice for your specific data or study. When the results matter, check your approach with a qualified statistician.