Please, could someone recommend a paper or blog post that describes the online k-means algorithm.

  • $\begingroup$ Your question is very weak, since you are neither presenting any problem, nor trying to understand something specific. Asking for comparisons between online/batch k-means, or for how to efficiently implement some part of the algorithm is ok; asking for simple descriptions is too broad -- a google search may be a better fit. $\endgroup$ – Rubens Jun 22 '14 at 16:56
  • $\begingroup$ @Rubens I'm asking for a recommendation so what's wrong about that ?, I already googled it but I couldn't find something useful. $\endgroup$ – Abdelmawla Jun 22 '14 at 17:27
  • $\begingroup$ This question appears to be off-topic because Data Science Stack Exchange is not a link recommendation service. Please use Google for basic information and tutorials. $\endgroup$ – asheeshr Jun 26 '14 at 1:41

The original MacQueen k-means publication (the first to use the name "kmeans") is an online algorithm.

MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations". Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1. University of California Press. pp. 281–297

After assigning each point, the mean is incrementally updated.

As far as I can tell, it was also meant to be a single pass over the data only, although it can be trivially repeated multiple times to reassign points until convergence.

MacQueen usually takes fewer iterations than Lloyds to converge if your data is shuffled. On ordered data, it can have problems. On the downside, it requires more computation for each object, so each iteration takes slightly longer.

When you implement a parallel version of k-means, make sure to study the update formulas in MacQueens publication. They're useful.


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