16
$\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.

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

$\endgroup$
  • 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 Jul 30 '14 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$ – JTT Jul 30 '14 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 Jul 30 '14 at 10:39
9
$\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”.

$\endgroup$
  • $\begingroup$ I prefer this answer as the other implies that ward.D is wrong, it isn't. Just different. $\endgroup$ – Chris Jun 13 '17 at 11:01
5
$\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}

$\endgroup$
  • $\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 Oct 24 '18 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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