Exercise 6.13

Let it equal to 0, we have ${\mu }_j=\frac{1}{\left|S_j\right|}{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{x_n\in S_j}{x}_n$ are the centroids of the clusters and minimize $E_{\mathit{in}}$.

Suppose this is not true, there must exist a point that doesn’t belong to the cluster which has the closest center to it. Let’s call the point $x^{\text{∗}}$, and its closest center ${\mu }_j$, such that $\parallel x^{\text{∗}}-{\mu }_j\parallel \le \parallel x^{\text{∗}}-{\mu }_l\parallel$ for $l=1,\dots ,k$. Under our assumption, $x^{\text{∗}}\notin S_j$.

There must exist another cluster, e.g. $S_i$, such that $x^{\text{∗}}\in S_i$, and $\parallel x^{\text{∗}}-{\mu }_j\parallel \le \parallel x^{\text{∗}}-{\mu }_i\parallel$.

We can compare $E_i,E_j$ components in $E_{\mathit{in}}$, where

and $E_j={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{x_n\in S_j}\parallel x_n-{\mu }_j{\text{∥}}^2.$$$

It’s clear that $E_i+E_j$ doesn’t achieve its minimum value under the assumption. Because if we just put $x^{\text{∗}}$ into $S_j$, we replace $\parallel x^{\text{∗}}-{\mu }_i{\text{∥}}^2$ with $\parallel x^{\text{∗}}-{\mu }_j{\text{∥}}^2$, which is clearly less than the former. So we reduce the sum of $E_i+E_j$ and thus $E_{\mathit{in}}$.

We conclude that for all points,we should put them into the cluster that has the closest center.