AISTATS 2021poster7 citations
Large Scale K-Median Clustering for Stable Clustering Instances
Abstract
We study the problem of computing a good k-median clustering in a parallel computing environment. We design an efficient algorithm that gives a constant-factor approximation to the optimal solution for stable clustering instances. The notion of stability that we consider is resilience to perturbations of the distances between the points. Our computational experiments show that our algorithm works well in practice - we are able to find better clusterings than Lloyd’s algorithm and a centralized coreset construction using samples of the same size.
BibTeX
@InProceedings{pmlr-v130-voevodski21a,
title = { Large Scale K-Median Clustering for Stable Clustering Instances },
author = {Voevodski, Konstantin},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {2890--2898},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/voevodski21a/voevodski21a.pdf},
url = {https://proceedings.mlr.press/v130/voevodski21a.html},
abstract = { We study the problem of computing a good k-median clustering in a parallel computing environment. We design an efficient algorithm that gives a constant-factor approximation to the optimal solution for stable clustering instances. The notion of stability that we consider is resilience to perturbations of the distances between the points. Our computational experiments show that our algorithm works well in practice - we are able to find better clusterings than Lloyd’s algorithm and a centralized coreset construction using samples of the same size. }
}