Skip to main content
2 of 5
added 132 characters in body
Haitao Du
  • 37.3k
  • 25
  • 148
  • 244

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*N*(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 your features are uniform distribution, and if you have too many dimensions, every distance should be close to $\frac 1 6$.

Here is the simulation for dimension from 1 to 500, every feature is uniform.

enter image description here

Haitao Du
  • 37.3k
  • 25
  • 148
  • 244