Complete-linkage clustering

The following algorithm is an agglomerative scheme that erases rows and columns in a proximity matrix as old clusters are merged into new ones. The ${\displaystyle N\times N}$ proximity matrix D contains all distances d(i,j). The clusterings are assigned sequence numbers 0,1,......, (n − 1) and L(k) is the level of the kth clustering. A cluster with sequence number m is denoted (m) and the proximity between clusters (r) and (s) is denoted d[(r),(s)].

The complete linkage clustering algorithm consists of the following steps:

1. Begin with the disjoint clustering having level ${\displaystyle L(0)=0}$ and sequence number ${\displaystyle m=0}$.
2. Find the most similar pair of clusters in the current clustering, say pair ${\displaystyle (r),(s)}$, according to ${\displaystyle d[(r),(s)]=\min d[(i),(j)]}$where the minimum is over all pairs of clusters in the current clustering.
3. Increment the sequence number: ${\displaystyle m=m+1}$. Merge clusters ${\displaystyle (r)}$ and ${\displaystyle (s)}$ into a single cluster to form the next clustering ${\displaystyle m}$. Set the level of this clustering to ${\displaystyle L(m)=d[(r),(s)]}$
4. Update the proximity matrix, ${\displaystyle D}$, by deleting the rows and columns corresponding to clusters ${\displaystyle (r)}$ and ${\displaystyle (s)}$ and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted ${\displaystyle (r,s)}$, and an old cluster ${\displaystyle (k)}$ is defined as ${\displaystyle d[(r,s),(k)]=\max\{d[(k),(r)],d[(k),(s)]\}}$.
5. If all objects are in one cluster, stop. Else, go to step 2.

The algorithm explained above is easy to understand but of complexity ${\displaystyle O(n^{3})}$. In May 1976, D. Defays proposed an optimally efficient algorithm of only complexity ${\displaystyle O(n^{2})}$ known as CLINK (published 1977)[4] inspired by the similar algorithm SLINK for single-linkage clustering.

• First clustering

Let us assume that we have five elements ${\displaystyle (a,b,c,d,e)}$ and the following matrix ${\displaystyle D_{1}}$ of pairwise distances between them:

In this example, ${\displaystyle D_{1}(a,b)=17}$ is the smallest value of ${\displaystyle D_{1}}$, so we join elements ${\displaystyle a}$ and ${\displaystyle b}$.

• First branch length estimation

Let ${\displaystyle u}$ denote the node to which ${\displaystyle a}$ and ${\displaystyle b}$ are now connected. Setting ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ ensures that elements ${\displaystyle a}$ and ${\displaystyle b}$ are equidistant from ${\displaystyle u}$. This corresponds to the expectation of the ultrametricity hypothesis. The branches joining ${\displaystyle a}$ and ${\displaystyle b}$ to ${\displaystyle u}$ then have lengths ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$ (see the final dendrogram)

• First distance matrix update

We then proceed to update the initial proximity matrix ${\displaystyle D_{1}}$ into a new proximity matrix ${\displaystyle D_{2}}$ (see below), reduced in size by one row and one column because of the clustering of ${\displaystyle a}$ with ${\displaystyle b}$. Bold values in ${\displaystyle D_{2}}$ correspond to the new distances, calculated by retaining the maximum distance between each element of the first cluster ${\displaystyle (a,b)}$ and each of the remaining elements:

${\displaystyle D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30}$

${\displaystyle D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34}$

${\displaystyle D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23}$

Italicized values in ${\displaystyle D_{2}}$ are not affected by the matrix update as they correspond to distances between elements not involved in the first cluster.

• Second clustering

We now reiterate the three previous steps, starting from the new distance matrix ${\displaystyle D_{2}}$ :

Here, ${\displaystyle D_{2}((a,b),e)=23}$ is the lowest value of ${\displaystyle D_{2}}$, so we join cluster ${\displaystyle (a,b)}$ with element ${\displaystyle e}$.

• Second branch length estimation

Let ${\displaystyle v}$ denote the node to which ${\displaystyle (a,b)}$ and ${\displaystyle e}$ are now connected. Because of the ultrametricity constraint, the branches joining ${\displaystyle a}$ or ${\displaystyle b}$ to ${\displaystyle v}$, and ${\displaystyle e}$ to ${\displaystyle v}$, are equal and have the following total length: ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5}$

We deduce the missing branch length: ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3}$ (see the final dendrogram)

• Second distance matrix update

We then proceed to update the ${\displaystyle D_{2}}$ matrix into a new distance matrix ${\displaystyle D_{3}}$ (see below), reduced in size by one row and one column because of the clustering of ${\displaystyle (a,b)}$ with ${\displaystyle e}$ :

${\displaystyle D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39}$

${\displaystyle D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43}$

• Third clustering

We again reiterate the three previous steps, starting from the updated distance matrix ${\displaystyle D_{3}}$.

Here, ${\displaystyle D_{3}(c,d)=28}$ is the smallest value of ${\displaystyle D_{3}}$, so we join elements ${\displaystyle c}$ and ${\displaystyle d}$.

• Third branch length estimation

Let ${\displaystyle w}$ denote the node to which ${\displaystyle c}$ and ${\displaystyle d}$ are now connected. The branches joining ${\displaystyle c}$ and ${\displaystyle d}$ to ${\displaystyle w}$ then have lengths ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$ (see the final dendrogram)

• Third distance matrix update

There is a single entry to update: ${\displaystyle D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43}$

The final ${\displaystyle D_{4}}$ matrix is:

So we join clusters ${\displaystyle ((a,b),e)}$ and ${\displaystyle (c,d)}$.

Let ${\displaystyle r}$ denote the (root) node to which ${\displaystyle ((a,b),e)}$ and ${\displaystyle (c,d)}$ are now connected. The branches joining ${\displaystyle ((a,b),e)}$ and ${\displaystyle (c,d)}$ to ${\displaystyle r}$ then have lengths:

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=43/2=21.5}$

We deduce the two remaining branch lengths:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=21.5-11.5=10}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=21.5-14=7.5}$

WPGMA Dendrogram 5S data

The dendrogram is now complete. It is ultrametric because all tips (${\displaystyle a}$ to ${\displaystyle e}$) are equidistant from ${\displaystyle r}$ :

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=21.5}$

The dendrogram is therefore rooted by ${\displaystyle r}$, its deepest node.