# Streaming k-means

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.

• What do you mean by original kmeans? There is several slightly different classic versions of K-means algorithm and they give different results. – ttnphns Apr 8 '14 at 11:59
• @ttnphns I think they differ only in how to initialize centroids. Or something else? – mrgloom Apr 8 '14 at 12:13
• 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. – ttnphns Apr 8 '14 at 14:16

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?

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