An Algorithm for Online K-Means Clustering

By Edo Liberty, Ram Sriharsha, Maxim Sviridenko. 2014

109 citations recorded by the source corpus.

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 the algorithm outputs a cluster identifier before receiving the next one. Our online algorithm generates ~O(k) clusters whose k-means cost is ~O(W*). Here, W* is the optimal k-means cost using k clusters and ~O suppresses poly-logarithmic factors. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Memory Efficient Experience Replay for Streaming Learning (2018, methodology): “2) Online k-means: This is a partitioning-based heuristic for an online variant of the traditional k-means clustering algorithm [49].”
K-variates++: More Pluses in the K-means++ (2016, methodology): “…extending k-means clustering to these settings has been a major research area in recent years, there has been no obvious solution to tailoring kmeans++ (Ackermann et al., 2010; Ailon et al., 2009; Bahmani et al., 2012; Balcan et al., 2013; Liberty et al., 2014; Shindler et al., 2011) (and others).”