Hierarchical clustering in R - centroid linkage - problem with dendrogram heights

Question

I have got a problem with understanding the hierarchical clustering algorythm, especially centroid linkage method. I have read many articles with description and they seems to be quite easy but I connot understand the results on real values.

I have got sample set like this:

test_list <- list( one = c(1), two = c(2), six = c(6), eleven = c(11), sixteen = c(16) )

I can generate a cluster using this function:

test_dendrogram <- tsclust(test_list, type = "hierarchical", distance = "L1", control = hierarchical_control(method = "centroid" ) )

The dendrogram looks like this:

The list of heights is: 1.000000 4.250000 5.000000 8.138889

I understand the results as below:

1 = 2 - 1

5 = 16 - 11

4.25 = 6-((2+1)/2 + 2)/2 <- in this step we need to replace 1 for centroid 1 and 2 = 1,5 and calculate centroid which means arithmetic average.

But I have no idea how to calculate 8.13. I did the same exercise with single, average and complete linkage methods and the results are obvious.

Answer 1

Explaining calculations done in centroid linkage hierarchical clustering

Your data: 5 points in 1D feature space:
a   1 
b   2 
c   6 
d  11 
e  16

Compute squared euclidean distances (because centroid method needs thus) and perform the agglomerative clustering (done in SPSS).

On the dengrogram, the computed distances between clusters being merged on steps are numerically rescaled into range 1-25, however in the agglomeration history table they are displayed as is (called "coefficients").

Let us now trace the computations done.

Step 1. Find the minimal distance and merge these two points. These are a and b (i.e. points 1 and 2 in the aggl. schedule) and the (squared euclidean) distance is $1$. OK. Label cluster (a+b) 1 (the lesser between labels 1 and 2) and delete cluster 2, i.e. point b, from the matrix. Now update sq. eucl. distances between cluster 1 (i.e. points a+b) and every other point/cluster. This is done through Lance-Williams formula which in case of centroid linkage method unwraps into this:

$D_{(pq)r} = \frac{N_p}{N_{pq}} D_{pr} + \frac{N_q}{N_{pq}} D_{qr} - \frac{N_pN_q}{N_{pq}^2} D_{pq}$

where $D_{(pq)r}$ is the distance of the newly merged cluster "pq" (just merged of "p" and "q" subclusters) and every else cluster "r", $N$ with subscript is the number of points in a cluster.

So, after merge at step 1 we compute distance between (a+b) and, say, d, as

$D_{(ab)d} = \frac{1}{2} 100 + \frac{1}{2} 81 - \frac{1 \cdot 1}{2^2} 1 = 90.25$.

Upon computing distance between (a+b) and every other cluster the updated distance matrix is:

       ab     c      d      e
ab     .00  20.25  90.25 210.25
c    20.25    .00  25.00 100.00
d    90.25  25.00    .00  25.00
e   210.25 100.00  25.00    .00

Step 2. Find the minimal distance in it. It is the distance between cluster (a+b) and cluster (point) c (aka 3 in aggl. schedule). Merge the two clusters, (ab+c) and, using the formula, update the distances between it and every other one (before that, remove row and column c). For example, the distance between (ab+c) and d will be:

$D_{((ab)c)d} = \frac{2}{3} 90.25 + \frac{1}{3} 25 - \frac{2 \cdot 1}{3^2} 20.25 = 64$

and whole updated distance matrix

       abc    d      e
abc    .00  64.00 169.00
 d   64.00    .00  25.00
 e  169.00  25.00    .00

Step 3. etc likewise. The two clusters to merge will be d and e which distance = $25$ is currently the least.

Remember that computations are done on squared euclidean distances (in centroid method). Of course, you may take root from the computed $D$s at each step if you (reasonably) want to plot the dendrogram reflecting nonsquared distances between clusters. Just take sq. root from the "coefficients" in the agglomeration schedule above and that will be your nonsquared distances for the dendrogram. In my dendrogram shown above, squared distances were plotted.