0
$\begingroup$

I am working with a large dataset containing about 500 million records and about 50 discrete dimensions. I am planning to cluster these records into a number of distinct clusters (~30). Now, every day, for a number of these records, some dimensions will change. Given that the initial clustering will take quite a bit of time, I am looking for a way to avoid running complete reclustering every day, in order to accomodate for changed records. I suppose that in most cases, for an algorithm that permits it, starting the run from previous converged solution would allow convergence to a new solution in hopefully only few iteration.

Is there a specific algorithm (preferably one that allows membership in multiple clusters) that would be useful in this case, or a trick that can help me avoid full recalculation?

Improve this question
$\endgroup$
2
  • $\begingroup$ I would need some more details about your problem to say for sure, but many clustering algorithms do their clustering based on the distance between items. If that's how clustering will work here. The easiest way it probably to just save the distance matrix between runs. When data points change, you can recalculate the distance between the $m << n$ points that change with all $n$ points. If you use a clustering algorithm like $k$-means, you can initialize today's clustering with yesterday's centroids to speed it up. $\endgroup$
    – Ben
    Commented Oct 14, 2015 at 13:33
  • $\begingroup$ Can you define "some" dimensions? How many are you talking about? Also, you can simplify your life by taking samples of the 500 million records and projecting results to the remainder. This would also afford an opportunity to cross-validate the results in terms of classification (or misclassification)... $\endgroup$
    – user78229
    Commented Oct 14, 2015 at 13:33

1 Answer 1

Reset to default
0
$\begingroup$

Any iterative algorithm like k-means or GMM will allow you to just recycle the previous result and continue where you left off.

For k-means, mini-batch k-means doesn't even use all your data, but repeatedly draws a sample and does a few iterations. It will never "converge", but if you do a dozen iterations every day, your result will be as good as k-means is (which is not very good, unfortunately).

You could do the same with GMM if you don't want binary cluster membership.

Improve this answer
$\endgroup$

Your Answer

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

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