Characterization, stability and convergence of hierarchical clustering algorithms
Date
2010
Authors
Carlsson, Gunnar
Memoli, Facundo
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Journal of Machine Learning Research, 2010; 11(4):1425-1470
Statement of Responsibility
clustering; hierarchical clustering; stability of clustering; Gromov-Hausdorff distance
Conference Name
Abstract
We study hierarchical clustering schemes under an axiomatic view. We show that within this framework, one can prove a theorem analogous to one of Kleinberg (2002), in which one obtains an existence and uniqueness theorem instead of a non-existence result. We explore further properties of this unique scheme: stability and convergence are established. We represent dendrograms as ultrametric spaces and use tools from metric geometry, namely the Gromov-Hausdorff distance, to quantify the degree to which perturbations in the input metric space affect the result of hierarchical methods.
School/Discipline
School of Computer Science
Dissertation Note
Provenance
Description
Access Status
Rights
© 2010 Gunnar Carlsson and Facundo Mémoli