Exercise 11.10 - Deriving the K-means cost function

Answers

For every term for a given $k$ , note that:

\begin{aligned} \sum_{i : z_{i} = k} \sum_{i^{'} : z_{i^{'}} = k} {(x_{i} - x_{i^{'}})}^{2} & = \sum_{i} \sum_{i^{'}} {[(x_{i} - \bar{x}) - (x_{i^{'}} - \bar{x})]}^{2} \\ = \sum_{i} \sum_{i^{'}} {(x_{i} - \bar{x})}^{2} + {(x_{i^{'}} - \bar{x})}^{2} - 2 (x_{i} - \bar{x}) (x_{i^{'}} - \bar{x}) \\ = 2 \cdot n_{k} \cdot \sum_{i} {(x_{i} - \bar{x})}^{2} - 2 [\sum_{i} (x_{i} - \bar{x})] [\sum_{i^{'}} (x_{i^{'}} - \bar{x})] \\ = 2 \cdot n_{k} \cdot \sum_{i} {(x_{i} - \bar{x})}^{2} . \end{aligned}

This finishes the proof. One can also adopt (11.132)-(11.135) for the desired result.

solour_lfq

2021-03-24 13:42