14
$\begingroup$

I am looking to do k-means clustering on a set of 10-dimensional points. The catch: there are $10^{10}$ points.

I am looking for just the center and size of the largest clusters (let's say 10 to 100 clusters); I don't care about what cluster each point ends up in. Using k-means specifically is not important; I am just looking for a similar effect, any approximate k-means or related algorithm would be great (minibatch-SGD means, ...). Since GMM is in a sense the same problem as k-means, doing GMM on the same size data is also interesting.

At this scale, subsampling the data probably doesn't change the result significantly: the odds of finding the same top 10 clusters using a 1/10000th sample of the data are very good. But even then, that is a $10^6$ point problem which is on/beyond the edge of tractable.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Several algorithms are described in the book "Mining of Massive Datasets", which you can download for free here. Read Chapter 7 "Clustering". $\endgroup$
    – lanenok
    May 11 '15 at 12:42
12
$\begingroup$

k-means is based on averages.

It models clusters using means, and thus the improvement by adding more data is marginal. The error of the average estimation reduces with 1/sqrt(n); so adding more data pays off less and less...

Strategies for such large data always revolve around sampling:

If you want sublinear runtime, you have to do sampling!

In fact, Mini-Batch-Kmeans etc. do exactly this: repeatedly sample from the data set.

However, sampling (in particular unbiased sampling) isn't exactly free either... usually, you will have to read your data linearly to sample, because you don't get random access to individual records.

I'd go with MacQueen's algorithm. It's online; by default it does a single pass over your data (although it is popular to iterate this). It's not easy to distribute, but I guess you can afford to linearly read your data say 10 times from a SSD?

Improve this answer
$\endgroup$
1
  • $\begingroup$ I didn't know about MacQueen's online algorithm! Does it usually get the same results as "classic" K-means? What about using reservoir sampling instead? That way OP has a sample to re-run K-means on in case multiple values of K should be tested. $\endgroup$
    – Victor Ma
    May 15 '15 at 0:12
6
$\begingroup$

As a side comment note that using K-means for 10D data might end up in nowhere according to the curse of dimensionality. Of course it varies a bit according to the nature of the data but once I tried to determine the threshold in which K-Means starts behaving strange regarding the dimensionalty, I got something like 7D. After 7 dimensions it started to miss correct clusters (my data was manually generated according to 4 well-separated Gaussian distributions and I used MATLAB kmeans function for my little experiment).

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is possible and, of course, always dependent on the data. However, given that the poster has 10^10 (presumably independent) samples, it seems that 10 dimensions wouldn't be too big a problem here. $\endgroup$
    – Ryan J. Smith
    May 11 '15 at 18:03
  • 2
    $\begingroup$ Thanks for your comment @RyanJ.Smith. your comment is exactly in the same direction of mine. I just did not see anything regarding this problem in the post. And about the nr of samples; however he has many sample points he still might get stuck in the problem of dimensionality. I think you are arguing the opposite side of Low Sample Size Problem which I think is not valid. If he has a high dimensional data, low sample size will be a problem but I think a large amount of data does not necessarily mean anything. $\endgroup$
    – Kasra Manshaei
    May 11 '15 at 18:52
  • $\begingroup$ 10 dimensions are not a lot yet. $\endgroup$
    – Has QUIT--Anony-Mousse
    May 13 '15 at 7:51
  • 1
    $\begingroup$ How do you determine my friend? what I said was the result of an experiment designed to answer such a question however it CAN NOT be answered in general! What is "a lot" in your comment exactly? it depends on many circumstances as I mentioned in my answer. in some situations 10D could be problematic. $\endgroup$
    – Kasra Manshaei
    May 13 '15 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.