•We can think of this as trying to find the optimal solution to:
– Given points
p1… pn, find centers c1…ck
– and find mapping
f:{p1…pn}->{c1…ck}
–that minimizes C = (p1-f(p1))^2 + …+ (pn-f(pn))^2.
•Every step reduces C.
–The mean is the pt that minimizes sum of squared
distance to a set of points. So changing the
center to be the mean reduces this
distance.
–When we reassign a point to a closer center, we reduce
its distance to its cluster center.
•Convergence: since there are only a finite set of possible assignments.