Optimal Time Bounds for Approximate Clustering

By Ramgopal R. Mettu, Greg Plaxton. 2002

125 citations recorded by the source corpus.

AbstractClustering is a fundamental problem in unsupervised learning, and has been studied widely both as a problem of learning mixture models and as an optimization problem. In this paper, we study clustering with respect to the k-median objective function, a natural formulation of clustering in which we attempt to minimize the average distance to cluster centers. One of the main contributions of this paper is a simple but powerful sampling technique that we call successive sampling that could be of independent interest. We show that our sampling procedure can rapidly identify a small set of points (of size just O( $$k \log \frac{n}{k}$$ )) that summarize the input points for the purpose of clustering. Using successive sampling, we develop an algorithm for the k-median problem that runs in O(nk) time for a wide range of values of k and is guaranteed, with high probability, to return a solution with cost at most a constant factor times optimal. We also establish a lower bound of Ω(nk) on any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible (say $$\frac{1}{{100}}$$ ) probability. The best previous upper bound for the problem was Õ(nk), where the Õ-notation hides polylogarithmic factors in n and k. The best previous lower bound of Ω(nk) applied only to deterministic k-median algorithms. While we focus our presentation on the k-median objective, all our upper bounds are valid for the k-means objective as well. In this context our algorithm compares favorably to the widely used k-means heuristic, which requires O(nk) time for just one iteration and provides no useful approximation guarantees.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Proportionally Fair Clustering (2019, methodology): “Minimizing the k-median objective without proportionality is a well studied problem in approximation algorithms, and several constant approximations are known [8, 2, 29].”
On coresets for k-means and k-median clustering (2004, methodology): “The fastest known algorithm is due to Mettu and Plaxton [29] who give an algorithm which runs in O(n(k +log n)) time for small enough k given the distances are bound by 2O(n/ log(n/k)) .”
Clustering Data Streams: Theory and Practice (2003, background): “…abundant literature on these, books [45], [62], [55], provable algorithms [41], [49], [54], [53], [71], [31], [16], [15], [6], [52], [47], [14], [59], [7], [46], the running time of provable clustering heuristics [21], [10], [42], [34], [73], [60], and special metric spaces [6], [52], [43], [68].”
The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2006, methodology): “There are also various constantfactor approximation algorithms for the related k-median problem [26, 7, 6, 25, 37], which also yield approximation algorithms fork-means, and have running time polynomial in n, k and the dimension; recently Kanungo et al.”
Smaller Coresets for k-Median and k-Means Clustering (2005, methodology): “Alternative titles for this paper include “Finding Space/Time Stream Coresets” and “Improved Homeland Security using Grid Computing via Mobile ad-hoc Trustable Coresets”.”
A local search approximation algorithm for k-means clustering (2002, methodology): “This includes the work of Thorup on solving location problems in sparse graphs [40] and by Mettu and Plaxton [33] on the use of successive swapping for the metric k-means problem.”
Smooth sensitivity and sampling in private data analysis (2007, background): “It is NP-hard, in general, to find the optimal clustering of a data set but there exist ecient O(1) approximation algorithms (e.g., [ 14 ]).”