# Derivation of Ward's formula for agglomerative clustering

Figure describe formula of ward method for hierarchical or agglomarative clustering i.e. increment of total error after merging two cluster.

How did they get

$$\frac{n_A\cdot n_B}{n_A+n_B} ||\vec m_A-\vec m_B||^2$$

from first line of formula as shown in figure?

• Hi, if my answer clarified your understanding of this formula, may I ask you to mark my answer as the right answer by clicking checkmark at the top left of its body, just below its score? :) – VividD May 18 '17 at 3:40

## 1 Answer

I will be using these facts without proof (but the proofs either follow directly from definitions or are straightforward): The vector of the centroid of a set of points is arithmetic mean of all vectors of the points in the set. Also, the centroid of the union of two sets of point is on the straight line connecting centroids of these two sets, and it divides that straight line into two parts whose ratio is determined by the ratio of number of points of in these sets.

Let's consider following series of identities:

$\sum_{i\in A} \|\vec{x}_i-\vec{m}_{A\cup B}\|^2 =$

$$= \sum_{i\in A} \Big\Vert \vec{x}_i-\Big(\vec{m}_{A} - \frac{n_B}{n_A+n_B} (\vec{m}_{A} - \vec{m}_{B})\Big)\Big\Vert^2$$

$$= \sum_{i\in A} \Big\Vert\big(\vec{x}_i-\vec{m}_{A}\big) + \frac{n_B}{n_A+n_B} \big(\vec{m}_{A} - \vec{m}_{B}\big)\Big\Vert^2$$

$$= \sum_{i\in A} \Big\Vert\big(\vec{x}_i-\vec{m}_{A}\big)\Big\Vert^2 + 2 \cdot \sum_{i\in A}\big(\vec{x}_i-\vec{m}_{A}\big) \cdot \frac{n_B}{n_A+n_B} \big(\vec{m}_{A} - \vec{m}_{B}\big) + n_A \cdot \Big\Vert\frac{n_B}{n_A+n_B} \big(\vec{m}_{A} - \vec{m}_{B}\big)\Big\Vert^2\big)$$

$$= \sum_{i\in A} \Big\Vert\big(\vec{x}_i-\vec{m}_{A}\big)\Big\Vert^2 + n_A \cdot \Big\Vert\frac{n_B}{n_A+n_B} \big(\vec{m}_{A} - \vec{m}_{B}\big)\Big\Vert^2\big)$$

$$= \sum_{i\in A} \Vert\vec{x}_i-\vec{m}_{A}\Vert^2 + \frac{n_A n_B^2}{(n_A+n_B)^2} \Vert\vec{m}_{A} - \vec{m}_{B}\Vert^2$$

Similarly:

$$\sum_{i\in B} \|\vec{x}_i-\vec{m}_{A\cup B}\|^2 = \sum_{i\in B} \Vert\vec{x}_i-\vec{m}_{B}\Vert^2 + \frac{n_A^2 n_B}{(n_A+n_B)^2} \Vert\vec{m}_{A} - \vec{m}_{B}\Vert^2$$

By adding:

$$\sum_{i\in {A\cup B}} \|\vec{x}_i-\vec{m}_{A\cup B}\|^2 = \sum_{i\in A} \Vert\vec{x}_i-\vec{m}_{A}\Vert^2 +\sum_{i\in B} \Vert\vec{x}_i-\vec{m}_{B}\Vert^2 + \frac{n_A^2 n_B + n_A n_B^2}{(n_A+n_B)^2} \Vert\vec{m}_{A} - \vec{m}_{B}\Vert^2$$

Or:

$$\sum_{i\in {A\cup B}} \|\vec{x}_i-\vec{m}_{A\cup B}\|^2 - \sum_{i\in A} \Vert\vec{x}_i-\vec{m}_{A}\Vert^2 - \sum_{i\in B} \Vert\vec{x}_i-\vec{m}_{B}\Vert^2 = \frac{n_A n_B (n_A + n_B)}{(n_A+n_B)^2} \Vert\vec{m}_{A} - \vec{m}_{B}\Vert^2$$

Or:

$$\Delta \big(A, B\big) = \frac{n_A n_B}{n_A+n_B} \Vert\vec{m}_{A} - \vec{m}_{B}\Vert^2$$