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

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

• I think you are going to have to clarify for us what you mean by a symptom. – mdewey Aug 30 '16 at 14:32
• If "symptom" is a hand-waivery version of "test", then perhaps you could take subsamples of your dataset -- perhaps 66% of the sample size, perform your analysis (kmeans, in your case), and then see how jumpy the results are. For example, you could see how often particular observations are assigned to the same cluster. Then again, it might not be worth the effort. If you're worried about the possibility of a dimensionality problem, chances are you have one. You might consider other clustering approaches that reduce dimensionality somewhat. – generic_user Aug 30 '16 at 14:40
• @generic_user if that comment were an answer, I would count it as an accepted answer :) – mathieu Aug 30 '16 at 16:47
• This question is clear enough to remain open, IMO. – gung - Reinstate Monica Aug 30 '16 at 17:28
• Often enough, you run into much more severe problems of k-means earlier than the "curse of dimensionality". k-means can work on 128 dimensional data (e.g. SIFT color vectors) if the attributes are good natured. To some extent, it may even work on 10000-dimensional text data sometimes. The theoretical model of the curse never holds for real data. The larger problems are incomparable features, sparsity, and inability to visualize and double-check the result. – Has QUIT--Anony-Mousse Aug 31 '16 at 22:04

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).

• It turns out there is already a tag for manifold learning (should have looked first!). To summarize for those who may not know, the idea is that while high-dimensional data tends to be sparse in terms of the whole space, it may be dense on some hypersurface within that space. – GeoMatt22 Aug 31 '16 at 13:43
• +1 for the excellent answer. Could you please elaborate a bit more on the eigenvalues part? If the effective dimensionality is small then do you recommend doing PCA and retain only first few scores with high eigenvalues? – DataD'oh Aug 25 '17 at 14:29
• @DataD'oh, that's certainly one possibility, but what I'm saying is that you needn't do that. In effect, the data aren't high-dimensional (when only the first few eigenvectors have high eigenvalues), so you don't necessarily need to do anything--the curse of dimensionality just won't apply. – gung - Reinstate Monica Aug 26 '17 at 1:15
• @gung I have posted a new question. I hope it is not too trivial. – DataD'oh Aug 28 '17 at 6:20

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))
}


• What is $P$?$\,$ – amoeba says Reinstate Monica Aug 30 '16 at 19:05
• I had upvoted because of a demonstration of the euclidean shrinkage phenomenon under high dimensions. But the answer doesn't demonstrate a suffering of k-means clustering from the curse. The suffering would imply that in high dimensions reasonably well separated clusters (and not uniform random data like yours) may fail to be uncovered as succesfully as it is in low dimensions. You didn't touch this topic. – ttnphns Aug 30 '16 at 21:53
• @amoeba $P$ is number of dimensions. I will review the plot and add the code. Thanks. – Haitao Du Aug 31 '16 at 1:35
• @ttnphns thanks for your comment and upvote. I will see If I can add one paragraph to discuss the impact on k means. – Haitao Du Aug 31 '16 at 1:37