7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – winwaed
    Feb 20, 2012 at 16:54

3 Answers 3

4
$\begingroup$

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$).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Consider using Dirichlet Process K-means original paper with implementation on github. The DP means algorithm creates new clusters as more data arrives. It doesn't require a prior knowledge of the number of clusters K. DP means is a Bayesian non-parametric extension of the K-means algorithm based on small variance asymptotics (SVA) approximation of the Dirichlet Process Mixture Model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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