22
$\begingroup$

The one used by option "ward.D" (equivalent to the only Ward option "ward" in R versions <= 3.0.3) does not implement Ward's (1963) clustering criterion, whereas option "ward.D2" implements that criterion (Murtagh and Legendre 2014).

(http://stat.ethz.ch/R-manual/R-patched/library/stats/html/hclust.html)

Apparently ward.D does not implement Ward's criterion properly. Nonetheless it seems to do a good job regarding the clusterings it produces. What does method="ward.D" implement if it is not Ward's criterion?

References

Murtagh, F., & Legendre, P. (2014). Ward’s hierarchical agglomerative clustering method: which algorithms implement Ward’s criterion?. Journal of Classification, 31(3), 274-295.

Improve this question
$\endgroup$
7
  • $\begingroup$ Does the Murthagh and Legendre paper say anything about this? $\endgroup$
    – cbeleites
    Commented Jul 30, 2014 at 8:04
  • $\begingroup$ I have no access to that paper $\endgroup$
    – Raffael
    Commented Jul 30, 2014 at 8:15
  • $\begingroup$ First thing a search turns up for me is the pdf of the manuscript at u montreal!? $\endgroup$
    – cbeleites
    Commented Jul 30, 2014 at 8:24
  • $\begingroup$ so what does the paper say? I can't find it $\endgroup$
    – Raffael
    Commented Jul 30, 2014 at 8:28
  • $\begingroup$ That's what I ask you to tell us. $\endgroup$
    – cbeleites
    Commented Jul 30, 2014 at 8:29

3 Answers 3

Reset to default
14
$\begingroup$

The relevant manuscript is here.

The difference between ward.D and ward.D2 is the difference between the two clustering criteria that in the manuscript are called Ward1 and Ward2.

It basically boils down to the fact that the Ward algorithm is directly correctly implemented in just Ward2 (ward.D2), but Ward1 (ward.D) can also be used, if the Euclidean distances (from dist()) are squared before inputing them to the hclust() using the ward.D as the method.

For example, SPSS also implements Ward1, but warn the users that distances should be squared to obtain the Ward criterion. In such sense implementation of ward.D is not deprecated, and nonetheless it might be a good idea to retain it for backward compatibility.      

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ From the paper you link to it follows not Ward algorithm is directly correctly implemented in just Ward2, but rather that: (1) to get correct results with both implementations, use squared Euclidean distances with Ward1 and nonsquared Euclidean distances with Ward2; (2) to further make their output dendrograms comparable (identical), apply sq. root to fusion levels after Ward1 or square fusion levels after Ward2, before constructing dendrogram. $\endgroup$
    – ttnphns
    Commented Jul 30, 2014 at 10:06
  • $\begingroup$ You are right, of course. Thanks for the clarification. What I meant by "directly correctly implemented" is that no further steps, such as taking a square root of the heights, are needed to arrive to the correct result with the ward.D2 method. $\endgroup$
    – anon
    Commented Jul 30, 2014 at 10:29
  • 1
    $\begingroup$ The tiny nuance here is that with Ward's method, it is not defined what is "correct" or true fusion levels presentation - whether they should be plotted "nonsquared" or "squared". The cause of of the indecision is that fusion levels in Ward are not distances, they are incremental dispersions. $\endgroup$
    – ttnphns
    Commented Jul 30, 2014 at 10:39
15
$\begingroup$

The only difference between ward.D & ward.D2 is the input parameter.

hclust(dist(x)^2,method="ward.D") ~ hclust(dist(x)^2,method="ward")

which are equivalent to: hclust(dist(x),method="ward.D2")

You can find the reserach paper : Ward’s Hierarchical Clustering Method: Clustering Criterion and Agglomerative Algorithm

The Ward2 criterion values are “on a scale of distances” whereas the Ward1 criterion values are “on a scale of distances squared”.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I prefer this answer as the other implies that ward.D is wrong, it isn't. Just different. $\endgroup$
    – Chris
    Commented Jun 13, 2017 at 11:01
6
$\begingroup$

I came across the research paper that corresponds to the objective function that is being optimized by "Ward1 (ward.D)": Hierarchical Clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method. It turns out that R's implementation of "Ward1 (ward.D)" is equivalent to minimizing the energy distance between cluster groups.

2.1 Cluster $e$-distance and Objective Function

Let $A = \{a_1, \ldots, a_{n_1}\}$ and $B = \{b_1, \ldots, b_{n_2}\}$ be nonempty subsets of $\mathbb R^d$. Define the between-within, or $e$-distance $e(A, B)$, between $A$ and $B$ as \begin{align} e(A, B) = &\frac{n_1n_2}{n_1+n_2}\bigg(\frac{2}{n_1n_2}\sum_{i=1}^{n_1} \sum_{j=1}^{n_2} \|a_i-b_j\| \\ &- \frac{1}{n_1^2}\sum_{i=1}^{n_1}\sum_{j=1}^{n_1}\|a_i-a_j\| - \frac{1}{n_2^2}\sum_{i=1}^{n_2}\sum_{j=1}^{n_2}\|b_i-b_j\|\bigg). \tag{1} \end{align}

Improve this answer
$\endgroup$
1
  • $\begingroup$ Are you sure that that is the correct interpretation of the contents of that paper? It seems to me that $e^{(2)}$ corresponds to ward.D2, but I don't think it is stated anywhere that $e^{(1)}$ corresponds to ward.D1. In fact, on page 161–162, it is stated that for $0<\alpha<2$, $e^{(\alpha)}$ does not correspond to any power of Euclidean distance, assuming cluster size is greater than $1$ . Interesting paper none the less. $\endgroup$
    – Jonas Dahlbæk
    Commented Oct 24, 2018 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.