4

In cluster analysis I have frequently encountered a statement that the total sum of squares $\sum\limits_{i = 1}^n {{{({x_i} - \overline x )}^2}} $ being equal to within-cluster sum of squares $\sum\limits_{k = 1}^K {\sum\limits_{i = 1}^{{n_k}} {{z_{ik}}{{({x_i} - {{\overline x }_k})}^2}} } $ and between cluster sum of squares $\sum\limits_{k = 1}^K {\frac{{{n_k}}}{n}{{({{\overline x }_k} - \overline x )}^2}} $, where $n$ is the total number of elements, $K$ is the number of clusters, $n_k$ is the number of elements in the $k$th cluster, ${{{\overline x }_k}}$ is the mean of the $k$th cluster, $z_{ik}$ is an indicator function ${z_{ik}} = \left\{ {\begin{array}{*{20}{c}} 1&{{x_i} \in {\rm{cluster }}k}\\ 0&{{x_i} \notin {\rm{cluster }}k} \end{array}} \right.$. Anyone can provide a proof that the following equation indeed holds?

$\sum\limits_{i = 1}^n {{{({x_i} - \overline x )}^2}} = \sum\limits_{k = 1}^K {\sum\limits_{i = 1}^{{n_k}} {{z_{ik}}{{({x_i} - {{\overline x }_k})}^2}} } + \sum\limits_{k = 1}^K {{{{n_k}}}{{({{\overline x }_k} - \overline x )}^2}} $

Thank you!

Tony
  • 1,583
  • 4
  • 15
  • 20
  • 2
    The factor $n_k/n$ in the second term should probably be $n_k$. – Lucas Apr 18 '15 at 08:13
  • Thanks Lucas. You are right. I have edited the question. – Tony Apr 18 '15 at 15:52
  • 1
    To those who marked this question as duplicate. I don't think my question duplicates "Partitioning sum of squares". – Tony Apr 18 '15 at 15:53
  • Can you explain why? It would help if you edited your question to state what you understand from the other Q & what you still need to know. Then you might get the answers you need, rather than just material that already didn't help you. – gung - Reinstate Monica Apr 18 '15 at 16:13

1 Answers1

4

One way to see this would be to use the law of total variance, $$\text{Var}[X] = \text{E}[\text{Var}[X \mid K]] + \text{Var}[\text{E}[X \mid K]],$$ applied to the distributions \begin{align} p(x \mid k) &= \sum_i \frac{z_{ik}}{n_k} \delta(x - x_i), & p(k) &= \frac{n_k}{n}. \end{align}

The more direct proof is straightforward but lengthy, which is probably why it wasn't mentioned in your books. Using the binomial theorem and \begin{align} \sum_i z_{ik} &= n_k, & \sum_k z_{ik} &= 1, \end{align} it follows that \begin{align} \sum_i (x_i - \bar x)^2 &= \sum_i \sum_k z_{ik} (x_i - \bar x)^2 \\ &= \sum_i \sum_k z_{ik} (x_i - \bar x_k + \bar x_k - \bar x)^2 \\ &= \sum_k \sum_i z_{ik} \left( (x_i - \bar x_k)^2 + 2 (x_i - \bar x_k) (\bar x_k - \bar x) + (\bar x_k - \bar x)^2 \right) \\ &= \sum_k \sum_i z_{ik} (x_i - \bar x_k)^2 + 2 \sum_k \sum_i z_{ik} (x_i - \bar x_k) (\bar x_k - \bar x) + \sum_k \sum_i z_{ik} (\bar x_k - \bar x)^2 \\ &= \sum_k \sum_i z_{ik} (x_i - \bar x_k)^2 + 2 \sum_k (\bar x_k - \bar x) \left( \sum_i z_{ik} x_i - \sum_i z_{ik} \bar x_k \right) + \sum_k n_k (\bar x_k - \bar x)^2 \\ &= \sum_k \sum_i z_{ik} (x_i - \bar x_k)^2 + 2 \sum_k (\bar x_k - \bar x) \left( n_k \bar x_k - n_k \bar x_k \right) + \sum_k n_k (\bar x_k - \bar x)^2 \\ &= \sum_k \sum_i z_{ik} (x_i - \bar x_k)^2 + \sum_k n_k (\bar x_k - \bar x)^2. \end{align}

Lucas
  • 5,692
  • 29
  • 39