.png){kind=icon}
.png){kind=icon}
Return
Optimal time bounds for approximate clustering
.png){kind=icon}
OA
AI
DOI：10.1023/B:MACH.0000033114.18632.e0.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Clustering 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 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 Omega(nk) on any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible (say 1/100) probability. The best previous upper bound for the problem was (O) over tilde (nk), where the (O) over tilde -notation hides polylogarithmic factors in n and k. The best previous lower bound of Omega(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.
Keywords:
k-means
k-median
unsupervised clustering
approximation algorithms
discrete location theory
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
2.6K
Citations:
3.4W
Organization
No organization information available