|
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? |
||||
|
|
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$). |
|||
|
|
|
Read the original k-means literature. The MacQueen publication was based on updating the result by adding single points. Most people nowerdays seem to use Lloyd iteratation, where you do the typical EM iterations, somewhat a "bulk version" of MacQueen. |
|||
|
|
