PaperlayerView exact revision on arXiv

Source-linked AI summary

Ward's Hierarchical Clustering Method: Clustering Criterion and Agglomerative Algorithm

Fionn Murtagh, Pierre Legendre

arXiv:1111.6285v2stat.MLcs.CVstat.AP

TL;DR

Ward’s hierarchical clustering method has conflicting interpretations and software implementations, including differences in inputs, loop structure, and dendrogram heights. This paper surveys these distinctions and case studies, showing that implementations can optimize the same error-sum-of-squares criterion yet produce different outputs, while some formulations are identical.

  • Problem

    The literature and software packages differ in how Ward’s method defines inputs, algorithm structure, and dendrogram heights, creating confusion for users.

  • Method

    The paper surveys Ward implementations by examining data inputs, agglomerative loop structures, optimized criteria, and dendrogram node heights.

  • Results

    Implementations can minimize the same error-sum-of-squares criterion while producing different outputs, whereas suitably formulated Ward1 and Ward2 implementations can produce identical outputs.

  • Takeaways & Limitations

    Users should distinguish Ward implementations and check how their software handles dissimilarities, algorithm updates, and dendrogram heights.

  • Takeaways & Limitations

    Inter-cluster dissimilarities may fail to satisfy the triangular inequality even when the agglomerative process starts with Euclidean distances.

Abstract

from arXiv · show

The Ward error sum of squares hierarchical clustering method has been very widely used since its first description by Ward in a 1963 publication. It has also been generalized in various ways. However there are different interpretations in the literature and there are different implementations of the Ward agglomerative algorithm in commonly used software systems, including differing expressions of the agglomerative criterion. Our survey work and case studies will be useful for all those involved in developing software for data analysis using Ward's hierarchical clustering method.

1 Introduction · 2 Ward’s Agglomerative Hierarchical Clustering Method

The paper examines conflicting interpretations and implementations of Ward’s hierarchical clustering method, focusing on input dissimilarities, dendrogram heights, agglomerative updates, and variance-based criteria. It defines the method’s mathematical foundations, alternative variance expressions, Lance-Williams updates, limitations, and generalizations.

  • 1 Introduction: Ward implementations differ in input dissimilarities, dendrogram-height transformations, and the loop structure of the stepwise agglomerative algorithm.These differences create confusion in both the literature and software packages.
  • 1 Introduction: R’s hclust implementation requires squared distances as input, using hclust(dist(x)^2,method="ward"), while square-rooted dendrogram heights may be considered separately.The paper explains why distance squaring is required and discusses square roots of agglomeration heights in a later experiment.
  • 1 Introduction: hclust and agnes can produce different outputs from the same dissimilarity matrix despite formal similarity in their criteria and algorithms.The paper identifies this discrepancy as a central issue.
  • 2.1 Some Definitions: A distance is positive, symmetric, definite, and triangular, whereas a dissimilarity may omit the triangular inequality and an ultrametric satisfies the strong triangular inequality.The definitions distinguish ordinary distances, dissimilarities, and tree distances used in hierarchical clustering.
  • 2.1 Some Definitions: Ward’s within-cluster quantities include variance and error sum of squares, obtained from weighted squared distances to a cluster center.The expression becomes variance when p(i) = 1/|q| and error sum of squares when p(i) = 1.
  • 2.2 Alternative Expressions for the Variance: Population variance divides by |q|, whereas sample variance divides by |q| −1; the population quantity is used by Murtagh, while the sample statistic is used by Le Roux and Rouanet and Legendre and Legendre.The paper also notes that variance can be expressed through pairwise distances, distance-matrix traces, or principal-coordinate eigenvalues.
  • 2.3 Lance-Williams Dissimilarity Update Formula: The Lance-Williams recurrence updates d(i ∪j, k) as a weighted combination of d(i,k), d(j,k), d(i,j), and their absolute difference.Its coefficients depend on the clustering criterion, and the recurrence can operate on dissimilarities without requiring an initial Euclidean distance.
  • 2.4 Generalizing Lance-Williams: Even with an initial Euclidean distance, non-singleton inter-cluster dissimilarities need not satisfy the triangular inequality or retain Euclidean metric properties.The recurrence has also been generalized to criteria based on variance, inertia, weighted variance increases, and higher-order distance powers.

3 Implementations of Ward’s Method

The paper distinguishes Ward implementations by their input dissimilarities, agglomerative update formulas, and dendrogram node heights. Despite these formulation differences, Ward1 and Ward2 can minimize the same variance-change criterion and produce identical outputs when appropriately specified.

  • Implementation differences: The implementations differ subtly in data inputs, agglomerative loop structure, and output dendrogram node heights.These differences are examined in relation to how Ward’s method is understood in practice and encoded in software.
  • Ward2: Both Ward1 and Ward2 minimize the change in variance, or the error sum of squares, despite using different expressions for their dissimilarity functions.Ward2 also uses squared Euclidean input dissimilarities, while its δ function differs between the relevant equations as a squared distance versus a distance.
  • Ward1: Ward1 requires squared Euclidean distances as its initial dissimilarities; using Euclidean distances instead can produce a very different clustering topology.This specification is required for the Ward algorithm implemented in Murtagh’s work and in R’s hclust.
  • Ward1: Ward1 minimizes the decrease in partition variance, equivalently minimizing the variance change Var(c)−Var(c1)−Var(c2) from each agglomeration.The same criterion can be viewed as minimizing within-cluster variance or maximizing between-cluster variance.
  • Ward1 and Ward2: With appropriate choices of δ, Ward1 and Ward2 are identical implementations and can yield identical outputs.The paper derives an equivalent Lance–Williams update representation for the two formulations.

4 Case Studies: Ward Implementations and Their Relationships

The case studies compare several R hierarchical-clustering implementations, including distinct Ward1 and Ward2 options in hclust.PL. They use reproducible inputs and dendrogram node heights to assess numerical equivalences.

  • Programs used: The case studies use hclust, agnes, and hclust.PL, three R programs for hierarchical clustering.hclust is in the stats package, agnes in the cluster package, and hclust.PL extends hclust.
  • Ward implementations: hclust.PL implements Ward1 with method="ward.D" and Ward2 with method="ward.D2".The extended function distinguishes the two algorithms through its method argument.
  • Reproducible setup: The analyses ensure reproducibility by providing all code and generating the input data set with a fixed random-number seed.The example fixes the seed at 19037561 before creating a 20×4 input matrix.
  • Comparison procedure: Dendrogram node heights, associated with agglomeration criterion values, are used to quickly show numerical equivalences before displaying dendrograms.Experiment 1 compares hclust.PL and agnes using Ward2-related code: method="ward.D2" and method="ward".

X.hclustPL.wardD2 · X.agnes.wardD2

The paper finds that hclust.PL with method="ward.D2" is identical to agnes with method="ward". Their dendrograms match visually, differing only by inconsequential node swiveling, and the authors provide reproducibility code for the figure.

  • X.agnes.wardD2: Figure 1 documents the outcome of the comparison between the two clustering methods.The figure is presented as the visual evidence for their matching results.
  • X.agnes.wardD2: hclust.PL with method="ward.D2" is identical to agnes with method="ward".This establishes equivalence between the two implementations.
  • X.agnes.wardD2: The two methods produce the same visual dendrogram result.Figure 1 displays the matching outcome in both cases.
  • X.agnes.wardD2: The dendrograms differ only through inconsequential swiveling of nodes.The paper describes this equivalence as wreath product invariance in group theory terminology.
  • X.agnes.wardD2: The authors provide the code used to produce Figure 1 as part of their reproducibility agenda.The code is included to fully document how the displayed result was generated.
  • 4.2 Experiment 2: hclust and Ward1 Implementation, hclust.PL: Experiment 2 reports code using hclust with method="ward" and hclust.PL with method="ward.D".Both commands operate on dist(y)^2, as shown in the supplied code.

X.hclust · X.hclustPL.sq.wardD

With squared inputs, hclust using “ward” and hclust.PL using method="ward.D" produce identical clustering results whose levels are squared from Experiment 1. With non-squared inputs, the corresponding implementations agree visually but produce a different, non-Ward hierarchy.

  • X.hclustPL.sq.wardD: Experiment 2 displays the same visual result for hclust and hclust.PL under the squared-input configurations.The figure reports the outcome of the comparison.
  • X.hclustPL.sq.wardD: On squared input, hclust with option “ward” is identical to hclust.PL with method="ward.D".Both cases display the same visual outcome.
  • X.hclustPL.sq.wardD: The Experiment 2 clustering levels are the squares of those produced by Experiment 1.This relationship describes the levels shown for the squared-input comparison.
  • 4.3 Experiment 3: Non-Ward Result Produced by hclust and hclust.PL: With different, non-squared input, the methods produce a well-defined hierarchical clustering that differs from Ward.The experiment uses hclust.PL with method="ward.D" and hclust with method="ward".
  • 4.3 Experiment 3: Non-Ward Result Produced by hclust and hclust.PL: Without squaring inputs, hclust.PL method="wardD" and hclust method="ward" produce the same result.The two implementations also show the same visual outcome.
  • 4.3 Experiment 3: Non-Ward Result Produced by hclust and hclust.PL: The non-squared-input clustering levels differ from, and are not monotonic relative to, those from Experiments 1 and 2.Both the input treatment and the resulting level behavior distinguish this experiment from the earlier ones.
  • 4.4 Experiment 4: Modifying Inputs and Options so that Ward1 Output is Identical to Ward2 Output: Experiment 4 uses the formal equivalences of Ward1 and Ward2 implementations to modify inputs and options for identical output.The experiment is presented as a way to bring about identical Ward1 and Ward2 results.

X.hclustPL.wardD · X.hclust.nosq

The section examines how squaring input dissimilarities and implementation options affect Ward clustering outputs. It emphasizes unsquared distance terms for node heights and shows equivalent tree results after appropriate square-root transformations.

  • X.hclust.nosq: Squaring or not squaring input dissimilarities, along with option choices, is used to examine differences in output.The comparison varies both the dissimilarity transformation and software options.
  • X.hclust.nosq: Node heights are reported in distance terms based on the initial, unsquared Euclidean distances.Although agglomerations redefine distances as dissimilarities, the analysis concerns unsquared dissimilarities.
  • X.hclust.nosq: Inter-cluster measures are dissimilarities, whereas inter-node measures defined on the tree are ultrametric.The distinction applies to measures defined within a partition versus measures defined on the resulting tree.
  • X.hclust.nosq: Sorting squared agglomeration or height levels is equivalent to sorting them first and then squaring them.The ordering is unchanged by applying the monotonic squaring operation after sorting.
  • X.hclust.nosq: Experiment 4 identifies equivalent outcomes when node heights are square rooted.The reported equivalence concerns the displayed tree heights rather than a new clustering order.
  • X.hclustPL.wardD: The compared implementations include hclust with the "ward" option on squared input and hclust.PL with method="ward.D" on squared input.These options are explicitly listed as producing the compared outcomes.
  • X.hclust.nosq: Figure 4 shows the same visual result in both cases, consistent with the numerical node or agglomeration height values.The displayed comparison uses square-rooted heights for X.hclust and X.hclustPL.wardD2.

5 Discussion

The discussion emphasizes that input squaring and implementation choices are crucial, while Ward1 and Ward2 produce equivalent dendrogram results despite differing criterion scales. It also distinguishes stored-dissimilarity from stored-data implementations and notes practical differences in interpreting dendrogram distances.

  • Experiments: Experiments 1 and 2 show that inputs, whether squared or not, and implementation options are crucial to obtaining Ward2 or Ward1.Experiment 3 shows either implementation can be modified to produce another well-defined non-Ward hierarchy.
  • Ward1 and Ward2: Ward1 and Ward2 yield the same dendrogram morphology and equivalent results, although their cluster criterion values, or node heights, differ.Experiment 4 demonstrates the underlying equivalence of the two implementations’ results.
  • Ward1 and Ward2: Ward2’s cluster criterion is most naturally the square root of Ward1’s, preserving morphology and optimization because the two optimants are monotonically related.The scale transformation affects criterion values but not the hierarchy’s morphology or optimization outcome.
  • Practical differences: Ward2 criterion values are on a distance scale, whereas Ward1 criterion values are on a distance-squared scale.This distinction matters when directly comparing dendrogram ultrametric distances with input distances.
  • Implementations: The algorithm supports stored-dissimilarity implementations using a dissimilarity matrix and stored-data implementations that create dissimilarities on the fly.The distinction was first made in Anderberg (1973).

6 Conclusions

The article distinguishes two closely related implementations, Ward1 and Ward2, that both claim to implement Ward’s 1963 method but can produce different results. For the same dissimilarity matrix, only Ward2 minimizes the Ward clustering criterion, while the implementations can be aligned to optimize the same criterion and produce the same clustering topology.

  • 6 Conclusions: Implementations differing by only a few lines of code can create confusion for learners, practitioners, and specialists who believe they are using the same method.The article reviews the relevant background and lays out the two differing implementations clearly.
  • 6 Conclusions: Ward1 and Ward2 both claim to implement Ward’s 1963 clustering method, yet they produce different results when applied to the same distance matrix D.The article emphasizes that the two algorithms are very close implementations despite their differing outputs.
  • 6 Conclusions: Only Ward2 minimizes the Ward clustering criterion and produces the Ward method when applied to the same dissimilarity matrix D.Ward1 and Ward2 can be made to optimize the same criterion and produce the same clustering topology.
  • 6 Conclusions: Software developers offering only Ward1 should clearly explain how to obtain Ward2 output.The article presents this as an implementation recommendation based on the preceding distinction.
Loading 1111.6285v2…