Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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.
