# Online clustering

I'm trying to build a K-means clustering system with 'online learing', that is, there are existing K clusters and data points in them, and periodically there is a new data point that is sent to an appropriate cluster.

The problem is occuring when I try to reclusterize/redistribute, as it becomes increasingly expensive with each new datapoint. Can someone recommend a workaround for this?

-
Many of the optimizations available optimize the choice of initial locations. This is not much use for your application. However when trying to optimize K-means with a profiler, I found by far the biggest improvements were gained by heavily optimizing my distance calculation. I was working on the Earth's surface and was able to unwrap some of the trigonometry. –  winwaed Feb 20 '12 at 16:54

Within the sofia-ml package there is code for fast k-means clustering based on mini-batches (see paper here). The other thing you can do to speed things up is use Random Projections (see e.g. here and here) - since in k-means all you are interested in is $\ell_2$ distances, and random projections preserve these (up to some $\epsilon$).

-