# Uniform Effect of K-means Clustering

In the following link is discussed the uniform Effect of K-means Clustering:

He used the following equation:

$$\frac{\displaystyle2 d(C_1,C_2)}{\displaystyle n_1n_2}=\frac{\displaystyle d(C_1,C_1)}{\displaystyle n_1^2}+\frac{\displaystyle d(C_2,C_2)}{\displaystyle n_2^2}+2||m_1−m_2||^2.$$

where

$$d(C_1,C_2)=\sum_{x_i\in C_1}\sum_{x_j\in C_2}||x_i−x_j||^2$$ with $$|C_1|=n_1$$ and $$|C_2 |=n_2$$.

I tried to prove this, but I do not get this. He uses the fact that

$$d(C_1,C_1)=2(n_1-1)\sum_{i=1}^{n_1} ||x_i||^2 -4 \sum_{1\leq i < j \leq n_1}\langle x_i,x_j\rangle.$$

$$d(C_2,C_2)=2(n_2-1)\sum_{i=1}^{n_2} ||y_i||^2 -4 \sum_{1\leq i < j \leq n_2}\langle y_i,y_j\rangle.$$

$$d(C_1,C_2)=2n_2\sum_{i=1}^{n_1} ||x_i||^2+2n_1\sum_{i=1}^{n_2} ||y_i||^2 -4 \sum_{1\leq i\leq n_1}\sum_{1\leq j\leq n_2}\langle x_i,y_j\rangle.$$

And furthermore with

$$||m_1−m_2||^2=\langle \sum_{i=1}^{n_1}x_i/n_1-\sum_{j=1}^{n_1}y_j/n_2,\sum_{i=1}^{n_1}x_i/n_1-\sum_{j=1}^{n_1}y_j/n_2 \rangle = \frac{1}{\displaystyle n_1^2}\sum_{i=1}^{n_1} ||x_i||^2 + \frac{2}{\displaystyle n_1^2}\sum_{1\leq i < j\leq n_1} \langle x_i, x_j\rangle +\frac{1}{\displaystyle n_2^2}\sum_{i=1}^{n_2} ||y_i||^2 + \frac{2}{\displaystyle n_2^2}\sum_{1\leq i < j\leq n_2} \langle y_i, y_j\rangle - \frac{2}{n_1n_2} \sum_{1\leq i\leq n_1}\sum_{1\leq j\leq n_2}\langle x_i,y_j\rangle,$$

I obtain that

$$\frac{\displaystyle d(C_1,C_2)}{\displaystyle n_1n_2}=\frac{\displaystyle d(C_1,C_1)}{\displaystyle n_1^2}+\frac{\displaystyle d(C_2,C_2)}{\displaystyle n_2^2}+2||m_1−m_2||^2.$$

Where is my error?

• I suggest working through the case $n_1=1, n_2=2$ to see where your derivation goes wrong (the paper is definitely correct). Maybe you've forgotten that $||x_i-x_j||^2$ appears twice in each $d(C_i,C_i)$? – Matthew Towers Nov 23 '18 at 17:59

I think the problem is in the computation of $$d(C_1, C_2)$$: \begin{align} d(C_1, C_2) &= \sum_{i =1}^{n_1}\sum_{j =1}^{n_2}|| x_i - y_j||^2\\ &= \sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle x_i - y_j, x_i - y_j\rangle \\ &= \sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\left(\langle x_i, x_i\rangle+\langle x_i , - y_j\rangle+\langle - y_j, x_i\rangle+\langle - y_j, - y_j\rangle \right)\\ &= \sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle x_i, x_i\rangle-2\sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle x_i , y_j\rangle+\sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle y_j, y_j\rangle \\ &= \sum_{i =1}^{n_1}n_2\langle x_i, x_i\rangle-2\sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle x_i , y_j\rangle+n_1\sum_{j =1}^{n_2}\langle y_j, y_j\rangle \\ &= n_2\sum_{i =1}^{n_1}|| x_i||^2+n_1\sum_{j =1}^{n_2}|| y_j||^2-2\sum_{i =1}^{n_1}\sum_{j =1}^{n_2}\langle x_i , y_j\rangle \\ \end{align}