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.


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}$$
