A Randomized Algorithm for Pairwise Clustering
Abstract
We present a stochastic clustering algorithm based on pairwise sim(cid:173) ilarity of datapoints. Our method extends existing deterministic methods, including agglomerative algorithms, min-cut graph algo(cid:173) rithms, and connected components. Thus it provides a common framework for all these methods. Our graph-based method differs from existing stochastic methods which are based on analogy to physical systems. The stochastic nature of our method makes it more robust against noise, including accidental edges and small spurious clusters. We demonstrate the superiority of our algorithm using an example with 3 spiraling bands and a lot of noise.
Cite
Text
Gdalyahu et al. "A Randomized Algorithm for Pairwise Clustering." Neural Information Processing Systems, 1998.Markdown
[Gdalyahu et al. "A Randomized Algorithm for Pairwise Clustering." Neural Information Processing Systems, 1998.](https://mlanthology.org/neurips/1998/gdalyahu1998neurips-randomized/)BibTeX
@inproceedings{gdalyahu1998neurips-randomized,
title = {{A Randomized Algorithm for Pairwise Clustering}},
author = {Gdalyahu, Yoram and Weinshall, Daphna and Werman, Michael},
booktitle = {Neural Information Processing Systems},
year = {1998},
pages = {424-430},
url = {https://mlanthology.org/neurips/1998/gdalyahu1998neurips-randomized/}
}