ML Anthology

Error Bounds for Correlation Clustering

Thorsten Joachims, John E. Hopcroft
ICML 2005 pp. 385-392
doi:10.1145/1102351.1102400 /icml/2005/joachims2005icml-error/

Abstract

This paper presents a learning theoretical analysis of correlation clustering (Bansal et al., 2002). In particular, we give bounds on the error with which correlation clustering recovers the correct partition in a planted partition model (Condon & Karp, 2001; McSherry, 2001). Using these bounds, we analyze how the accuracy of correlation clustering scales with the number of clusters and the sparsity of the graph. We also propose a statistical test that analyzes the significance of the clustering found by correlation clustering.

PDF ICML Semantic Scholar

Cite

Text

Joachims and Hopcroft. "Error Bounds for Correlation Clustering." International Conference on Machine Learning, 2005. doi:10.1145/1102351.1102400

Markdown

[Joachims and Hopcroft. "Error Bounds for Correlation Clustering." International Conference on Machine Learning, 2005.](https://mlanthology.org/icml/2005/joachims2005icml-error/) doi:10.1145/1102351.1102400

BibTeX

@inproceedings{joachims2005icml-error,
  title     = {{Error Bounds for Correlation Clustering}},
  author    = {Joachims, Thorsten and Hopcroft, John E.},
  booktitle = {International Conference on Machine Learning},
  year      = {2005},
  pages     = {385-392},
  doi       = {10.1145/1102351.1102400},
  url       = {https://mlanthology.org/icml/2005/joachims2005icml-error/}
}