3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is how the generic Lance-Williams formula for hierarchical agglomerative clustering "unwraps" for the centroid method. $\endgroup$
    – ttnphns
    Commented May 13, 2022 at 20:27

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – loosi95
    Commented May 14, 2022 at 4:50
  • $\begingroup$ @loosi95 I have added the open form. $\endgroup$
    – gunes
    Commented May 14, 2022 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.