30

Is there a online version of the k-Means clustering algorithm?

By online I mean that every data point is processed in serial, one at a time as they enter the system, hence saving computing time when used in real time.

I have wrote one my self with good results, but I would really prefer to have something "standardized" to refer to, since it is to be used in my master thesis.

Also, does anyone have advice for other online clustering algorithms? (lmgtfy failed ;))

Theodor
  • 5,536
  • 15
  • 41
  • 55

1 Answers1

42

Yes there is. Google failed to find it because it's more commonly known as "sequential k-means".

You can find two pseudo-code implementations of sequential K-means in this section of some Princeton CS class notes by Richard Duda. I've reproduced one of the two implementations below:

Make initial guesses for the means m1, m2, ..., mk
Set the counts n1, n2, ..., nk to zero
Until interrupted
    Acquire the next example, x
    If mi is closest to x
        Increment ni
        Replace mi by mi + (1/ni)*( x - mi)
    end_if
end_until

The beautiful thing about it is that you only need to remember the mean of each cluster and the count of the number of data points assigned to the cluster. Once you update those two variables, you can throw away the data point.

I'm not sure where you would be able to find a citation for it. I would start looking in Duda's classic text Pattern Classification and Scene Analysis or the newer edition Pattern Classification. If it's not there, you could try Chris Bishop's newest book or Daphne Koller and Nir Friedman's recent text.

qdjm
  • 1,033
  • 10
  • 14
  • Thank you. That made all the difference. – Theodor Sep 14 '10 at 08:55
  • 3
    The appropriate citation might actually be the MacQueen publication. He definitely includes this mean updating rule, and as far as I can tell, he does a single pass. Then you have exactly this algorithm. – Has QUIT--Anony-Mousse Feb 08 '12 at 18:31
  • I would suggest replacing "( x - mi)" by to make it clear that it is a distance measure. – Karthick Aug 16 '18 at 14:51
  • @HasQUIT--Anony-Mousse which MacQueen publication? – Rylan Schaeffer Apr 19 '21 at 17:46
  • @dww -- this replacement is not correct and updating the mean (or centroid) online is almost certainly not possible for every distance measure. – qdjm Apr 20 '21 at 19:18
  • 1
    @RylanSchaeffer The first one to use the name kmeans, cf [(ref)](https://datascience.stackexchange.com/questions/458/k-means-vs-online-k-means) – qdjm Apr 20 '21 at 19:21