How to Tell When a Clustering Is (approximately) Correct Using Convex Relaxations
Abstract
We introduce the Sublevel Set (SS) method, a generic method to obtain sufficient guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. This method can be instantiated for a variety of clustering loss functions for which convex relaxations exist. Obtaining the guarantees in practice amounts to solving a convex optimization. We demonstrate the applicability of this method by obtaining distribution free guarantees for K-means clustering on realistic data sets.
Cite
Text
Meila. "How to Tell When a Clustering Is (approximately) Correct Using Convex Relaxations." Neural Information Processing Systems, 2018.Markdown
[Meila. "How to Tell When a Clustering Is (approximately) Correct Using Convex Relaxations." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/meila2018neurips-tell/)BibTeX
@inproceedings{meila2018neurips-tell,
title = {{How to Tell When a Clustering Is (approximately) Correct Using Convex Relaxations}},
author = {Meila, Marina},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {7407-7418},
url = {https://mlanthology.org/neurips/2018/meila2018neurips-tell/}
}