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.

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.
$\endgroup$
1
  • 1
    $\begingroup$ This is how the generic Lance-Williams formula for hierarchical agglomerative clustering "unwraps" for the centroid method. $\endgroup$
    – ttnphns
    May 13 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
    May 14 at 4:50
  • $\begingroup$ @loosi95 I have added the open form. $\endgroup$
    – gunes
    May 14 at 7:48

Your Answer

loosi95 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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