2
$\begingroup$

Are there clustering algorithms that take advantage of bootstrap?

For example can one combine bootstrap with a standard K-Means algorithm to scale K-Means.

I was thinking if the following at a high-level:

  1. Use bootstrap to create sub-samples from the elements that need to be clustered.
  2. Each of these sub-samples should be the size that K-Means scale
  3. K-Means each sub-sample in parallel
  4. Use the co-occurrence of elements in clusters to extract clusters from the larger population

Thanks.

$\endgroup$
6
$\begingroup$

If you're still interested in applying bootstrap approach to clustering, I would recommend you to read the following two excellent and IMHO relevant answers: one on applying bootstrapping to clustering (https://stats.stackexchange.com/a/11702/31372) and another on determining optimal number of clusters and more (https://stackoverflow.com/a/15376462/2872891). In addition to some fit measures, mentioned in the above-referenced answers, I'd also suggest to use AIC and/or BIC, as described in answers to this question, with more details here.

There is a significant amount of research literature on using bootstrapping in clustering (for example, see this and this). Despite being beyond my current knowledge level, interest and the scope of this answer, I would like to point to two specifically interesting resources. This paper on using bootstrapping for speeding up K-means clustering might be also of interest, but requires "manual" implementation. This blog post seems to me interesting and relevant to the topic as well.

As a side note, I would recommend you to take a look at an alternative (non-K-means) approach to clustering, called model-based clustering, as implemented in mclust R package. The approach, methods and software are described in the paper "mclust Version 4 for R: Normal Mixture Modeling for Model-Based Clustering, Classification, and Density Estimation" by Chris Fraley, Adrian E. Raftery, T. Brendan Murphy and Luca Scrucca: http://www.stat.washington.edu/research/reports/2012/tr597.pdf.

$\endgroup$
1
$\begingroup$

Usually, it will be good enough to run k-means on a single sample.

So yes, one can combine k-means with sampling, in two ways:

  1. run k-means on the sample, and use the result.

  2. run k-means on the sample, use the resulting centers, and continue on the full data set (which should usually converge within a small number of iterations now).

I'm not convinced that repeating the process with multiple samples is essential, or that performing a more complex sampling helps. It's a best practise to run it multiple times, and it may work well to use different samples then each time.

$\endgroup$

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.