How do I know my k-means clustering algorithm is suffering from the curse of dimensionality?

Question

I believe that the title of this question says it all.

Answer 1

It helps to think about what The Curse of Dimensionality is. There are several very good threads on CV that are worth reading. Here is a place to start: Explain “Curse of dimensionality” to a child.

I note that you are interested in how this applies to $k$-means clustering. It is worth being aware that $k$-means is a search strategy to minimize (only) the squared Euclidean distance. In light of that, it's worth thinking about how Euclidean distance relates to the curse of dimensionality (see: Why is Euclidean distance not a good metric in high dimensions?).

The short answer from these threads is that the volume (size) of the space increases at an incredible rate relative to the number of dimensions. Even $10$ dimensions (which doesn't seem like it's very 'high-dimensional' to me) can bring on the curse. If your data were distributed uniformly throughout that space, all objects become approximately equidistant from each other. However, as @Anony-Mousse notes in his answer to that question, this phenomenon depends on how the data are arrayed within the space; if they are not uniform, you don't necessarily have this problem. This leads to the question of whether uniformly-distributed high-dimensional data are very common at all (see: Does “curse of dimensionality” really exist in real data?).

I would argue that what matters is not necessarily the number of variables (the literal dimensionality of your data), but the effective dimensionality of your data. Under the assumption that $10$ dimensions is 'too high' for $k$-means, the simplest strategy would be to count the number of features you have. But if you wanted to think in terms of the effective dimensionality, you could perform a principle components analysis (PCA) and look at how the eigenvalues drop off. It is quite common that most of the variation exists in a couple of dimensions (which typically cut across the original dimensions of your dataset). That would imply you are less likely to have a problem with $k$-means in the sense that your effective dimensionality is actually much smaller.

A more involved approach would be to examine the distribution of pairwise distances in your dataset along the lines @hxd1011 suggests in his answer. Looking at simple marginal distributions will give you some hint of the possible uniformity. If you normalize all the variables to lie within the interval $[0,\ 1]$, the pairwise distances must lie within the interval $[0,\ \sqrt{\sum D}]$. Distances that are highly concentrated will cause problems; on the other hand, a multi-modal distribution may be hopeful (you can see an example in my answer here: How to use both binary and continuous variables together in clustering?).

However, whether $k$-means will 'work' is still a complicated question. Under the assumption that there are meaningful latent groupings in your data, they don't necessarily exist in all of your dimensions or in constructed dimensions that maximize variation (i.e., the principle components). The clusters could be in the lower-variation dimensions (see: Examples of PCA where PCs with low variance are “useful”). That is, you could have clusters with points that are close within and well-separated between on just a few of your dimensions or on lower-variation PCs, but aren't remotely similar on high-variation PCs, which would cause $k$-means to ignore the clusters you're after and pick out faux clusters instead (some examples can be seen here: How to understand the drawbacks of K-means).

Answer 2

My answer is not limit to K means, but check if we have curse of dimensionality for any distance based methods. K-means is based on a distance measure (for example, Euclidean distance)

Before run the algorithm, we can check the distance metric distribution, i.e., all distance metrics for all pairs in of data. If you have $N$ data points, you should have $0.5\cdot N\cdot(N-1)$ distance metrics. If the data is too large, we can check a sample of that.

If we have the curse of dimensionality problem, what you will see, is that these values are very close to each other. This seems very counter-intuitive, because it means every one is close or far away from every one and distance measure is basically useless.

---

Here is some simulation to show you such counter-intuitive results. If all of the features are uniformly distributed, and if there are have too many dimensions, every distance metrics should be close to $\frac 1 6$, which comes from $\int_{x_i=0}^1\int_{x_j=0}^1 (x_i-x_j)^2 dx_i dx_j$. Feel free to change the uniform distribution to other distributions. For example, if we change to normal distribution (change runif to rnorm), it will converge to another number with large number dimensions.

Here is the simulation for dimension from 1 to 500, the features are uniform distribution from 0 to 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}