k-means++ initialization

The problem, from first principles

Plain k-means picks starting centers uniformly at random, and bad luck can drop two starting centers into the same blob. The run then converges to a poor local optimum. k-means++ spreads the starting centers out: the first center is random, and each later center is chosen with probability proportional to its squared distance from the nearest center already picked. Far-away points are likelier, so new centers land in unexplored regions.

Implement kmeans_plus_plus_init(X, k, seed=0), which returns a (k, d) array whose rows are chosen points from X.

1. Pick the first center uniformly at random.
2. For each next center, compute D² for every point (squared distance to the nearest chosen center) and sample a point with probability D² / ΣD².
3. If every D² is zero (all remaining points coincide with a center), pick uniformly at random.

Constraints

• 1 <= k <= n, otherwise raise ValueError.
• The same seed must give the same centers.
• Do not modify X.

Hints

Open one at a time. Each gives away a little more than the last.