2
$\begingroup$

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: enter image description here

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.

$\endgroup$
  • $\begingroup$ You should explain what your r comnand actually requests, in particular, what distance=L1 entails. For you should know that centroid method implicitly is based on L2, euclidean distance. $\endgroup$ – ttnphns Oct 21 '18 at 20:36
  • $\begingroup$ Distance L=1 is manhattan distance but for a single points we can treat euclidean and manhattan as a exactly the same distance algorithm. You can give me the answer for euclidean distance, does not matter in this case. $\endgroup$ – Bochnio Oct 22 '18 at 6:22
  • $\begingroup$ You say you read a lot of articles. Then you must be acquainted with how Lance-Williams formula mentioned here is expressed in case of centroid method. Use it. $\endgroup$ – ttnphns Oct 22 '18 at 8:09
  • $\begingroup$ ttnphns ok, I used Lance-Williams formula to calculate cluster [six + one-two] it is pretty easy 4,25 = =(1/2)*(6-1)+(1/2)*(6-2)+(-1/(2^2))*1 but I have no idea how to use this formula when I have 1 cluster which contains 3 elements and 1 cluster which contains 2 elements. Could you give me some advice? $\endgroup$ – Bochnio Oct 27 '18 at 14:00
  • $\begingroup$ I don't see the distance matrix (euclidean or squared euclidean d) in your question. Or the casewise data to be able to compute the distances. $\endgroup$ – ttnphns Oct 27 '18 at 14:10
1
$\begingroup$

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).

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thank you very much for your help, everything works well! $\endgroup$ – Bochnio Oct 28 '18 at 15:40

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.