Gromov–Hausdorff stability of linkage-based hierarchical clustering methods

• We study the problem of stability on linkage-based hierarchical clustering methods.
• Under some basic conditions, standard linkage-based methods are semi-stable.
• We consider linkage-based hierarchical clustering methods with an unchaining condition (generalizing the algorithm).
• In general, introducing any unchaining condition in the algorithm always produces unstable methods.

A hierarchical clustering method is stable if small perturbations on the data set produce small perturbations in the result. These perturbations are measured using the Gromov–Hausdorff metric. We study the problem of stability on linkage-based hierarchical clustering methods. We obtain that, under some basic conditions, standard linkage-based methods are semi-stable. We also prove that, avoiding exotic examples, introducing any unchaining condition in the algorithm always produces unstable methods.