What should be the optimum number of features for 10 million observations for kmeans clustering?

Question

I have a dataset of 10 million observations and 100 million features. I have to perform kmeans clustering on that dataset. The approx value of k is 30000

Is it advisable to perform clustering with such huge number of features? What are the problems I may face using such huge number of features? (Currently, I am facing OutofMemory in Spark mllib kmeans)

Wouldn't it be better to perform PCA reduce the number of features or feature-vectors are re-engineered in such a way that it contains less number of features? What should be the ideal number of features? Is there any doc on high dimensionality and kmeans?

Answer 1

Any algorithm that relies on a distance metric in a high-dimensional space will suffer from the curse of dimensionality. In effect, all your observations are going to appear "far" from one another, with relatively little variation in the distance measurement, making the clustering very weak. You'd be much better off selecting informative features, and using only those to construct your distance metric for k-means. The ideal number of features is very much problem dependent, so there's no set guideline on a pre-defined number.

Answer 2

Performing PCA before Kmeans clustering is an acceptable practice. The number of features for your number of samples is quite high and I guess many of them are correlated. I would give PCA a try.

Just change your number of PCA components and see how much of the variance is explained (maybe try n_components = [100,1000,10000]). Once you are happy with the number of components, experiment with the number of kmeans clusters and draw the entropy plot and find the elbow point.

Kmeans and PCA are both unsupervised and need manual experimentation.