Rethinkingk-means clustering in the age of massive datasets: a constant-time approach

摘要

We introduce a highly efficientk-means clustering approach. We show that the classical central limit theorem addresses a special case (k = 1) of thek-means problem and then extend it to the general case. Instead of using the full dataset, our algorithm namedk-means-lite applies the standardk-means to the combinationC(sizenk) of all sample centroids obtained fromnindependent small samples. Unlike ordinary uniform sampling, the approach asymptotically preserves the performance of the original algorithm. In our experiments with a wide range of synthetic and real-world datasets,k-means-lite matches the performance ofk-means whenCis constructed using 30 samples of size 40 + 2k. Although the 30-sample choice proves to be a generally reliable rule, when the proposed approach is used to scalek-means++ (we call this scaled versionk-means-lite++),k-means++' performance is matched in several cases, using only five samples. These two new algorithms are presented to demonstrate the proposed approach, but the approach can be applied to create a constant-time version of any otherk-means clustering algorithm, since it does not modify the internal workings of the base algorithm.