K-Means-Lite: Real Time Clustering for Large Datasets

We present a simple algorithm to address the poor scalability of k-means, arguably the most popular clustering algorithm. Our algorithm, named k-means-lite, is based on an intuitive extension of the classical central limit theorem. It obtains the k centroids which k-means seeks, by making inference from a few small samples, rather than by repeated exhaustive comparison of data points and centroids. Experiments show that, compared to k-means, k-means-lite achieves drastic efficiency gain, and solves large datasets (up to 1 million points tested) in real time. The efficiency gain is increasingly manifest as data size and number of clusters increase. Interestingly, k-means-lite also produces better clustering quality than k-means on the largest 7 of 10 datasets tested.