0

I write a Java code to cluster a huge dataset which has about 100000rowsx100000columns(sparse rows). But dataset is created with sparse instances, so it has the structure of a sparse matrix.

I can use 3 clustering functions in my code:

JavaML: Kmeans, Weka: SimpleKmeans, Weka: Xmeans

I have run Weka's SimpleKmeans function but it is working about 9 hours and clustering process in not over yet. What is the estimated running time of these functions and which one is the most suitable for this dataset best?

JoshuaJeanThree
  • 1,382
  • 2
  • 22
  • 41
  • See also: http://stackoverflow.com/questions/3039646/k-means-clustering-in-r-on-very-large-sparse-matrix http://stackoverflow.com/questions/3177827/clustering-on-very-large-sparse-matrix – Has QUIT--Anony-Mousse Nov 13 '12 at 07:46

1 Answers1

1

K-means is not appropriate for sparse data.

The reason is that the means will not be sparse, and as such, the means will actually be anomalous for your data set. Even worse: the distance between the means will likely be smaller than the distances from the instances to the means.

You will get some result at some point - Weka is horribly slow, you might want to look for something faster; for this data set size you might want to go for Mahout which is distributed (but judging from the questions here, has other issues). IIRC it also has an acceleration trick for sparse vectors, by precomputing the euclidean length - but nevertheless, the result will likely be not meaningful.

The problem is that K-means looks for an optimal Voronoi cell partitioning. But your data set, when sparse, will likely not have a natural Voronoi cell structure. So you spend a lot of time of finding an optimal structure that your data cannot have.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194