Applicability and Interpretability of Hierarchical Agglomerative Clustering With or Without Contiguity Constraints

Nathanaël Randriamihamison, Nathalie Vialaneix, Pierre Neuvial

Abstract

Hierarchical Agglomerative Classification (HAC) with Ward's linkage has been widely used since its introduction in Ward (1963). The present article reviews the different extensions of the method to various input data and the constrained framework, while providing applicability conditions. In addition, various versions of the graphical representation of the results as a dendrogram are also presented and their properties are clarified. While some of these results can sometimes be found in an heteroclite literature, we clarify and complete them all using a uniform background. In particular, this study reveals an important distinction between a consistency property of the dendrogram and the absence of crossover within it. Finally, a simulation study shows that the constrained version of HAC can sometimes provide more relevant results than its unconstrained version despite the fact that the latter optimizes the objective criterion on a reduced set of solutions at each step. Overall, the article provides comprehensive recommandations for the use of HAC and constrained HAC depending on the input data as well as for the representation of the results.

Introduction

Hierarchical Agglomerative Clustering (HAC) has remained a cornerstone of unsupervised learning since its inception in 1963. By iteratively merging clusters to minimize an objective function—typically the increase in within-cluster variance or "inertia"—it provides a nested sequence of partitions that can be visualized as a dendrogram. However, modern applications often involve non-Euclidean data structures (such as similarity matrices) or spatial/order constraints (contiguity constraints). This paper provides a rigorous unification of these extensions, addressing the fragmented literature and offering practical guidance on interpreting the resulting hierarchies.

The Standard HAC Framework

The core of the HAC methodology lies in its greedy optimization of the Error Sum of Squares (ESS). Starting with each data point as its own cluster, the algorithm proceeds through $n-1$ steps, merging the two clusters that result in the minimal increase in total inertia.

Algorithm 1: The standard procedure for Hierarchical Agglomerative Clustering (HAC).

As shown in Algorithm 1, the process is defined by the computation of pairwise linkage values between clusters in the current partition $\mathcal{P}_t$. While this standard approach is well-understood for Euclidean coordinates, its behavior becomes more complex when constraints are introduced or when the underlying data is represented by dissimilarities or kernels.

Extensions: Constraints and Non-Euclidean Data

The authors systematically extend Ward’s linkage to accommodate two major scenarios:

  1. Non-Euclidean Data: By utilizing "pseudo-inertia," the authors demonstrate how HAC can be applied to objects described only by pairwise similarities or kernels. This allows the method to be used in domains where explicit coordinates are unavailable.
  2. Contiguity Constraints: In many fields, such as genomics or geography, merges are only permissible between "neighboring" clusters. The paper analyzes CCHAC (Contiguity-Constrained HAC) and OCHAC (Order-Constrained HAC), where objects follow a linear sequence (e.g., DNA loci).

Interpretability: Reversals vs. Crossovers

A common frustration for practitioners is the appearance of "reversals" in dendrograms, where a merge at step $t$ occurs at a lower height than a merge at step $t-1$. The paper makes a critical distinction between a mathematical reversal and a visual crossover.

To resolve these issues, the authors compare four height definitions:

  • $m_t$: Standard Ward linkage value.
  • $ESS_t$: Total within-cluster Error Sum of Squares.
  • $I_t$: Inertia of the newly merged cluster.
  • $\bar{I}_t$: Average inertia of the merged cluster.

Their analysis shows that while $m_t$ is monotonic for unconstrained HAC, it often fails for constrained versions. In such cases, using $ESS_t$ as the height definition is recommended to maintain interpretability.

Experimental Results and Discussion

Using synthetic toy examples and real-world Hi-C genomic data (Chromosome 3 from human embryonic stem cells), the authors tested the robustness of constrained HAC.

The "Greedy" Paradox and Regularization

One of the most surprising findings is that constraints can act as a regularizer. In Hi-C simulations, OCHAC achieved a 25-30% lower ESS than standard unconstrained HAC at low noise levels. By restricting the search space, the algorithm is prevented from making locally optimal but globally poor decisions early in the process.

Robustness to Noise

Constrained HAC proves highly robust to structured noise. However, if the underlying spatial constraint is fundamentally incorrect (e.g., high levels of random permutation), the performance collapses. This collapse is accompanied by massive reversals in the dendrogram, serving as a diagnostic signal that the chosen constraint is invalid for the data.

Conclusion

This study clarifies the conditions under which HAC and its constrained variants remain applicable and interpretable. By providing a uniform mathematical background, the authors offer clear recommendations: use $ESS_t$ for height in constrained settings, and leverage constraints not just for domain-specific reasons, but as a tool to potentially improve global optimization. Future work remains in finding universally monotonic height definitions for constrained HAC on non-Euclidean data, where the physical intuition of a "center of gravity" is absent.

Summary updated

Abstract

Hierarchical Agglomerative Classification (HAC) with Ward's linkage has been widely used since its introduction in Ward (1963). The present article reviews the different extensions of the method to various input data and the constrained framework, while providing applicability conditions. In addition, various versions of the graphical representation of the results as a dendrogram are also presented and their properties are clarified. While some of these results can sometimes be found in an heteroclite literature, we clarify and complete them all using a uniform background. In particular, this study reveals an important distinction between a consistency property of the dendrogram and the absence of crossover within it. Finally, a simulation study shows that the constrained version of HAC can sometimes provide more relevant results than its unconstrained version despite the fact that the latter optimizes the objective criterion on a reduced set of solutions at each step. Overall, the article provides comprehensive recommandations for the use of HAC and constrained HAC depending on the input data as well as for the representation of the results.
BibTeX
@article{randriamihamison2021applicability,
  author = {Nathanaël Randriamihamison and Nathalie Vialaneix and Pierre Neuvial},
  title = {{Applicability and Interpretability of Hierarchical Agglomerative Clustering With or Without Contiguity Constraints}},
  journal = {J. Classif.},
  year = {2021},
  doi = {10.1007/s00357-020-09377-y},
}
Figure