An Algorithm for Online K-Means Clustering

摘要

This paper shows that one can be competitive with the k-means objective while operating online. In this model, the algorithm receives vectors v_1, ..., v_n one by one in an arbitrary order. For each vector v_t the algorithm outputs a cluster identifier before receiving v_(t+1). Our online algorithm generates O(k log n log γn) clusters whose expected k-means cost is O(W~* log n). Here, W~* is the optimal k-means cost using k clusters and γ is the aspect ratio of the data. The dependence on γ is shown to be unavoidable and tight. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.