ML0058 K-means++

K-means++ is an improved way to initialize the centroids of K-means. Instead of picking all centroids uniformly at random, it selects them one by one with probability proportional to the squared distance from the already chosen centroids. This spreads the initial centroids out, sharply reducing the chance of poor clustering and helping the algorithm converge faster and more reliably. After initialization, standard K-means proceeds unchanged.

(1) First Centroid: Choose uniformly at random from the dataset.
(2) Distance Computation: For each point, compute its squared distance to the nearest already-chosen centroid.
(3) Weighted Selection: Pick the next centroid with probability proportional to that squared distance: far points are favored.
(4) Repeat Until K: Continue until all centroids are chosen, then run standard K-means.

Figure 1: K-means++ initialization (K=5): the distance-squared weighting spreads the starting centroids across all five natural groups, so the algorithm starts close to a good solution instead of gambling on random seeds.

Mathematical Formulation:

Where:

• is one of the already chosen centroids; is point ‘s squared distance to its nearest chosen centroid.
• is the probability of becoming the next centroid, proportional to , so points far from every chosen centroid are exponentially favored over nearby ones.
• The denominator normalizes over all data points; selection repeats until centroids exist.

Figure 2: Why initialization matters: with an unlucky random init (left), two centroids land in one group and the small top cluster is merged away; K-means++ (right) seeds one centroid per group and recovers all three clusters cleanly.