Characterization, Stability and Convergence of Hierarchical Clustering Methods

Carlsson, G., Memoli, F. (2010). Characterization, Stability and Convergence of Hierarchical Clustering Methods. Journal of Machine Learning Research 11: 1425-1470.

Kleinberg, 2002: There exists no clustering algorithm that satisfies scale invariance, richness and consistency. Natural question is what about hierarchical clusters?

Going to skip some math and notation. Just formalities as this is a math paper.

A hierarchical clustering method is a map that assign a dendrogram to a finite metric space. HC methods operate on a metric space, where the points in the space are denoted as X and the distances between points are denoted as D. D is the distance matrix and is X x X in size.

Yeah, so this goes into some deep theory about HC methods and that HC is the same as mapping from a metric space to an ultrametric space (a metric space satisfies the triangle inequality, and in an ultrametric space all triangles are isocoles(?)) . Not a lot of practicality in this paper.

They also talk about similarities between dendrograms.