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$
  • $\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 '12 at 16:54
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$).

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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