Clustering high dimensional data

Question

I was going through this wiki page on clustering in high dimensions and I don't understand the following statement there. Can someone explain to me what this means?

The concept of distance becomes less precise as the number of dimensions grows, since the distance between any two points in a given dataset converges. The discrimination of the nearest and farthest point in particular becomes meaningless

Answer 1

This refers to the curse of dimensionality, which has its own Wikipedia page.

I don't think this claim is completely correct: distances do not "converge" for clusters. The classic distance form of the curse assumes that all data is from the same distribution. Once points come from different clusters, the "concentration" is false.

Don't rely on Wikipedia too much.

Answer 2

This statement says that as dimensionality goes beyond all boundaries, the distance between any pair of points becomes almost the same for all pairs of points. In other words, as dimensionality increases, it gets harder to distinguish between points based on distance.

For example, let's have $n = 10$ number of points and let points be tuples of $d$ real numbers taken uniformly and independently from $[0,1]$. This means we have a set of $n$ tuples of length $d$, which can be represented with $n \times d$ matrix. Now let's take the Euclidean distance and calculate discrimination power, defined by: $$ \frac{dist_{\max}(d) - dist_{\min}(d)}{dist_{\min}(d)}, $$ where $dist_{\max}$ is the maximum distance between any pair of points and $dist_{\min}$ is the minimum distance between any pair of points. In R code:

set.seed(pi)
n <- 10 # number of data points (observations)
d_max <- 1000 # max dimension
dist1 <- rep(0, d_max)
disc <- rep(0, d_max)
for (d in 1:d_max) {
  A <- matrix(runif(n*d), nrow=n, ncol=d)
  distances <- as.vector(dist(A))
  disc[d] <- ( max(distances) - min(distances) )/min(distances)
}
plot(11:d_max, disc[11:d_max], xlab = "d", 
     ylab = "(dist_max - dist_min) / dist_min", pch = 19)

We can see from the Figure below, that as $d$ increases the discrimination power decreases:

(Here we removed the first 10 values from the plot because they were too high and this makes the plot clearer.)

For $d = 1000$ distances between points:

 [1] 12.90191 12.97374 12.89478 13.13179 12.52021 13.12185 13.13992 12.74864 12.94139 12.93830 12.93154 12.82812 13.24305 12.78545 12.94532 12.82877 13.22162 [18] 12.86434 12.58688 13.16338 12.84874 13.05939 12.87777 12.85084 12.30536 12.68565 13.03605 13.31366 12.37667 12.90180 12.97520 12.62158 12.89200 13.08616 [35] 12.70571 13.13252 12.88714 12.75688 12.84972 12.94311 12.67934 12.84256 13.28620 13.05672 12.87923

are all close to 12.9.