K-Means++ Initialization

Standard k-means starts by placing $k$ centroids at random, then alternates assigning points to their nearest centroid and recomputing centroids as the mean of their assigned points. That final result depends heavily on the random starting positions: two centroids can land close together by chance, splitting one true cluster in two while merging two others into one, and the algorithm has no mechanism to escape that bad start.

K-means++ fixes this by choosing the initial centroids deliberately spread apart, rather than uniformly at random. The first centroid is chosen randomly from the data. Each subsequent centroid is then chosen from the remaining points with probability proportional to the squared distance to the nearest already-chosen centroid — points far from existing centroids are far more likely to be picked next.

Worked example. Data forms two obvious clusters, one near (0,0) and one near (10,10). Random initialization has a real chance of dropping both starting centroids inside the same cluster, say at (0,0) and (1,1), leaving the (10,10) cluster completely unrepresented until reassignment slowly corrects it, if it corrects at all. K-means++ picks the first centroid randomly, say near (0,0), then computes squared distances from every point to it — points near (10,10) are now roughly 200 times farther than points near (0,0) — making the second centroid overwhelmingly likely to land in the (10,10) cluster on the very first draw, giving the algorithm a fair start on both clusters from iteration one.