A Caltech Library Service

Clustering Oligarchies

Ackerman, Margareta and Ben-David, Shai and Loker, David and Sabato, Sivan (2013) Clustering Oligarchies. Proceedings of Machine Learning Research, 31 . pp. 66-74. ISSN 1938-7228.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We investigate the extent to which clustering algorithms are robust to the addition of a small, potentially adversarial, set of points. Our analysis reveals radical differences in the robustness of popular clustering methods. k-means and several related techniques are robust when data is clusterable, and we provide a quantitative analysis capturing the precise relationship between clusterability and robustness. In contrast, common linkage-based algorithms and several standard objective-function-based clustering methods can be highly sensitive to the addition of a small set of points even when the data is highly clusterable. We call such sets of points oligarchies. Lastly, we show that the behavior with respect to oligarchies of the popular Lloyd’s method changes radically with the initialization technique.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2013 by the authors.
Record Number:CaltechAUTHORS:20200221-124858095
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101460
Deposited By: Tony Diaz
Deposited On:21 Feb 2020 20:56
Last Modified:21 Feb 2020 20:56

Repository Staff Only: item control page