User:Manudouz/sandbox/single-linkage clustering

Working example

First step

• First clustering

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

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

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

• First branch length estimation

Let $u$ denote the node to which $a$ and $b$ are now connected. Setting $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ ensures that elements $a$ and $b$ are equidistant from $u$. This corresponds to the expectation of the ultrametricity hypothesis. The branches joining $a$ and $b$ to $u$ then have lengths $\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 $D_{1}$ into a new proximity matrix $D_{2}$ (see below), reduced in size by one row and one column because of the clustering of $a$ with $b$. Bold values in $D_{2}$ correspond to the new distances, calculated by retaining the minimum distance between each element of the first cluster $(a,b)$ and each of the remaining elements:

$D_{2}((a,b),c)=min(D_{1}(a,c),D_{1}(b,c))=min(21,30)=21$

$D_{2}((a,b),d)=min(D_{1}(a,d),D_{1}(b,d))=min(31,34)=31$

$D_{2}((a,b),e)=min(D_{1}(a,e),D_{1}(b,e))=min(23,21)=21$

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

Second step

• Second clustering

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

	(a,b)	c	d	e
(a,b)	0	21	31	21
c	21	0	28	39
d	31	28	0	43
e	21	39	43	0

Here, $D_{2}((a,b),c)=21$ and $D_{2}((a,b),e)=21$ are the lowest values of $D_{2}$, so we join cluster $(a,b)$ with element $c$ and with element $e$.

• Second branch length estimation

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

We deduce the missing branch length: $\delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2$ (see the final dendrogram)

• Second distance matrix update

We then proceed to update the $D_{2}$ matrix into a new distance matrix $D_{3}$ (see below), reduced in size by two rows and two columns because of the clustering of $(a,b)$ with $c$ and with $e$ : $D_{3}(((a,b),c,e),d)=min(D_{2}((a,b),d),D_{2}(c,d),D_{2}(e,d))=min(31,28,43)=28$

Final step

The final $D_{3}$ matrix is:

	((a,b),c,e)	d
((a,b),c,e)	0	28
d	28	0

So we join clusters $((a,b),c,e)$ and $d$.

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

$\delta (((a,b),c,e),r)=\delta (d,r)=28/2=14$

We deduce the remaining branch length:

$\delta (v,r)=\delta (a,r)-\delta (a,v)=\delta (b,r)-\delta (b,v)=\delta (c,r)-\delta (c,v)=\delta (e,r)-\delta (e,v)=14-10.5=3.5$

The single-linkage dendrogram

Single Linkage Dendrogram 5S data

The dendrogram is now complete. It is ultrametric because all tips ($a$, $b$, $c$, $e$, and $d$) are equidistant from $r$ :

$\delta (a,r)=\delta (b,r)=\delta (c,r)=\delta (e,r)=\delta (d,r)=14$

The dendrogram is therefore rooted by $r$, its deepest node.