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