What a K-means diagram must show

Topic: K-means clustering · more questions on this topic
‹ The within-cluster sum cannot choose K Euclidean clusters and mixture components ›

Consider Euclidean K-means in two dimensions with K=3 and distinct fitted centres.

  1. Describe the possible cluster boundaries and draw a labelled example containing observations, centres and the resulting regions.

  2. Explain what the algorithm is minimising and how the centres are updated.

  3. Explain why different starting centres can produce different answers and how you would respond in practice.

A bisector is only a candidate boundary. Keep the part where neither of the other centres is closer, then connect this geometry to the least-squares objective.

  1. Points are assigned to their nearest centre. Equality of squared distances to \mathbf{m}_j and \mathbf{m}_k gives

2(\mathbf{m}_k-\mathbf{m}_j)^\top\mathbf{x}=\|\mathbf{m}_k\|^2-\|\mathbf{m}_j\|^2,

a straight perpendicular bisector. The active portions form convex Voronoi cells. A full bisector need not be an actual boundary where a third centre is closer. A valid sketch has three labelled centres, data near them, and the appropriate clipped bisectors. For centres (0,0), (4,0) and (0,4), the active boundaries are x_1=2 for x_2\le 2, x_2=2 for x_1\le 2, and x_1=x_2 for x_1\ge 2.

  1. The algorithm minimises

\sum_{k=1}^3\sum_{i\in C_k}\|\mathbf{x}_i-\mathbf{m}_k\|^2.

For fixed nonempty assignments, each updated centre is the arithmetic mean of its assigned observations.

  1. The joint optimisation is non-convex, so alternating assignment and updating can stop at different local solutions. Use multiple sensible starts, compare objective values, and inspect stability. Multiple starts do not prove global optimality.