ML0057 K-means

K-means is an iterative unsupervised algorithm that partitions data into clusters by minimizing intra-cluster distances (within-cluster variance). It alternates between assigning points to the nearest centroid and recomputing centroids until convergence. It is fast and easy to implement, but sensitive to initialization and to non-convex cluster shapes.

(1) Initialization: Choose initial centroids (randomly, or with K-means++).
(2) Assignment Step: Assign every point to its closest centroid by Euclidean distance.
(3) Update Step: Recompute each centroid as the mean of the points assigned to it.
(4) Convergence: Repeat assignment and update until the centroids stabilize or a stopping criterion is met.

Figure 1: K-means (K=3) converged on blob data: colors mark the final assignments and the red X’s are the centroids: each is the mean of its cluster, and every point belongs to its nearest centroid’s cluster.

Mathematical Formulation:

Where:

• is a data point and the centroid of cluster (first formula: Euclidean assignment distance, = number of features).
• is the set of points currently assigned to cluster ; the update sets the centroid to their component-wise mean, the minimizer of squared distances for a fixed assignment.