Clustering Oligarchies
Abstract
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.
Additional Information
© 2013 by the authors.Attached Files
Published - ackerman13a.pdf
Files
Name | Size | Download all |
---|---|---|
md5:e4b25fc3d5a06fa504c09e791f7666d5
|
1.6 MB | Preview Download |
Additional details
- Eprint ID
- 101460
- Resolver ID
- CaltechAUTHORS:20200221-124858095
- Created
-
2020-02-21Created from EPrint's datestamp field
- Updated
-
2020-02-21Created from EPrint's last_modified field