1
$\begingroup$

The property (12.18) from here states that $$\frac{1}{|C_k|} \sum_{i, i' \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - x_{i'j}\right)^2 = 2 \sum_{i \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - \frac{1}{|C_k|} \sum_{i' \in C_k} x_{i'j}\right)^2$$ where $|C_k|$ denotes the number of observations in the k-th cluster. This property is used when tackling the K-means clustering optimization problem.

I can see that $$LHS = \frac{1}{|C_k|} \sum_{i \in C_k} \sum_{j = 1}^{p} \sum_{i' \in C_k} \left(x_{ij} - x_{i'j}\right)^2 = \frac{1}{|C_k|} \sum_{i \in C_k} \sum_{j = 1}^{p} \left[x_{ij}^2 + \sum_{i' \in C_k} \left(-2x_{ij}x_{i'j} + x_{i'j}^2\right)\right].$$ However, it is not clear if this is the proper way to verify the identity. Any help is greatly appreciated.

$\endgroup$
0
$\begingroup$

Define

$$\overline x_{kj}=\frac1{|C_k|}\sum_{i \in C_k} x_{ij} \quad\small,\,j=1,\ldots,p\,;\,k=1,\ldots,K$$

Then looks to me that

\begin{align} \sum_{i, i' \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - x_{i'j}\right)^2 &=\sum_{i, i' \in C_k}\sum_{j = 1}^{p}\left\{(x_{ij}-\overline x_{kj})-(x_{i'j}-\overline x_{kj})\right\}^2 \\&=\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2+\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{i'j}-\overline x_{kj})^2 \\&=2\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2 \\&=2|C_k|\sum_{i \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2 \end{align}

The product term in the second step vanishes because

$$\sum_{i \in C_k}(x_{ij}-\overline x_{kj})=|C_k|\overline x_{kj}-|C_k|\overline x_{kj}=0$$

So I think this works the same way as the following formula does:

$$\frac1{n^2}\sum_{1\le i,j\le n}(x_i-x_j)^2=\frac{2}n\sum_{i=1}^n (x_i-\overline x)^2$$

$\endgroup$

Your Answer

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.