# Euclidean Cluster Analysis

In ALGORITHM AS58 they explain Euclidian Cluster Analyis.

The article explain the algorithm that the observations are reassigned from cluster k to cluster l if it is nearer the center of latter. That is if $$d^2_l < d^2_k$$ where $d_i$ is the distance from the centre of cluster i. More effective way would be to reassign the observation if the squared deviation from the centre of cluster l is less than that from the centre of cluster k, even if the centres are simultaneously repositioned. That is when: $$\frac{n_l}{n_l+1}d^2_l < \frac{n_k}{n_k-1}d^2_k$$ where $n_i$ is the number of observations in cluster i.

I need to show how to derive the second formula from the first. Can anybody help me in showing how you can get from the first formula to the second one?

Let $C_i$ be a cluster and $\mu_i = |C_i|^{-1}\sum_{x\in C_i} x$. Then the point-cost of placing a point $y$ in cluster $j$ is given by:$$\xi_j(y) = \sum_{x\in C_j} || x - y ||_2^2$$ We can also define the cost of cluster $j$ via: $\eta_j = \xi_j(\mu_j)$.
First, note that $$\xi_j(z) = \eta_j + N_j\,|| \mu_j - z ||_2^2 \tag{1}$$ where $N_j = |C_j|$. Why? Because \begin{align*} \xi_j(z) - \eta_j &= \sum_{x\in C_j} ||x-\mu_j||_2^2 - ||x-\mu_j||_2^2\\ &= \sum_{x\in C_j}\sum_k z_k^2 - \mu_{jk}^2 - 2x_kz_k + 2x_k\mu_{jk}\\ &= \sum_k N_jz_k^2 - N_j\mu^2_{jk} - 2z_kN_j\mu_{jk} +2\mu_{jk}^2N_j\\ &= N_j||\mu_j - z||_2^2 \end{align*} Next consider the merge cost $\Delta_{ij}$, which is the cost of merging clusters $C_i$ and $C_j$. Let $C_{v} = C_i \cup C_j$. Then $$\Delta_{ij} = \eta_v - \eta_i -\eta_j$$ Using equation(1) and $\mu = [N_i\mu_i + N_j\mu_j]/(N_i + N_j)$, we get that: \begin{align*} \eta_v &= \xi_i(\mu_v) + \xi_j(\mu_v) \\ &= \eta_i + N_i||\mu_i - \mu_v||_2^2 + \eta_j + N_j||\mu_j - \mu_v||_2^2\\ &= \eta_i + \eta_j + \frac{N_jN_i^2}{(N_j + N_i)^2}||\mu_i - \mu_j||_2^2 + \frac{N_iN_j^2}{(N_j + N_i)^2}||\mu_j - \mu_i||_2^2\\ &= \eta_i + \eta_j + \frac{N_iN_j}{N_j + N_i}||\mu_j - \mu_i||_2^2 \\ \therefore\; \Delta_{ij} &= \frac{N_iN_j}{N_j + N_i}||\mu_j - \mu_i||_2^2 \tag{2} \end{align*} We next want to look at the cost of moving a point, i.e. reassigning from one cluster to another. Let $p\in C_i$. Then then change in cost of reassignment of $p$ from $C_i$ to $C_j$ is: $$\Theta_{ij}(p) = \eta_w + \eta_u - \eta_{i} - \eta_j$$ where $C_w = C_i \setminus p$, $C_p = \{p\}$, and $C_u = C_j \cup C_p$. Notice that: $$\eta_u - \eta_j = \Delta_{jp} = \frac{N_j}{N_j + 1}||\mu_j - p||_2^2$$ using $\eta_p=0$. Further, note that $$\eta_i - \eta_w = \Delta_{wp} = \frac{N_i-1}{N_i}||\mu_w - p||_2^2$$ using $C_i = C_w \cup C_p$. Next, use $\mu_w = (N_i\mu_i - p)/(N_i -1)$ to get $$\frac{N_i - 1}{N_i}||\mu_w-p||_2^2 = \frac{1}{(N_i - 1)N_i}||N_i\mu_i-p-(N_i-1)p||_2^2 = \frac{N_i}{N_i - 1}|| \mu_i-p ||_2^2$$
Clearly, we want to perform a reassignment only if the cost of reassignment is negative. (Meaning the cost was higher before the reassignment). That is, $\Theta_{ij}(p) < 0$. But we have \begin{align*} \Theta_{ij}(p) &= (\eta_u - \eta_j) - (\eta_i - \eta_w) < 0 \\ \implies\;&\; \eta_u - \eta_j < \eta_i - \eta_w \\ \therefore\;&\; \frac{N_j}{N_j + 1}||\mu_j - p||_2^2 < \frac{N_i}{N_i - 1}|| \mu_i-p ||_2^2 \end{align*} when an improvement occurs, as required.