K-Means++ Initialisation

The Problem with Random Initialisation

Standard K-Means picks $K$ initial centroids uniformly at random from the data points. This can lead to:

• Two (or more) centroids landing in the same true cluster, leaving another true cluster with no centroid.
• Poor local optima: the algorithm converges to a suboptimal solution with high WCSS.
• The need for many random restarts to find a good clustering, increasing runtime.

K-Means++ Solution

K-Means++ selects initial centroids so that they are spread out across the data. The probability of selecting a point as a new centroid is proportional to its squared distance from the nearest already-chosen centroid.

Algorithm

1. Choose the first centroid $\mu_1$ uniformly at random from the data points.
2. For each subsequent centroid ($k = 2, 3, \ldots, K$):
   • For each point $x$, compute $d(x)^2$, the squared distance to the nearest already-chosen centroid.
   • Choose a new centroid by sampling from the data points, where the probability of selecting $x$ is proportional to $d(x)^2$: $P(\text{choose } x) = \frac{d(x)^2}{\sum_{x'} d(x')^2}$
3. Proceed with standard K-Means (assignment and update steps) from these initial centroids.

Intuition

Points far from all existing centroids have high $d(x)^2$, so they are much more likely to be chosen. This ensures centroids are spread across different regions of the data space. The first centroid is random, the second is chosen far from the first, the third is chosen far from both, and so on.

Why It Is Better

K-Means++ provides theoretical guarantees: the expected WCSS of the final clustering is at most $O(\log K)$ times the optimal WCSS. In practice, it:

• Rarely produces empty clusters.
• Converges to solutions with consistently low WCSS.
• Reduces the need for multiple random restarts.

Practical Note

Scikit-learn uses K-Means++ as the default initialisation method (init='k-means++'). For exam purposes, understand both the standard random initialisation and the K-Means++ improvement. A question may ask: “Why might random initialisation be problematic, and how can it be improved?”

Comparison with Random Initialisation

Approach	How it works	WCSS quality	Runtime
Random	Pick $K$ points uniformly	Variable; often suboptimal	Fast init, may need many restarts
K-Means++	Probabilistic spread-out selection	Consistently near-optimal	Slightly slower init, fewer restarts needed
Multiple random restarts	Run K-Means many times, pick best WCSS	Good if enough restarts	Slow overall

Summary

Aspect	Detail
Problem	Random centroids may cluster together, missing true groups
Solution	Choose centroids with probability $\propto d(x)^2$
$d(x)$	Distance to the nearest already-chosen centroid
Effect	Spreads centroids across the data space
Guarantee	Expected WCSS $\leq O(\log K) \times \text{optimal}$
Usage	Default in scikit-learn

Past paper questions: y2024p3q7e