1
$\begingroup$

Let's look at this example:

simple.data = data.frame(
  x = c(0,1,0.5),
  y = c(0,0,0.9)
)

par(mfrow = c(1,2))
plot(simple.data, xlab = "Dimension 1", ylab = "Dimension 2")
text(simple.data[1,], labels = 1, pos = 3)
text(simple.data[2,], labels = 2, pos = 3)
text(simple.data[3,], labels = 3, pos = 1)

eucl = dist(simple.data, method = "euclidean")

#         1        2
# 2 1.000000         
# 3 1.029563 1.029563

agglo = hclust(eucl, method = "centroid")
cophenetic(agglo)

#          1        2
# 2 1.000000         
# 3 0.779563 0.779563

par(mar = c(2,4,1,1))
plot(as.dendrogram(agglo), main = "Dendrogram", ylab = "Height", ylim = c(0,1))

enter image description here

  1. I know that the distances between clusters can be computed using the Lance und Williams Formula, e.g. $$D(A \cup B,C)=\alpha_1 d(A,C)+\alpha_2 d(B,C)+ \beta d(A,B) + \gamma |d(A,C)-d(B,C)|.$$ with $\alpha_1 = \tfrac{|A|}{|A|+|B|}, \alpha_2 = \tfrac{|B|}{|A|+|B|}, \beta = \tfrac{|A||B|}{(|A|+|B|)^2}, \gamma = 0$ for centroid linkage (see also https://de.wikipedia.org/wiki/Hierarchische_Clusteranalyse#Lance_und_Williams_Formel).

  2. I also know that, in R, the dendrogram and the function cophenetic() computes the distances between two clusters with this formula, e.g. after merging the two closest points (in example above: point 1 and point 2), the distance between the cluster that consists of point 1 and 2 and the second cluster that only consists of point 3 is, according to the Lance und Williams Formula with $\alpha_1 = \alpha_2 = 0.5, \gamma = 0$ and $\beta = 0.25$: 0.5*1.029563 + 0.5*1.029563 - 0.25*1 = 0.779563. Therefore, the dendrogram shows a merge of those two clusters at "Height" 0.779563.

  3. However, since "in centroid method, the distance between two clusters is the distance between the two cluster centroids", I would have computed this distance differently, namely:

    • compute centroid of point 1 and 2, which is at (0.5, 0)
    • "centroid" of point 3 is point 3 itself (located at (0.5, 0.9), see plot).
    • euclidean distance between the two cluster centroids is therefore sqrt((0.5-0.5)^2+(0-0.9)^2) = 0.9, which is not the same distance as computed with the Lance und Williams Formula.

So, my questions is: Why do we use the Lance und Williams Formula (e.g. the 0.779563) to plot the dendrogram and do not use "the distance between the two cluster centroids", which is 0.9?

$\endgroup$
  • 1
    $\begingroup$ I think you need to re calculate your tree. This dengrogram is not drawn well. It has a reverse branch. Have a look at the end of this page: link Also check Dendrogram and some related areas in MATLAB website. They have great detailed explanations which if I remember correctly, your answer is also there. Sorry, I only know these through MATLAB, not R. $\endgroup$ – PeyM87 Jun 6 '16 at 14:01
  • 2
    $\begingroup$ Centroid method (and also median, Ward) expect that the input distances are squared euclidean, their L-W formula implies it. Either square your euclidean distances or tell the program that they aren't square (if there's such an option). $\endgroup$ – ttnphns Jun 6 '16 at 15:52
  • $\begingroup$ It seems that if I use squared euclidean distance agglo = hclust(eucl^2, method = "centroid"), I still have to take the root of the cophenetic distances sqrt(cophenetic(agglo)) to get 0.9. However, I did not see a possibility how to do this in the dendrogram... $\endgroup$ – Giuseppe Jun 7 '16 at 6:51
  • $\begingroup$ Well this does what I want: agglo = hclust(dist(simple.data, method = "euclidean")^2, method = "centroid");agglo$height = sqrt(agglo$height);plot(as.dendrogram(agglo), ylim = c(0,1)). I have to say that for interpretation purposes this is really strange: In the first step, the $y$ axis in the dendrogram can be interpreted as the euclidean distance between the two points. However, when we merge clusters, the $y$ axis of the dendrogram does not show the euclidean distances... $\endgroup$ – Giuseppe Jun 7 '16 at 7:17
  • 1
    $\begingroup$ Once again, by points. L-W formula for centroid method is formulated w.r.t. squared euclidean distance (s.e.d.); it is done for convenience and speed. Centroid method needs s.e.d. as the input distance matrix. Logically, s.e.d. is what should be plotted on a dendrogram. Whether it is possible to input nonsquared e.d. (and still get the right result!) and/or to plot dendrogram with root taken from the plotted linkage coefficients - depends entirely on your function additional options, these are features that might exist. $\endgroup$ – ttnphns Jun 7 '16 at 7:41
1
$\begingroup$

According to the book Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze:

centroid clustering is not monotonic. So-called inversions can occur: Similarity can increase during clustering as in the example in Figure 17.12, where we define similarity as negative distance.

this seems this is an typical behavior.

Clearly, 1 and 2 are the closest points at distance 1. So that is the best possible merge here.

The squared Euclidean distance of the centroids is $0^2+0.9^2=0.81$.

With Lance-Williams: The squared Euclidean distance is $d(1,3)=d(2,3)=0.9^2+0.5^2 = 1.06$, while d(1,2)=1. So we get $$\frac121.06+\frac121.06-\frac141=0.81.$$

Therefore:

  1. The result is correct - if you use squared Euclidean distances. I don't think you can use the (efficient!) Lance-Williams approach with other distances. Plus, the centroid makes most sense with squared errors, too.
  2. Inversions in centroid linkage do occur. Even if you would use non-squared Euclidean distance. With regular Euclidean distance, you would still merge 1,2 at distance 1, and then merge 1,2,3 at $\sqrt{0.81}=0.9$; which is less than 1.

But don't ask me for a proof that the Lance-Williams and "direct" definition are equivalent. Apparently the proof can only work for squared Euclidean? I guess it is similar to the derivation of Ward's, which appears to be the "properly weighted" version of centroid linkage.

$\endgroup$

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.