1
$\begingroup$

I want to perform something like streaming/online/out-of-core kmeans clustering on large data.

Here is simple idea:

  1. Break all data into N chunks.

  2. Read from disk 1st chunk and calculate centroids using original kmeans algorithm.

  3. Use centroid of previous chunk to initialize next chunk centroids.

  4. Do steps 2-3 N times.

But how it will differ from original kmeans clustering by result? Maybe I can improve it somehow?

Also I found mini batch kmeans but it seems it can't work with large data.

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean by original kmeans? There is several slightly different classic versions of K-means algorithm and they give different results. $\endgroup$
    – ttnphns
    Commented Apr 8, 2014 at 11:59
  • $\begingroup$ @ttnphns I think they differ only in how to initialize centroids. Or something else? $\endgroup$
    – mrgloom
    Commented Apr 8, 2014 at 12:13
  • $\begingroup$ Something else. On each iteration, centroids might be recomputed a) after all N objects are assigned to their clusters or b) immediately after each object is assigned. So, in streaming situation, you ought to decide how "often" the cntroids recomputation pass takes place. $\endgroup$
    – ttnphns
    Commented Apr 8, 2014 at 14:16

2 Answers 2

Reset to default
2
$\begingroup$

The k-means publication by MacQueen,

MacQueen, J. B. (1967).
"Some Methods for classification and Analysis of Multivariate Observations".
Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 2009-04-07.

is a streaming algorithm. It processes one element at a time.

In particular, it discusses the incremental update formula for the centroids (which is fairly simple).

Have you tried it?

Improve this answer
$\endgroup$
1
$\begingroup$

Just to add to the previous answer that the streaming algorithm in the cited paper is also known as "Sequential K-means". It doesn't need any iteration over the whole dataset but the results can be substantially different from the well-known K-means. Moreover, if you don't know (guess) the number of clusters K and are still interested in a streaming algorithm that derives from K-means and that doesn't need to loop over the whole dataset, let me suggest two publications:

J. Hensman, R. Pullin, M. Eaton, K. Worden, K. M. Holford and S. L. Evans, Detecting and identifying artificial acoustic emission signals in an industrial fatigue environment, http://dx.doi.org/10.1088/0957-0233/20/4/045101

E. Pomponi, A. Vinogradov, A real-time approach to acoustic emission clustering, Mech. Syst. Signal Process. (2013), http://dx.doi.org/10.1016/j.ymssp.2013.03.017

The former describes the online radius-based clustering algorithm (ORACAL) and the latter the Adaptive Sequential K-means (ASK) algorithm, two interesting variations of the standard Sequential K-means (i.e. MacQueen 1967)

Disclaimer: I'm the co-author of the second one

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.