Dejemos que $C_i$ sea una agrupación y $ \mu_i = |C_i|^{-1}\sum_{x\in C_i} x $ . Entonces el punto-coste de colocar un punto $y$ en grupo $j$ está dada por: $$ \xi_j(y) = \sum_{x\in C_j} || x - y ||_2^2 $$ También podemos definir el costo de la agrupación $ j $ a través de: $ \eta_j = \xi_j(\mu_j) $ .
En primer lugar, hay que tener en cuenta que $$ \xi_j(z) = \eta_j + N_j\,|| \mu_j - z ||_2^2 \tag{1} $$ donde $N_j = |C_j|$ . ¿Por qué? Porque \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*} A continuación, considere la coste de fusión $\Delta_{ij}$ que es el coste de la fusión de los clusters $C_i$ y $C_j$ . Sea $C_{v} = C_i \cup C_j$ . Entonces $$ \Delta_{ij} = \eta_v - \eta_i -\eta_j $$ Utilizando la ecuación(1) y $\mu = [N_i\mu_i + N_j\mu_j]/(N_i + N_j)$ Lo entendemos: \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*} A continuación, queremos analizar el coste de mover un punto, es decir, de reasignarlo de un clúster a otro. Sea $p\in C_i$ . Entonces cambio en el coste de reasignación de $p$ de $C_i$ a $C_j$ es: $$ \Theta_{ij}(p) = \eta_w + \eta_u - \eta_{i} - \eta_j $$ donde $C_w = C_i \setminus p$ , $C_p = \{p\}$ y $C_u = C_j \cup C_p$ . Fíjate que: $$ \eta_u - \eta_j = \Delta_{jp} = \frac{N_j}{N_j + 1}||\mu_j - p||_2^2 $$ utilizando $\eta_p=0$ . Además, tenga en cuenta que $$ \eta_i - \eta_w = \Delta_{wp} = \frac{N_i-1}{N_i}||\mu_w - p||_2^2 $$ utilizando $C_i = C_w \cup C_p$ . A continuación, utilice $\mu_w = (N_i\mu_i - p)/(N_i -1)$ para conseguir $$ \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 $$
Está claro que queremos realizar una reasignación sólo si el costo de reasignación es negativo . (Lo que significa que el coste era mayor antes de la reasignación). Eso es, $\Theta_{ij}(p) < 0$ . Pero tenemos \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*} cuando se produzca una mejora, según sea necesario.
Véase Telgarsky y Vattani, Método Hartigan: clustering k-means sin Voronoi .
