Distance between two clusters after their joining in centroid linkage

For a distance between two clusters A and B of objects given by $$d_{AB}=\left \|{m_{A}-m_{B}} \right \|^{2}$$ , where $$m_{A}$$ is the mean of the objects in cluster $$A$$, show that the formula expressing the distance between a cluster $$k$$ and a cluster formed by joining $$i$$ and $$j$$ is

$$d_{i+j,k}=\frac{n_{i}}{n_{i}+n_{j}}d_{ik}+\frac{n_{j}}{n_{i}+n_{j}}d_{jk}-\frac{n_{i}n_{j}}{(n_{i}+n_{j})^2}d_{ij}$$

where there are $$n_{i}$$ objects in group $$i$$. This is the update rule for the centroid method of hierarchical agglomeration.

Could anyone help me how to get it?
I calculate mean of each cluster, and substitute but I'm not familiar with norm operations.

New contributor
loosi95 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• This is how the generic Lance-Williams formula for hierarchical agglomerative clustering "unwraps" for the centroid method. May 13 at 20:27

A bit tricky to come up with the manipulations, but let's begin with expanding $$d_{i+j,k}$$: \begin{align}d_{i+j,k}&=||m_{i+j}-m_k||^2=\left|\left|\frac{m_in_i+n_jm_j}{n_i+n_j}-m_k\right|\right|^2\\&=\frac{1}{(n_i+n_j)^2}\left|\left|n_i(m_i-m_k)+n_j(m_j-m_k)\right|\right|^2\end{align}

We can open a two norm as follows: $$||a+b||^2=(a+b)^T(a+b)=a^Ta+a^Tb+b^Ta+b^Tb$$

This yields $$d_{i+j,k}=\frac{n_i^2}{(n_i+n_j)^2}d_{ik}+\frac{n_j^2}{(n_i+n_j)^2}d_{jk}+\frac{n_in_j}{(n_i+n_j)^2}(m_i-m_k)^T(m_j-m_k)+\frac{n_in_j}{(n_i+n_j)^2}(m_j-m_k)^T(m_i-m_k)$$

We'll try to write the third and fourth terms using distances. Take the third term without the scalar: $$(m_i-m_k)^T(m_j-m_k)=(m_i-m_k)^T((m_i-m_k)-(m_i-m_j))=d_{ik}-(m_i-m_k)^T(m_i-m_j)$$ The fourth term would symmetrically (exchange $$i$$ with $$j$$) be: $$d_{jk}-(m_j-m_k)^T(m_j-m_i)$$

The third and fourth terms have the same scalar, so we can sum them (also open the parantheses):

\begin{align}&\rightarrow d_{jk}+d_{ik}-(m_i^Tm_i-m_i^Tm_j-m_k^Tm_i+m_k^Tm_j)-(m_j^Tm_j-m_j^Tm_i-m_k^Tm_j+m_k^Tm_i)\\&\rightarrow d_{jk}+d_{ik}-(m_i^Tm_i+m_J^Tm_j-m_i^Tm_j-m_j^Tm_i)\\&\rightarrow d_{jk}+d_{ik}-d_{ij}\end{align}

Substitute these into the original equation: \begin{align}d_{i+j,k}&=\left(\frac{n_i^2}{(ni+n_j)^2}+\frac{n_in_j}{(n_i+n_j)^2}\right)d_{ik}+\left(\frac{n_j^2}{(ni+n_j)^2}+\frac{n_in_j}{(n_i+n_j)^2}\right)d_{jk}-\frac{n_in_j}{(n_i+n_j)^2}d_{ij}\\&=\frac{n_i}{n_i+n_j}d_{ik}+\frac{n_j}{n_i+n_j}d_{jk}-\frac{n_in_j}{(n_i+n_j)^2}d_{ij}\end{align}

• Thank you so much. You sum third and forth terms but the result is not true. Would you please write again with more details? Becouse I sum them but I can't get the result you wrote. May 14 at 4:50
• @loosi95 I have added the open form. May 14 at 7:48