Choosing Where K-Means Starts

K-Means drops its $K$ starting centroids at random, and an unlucky drop can leave it stuck with a poor clustering, for example when two centroids land inside the same natural group. K-Means++ is a smarter way to choose the starting centroids. It still uses randomness, but it tilts the odds toward points that are far from every centroid chosen so far.

The recipe, for a list of points and k clusters:

1. First centroid: pick one point, every point equally likely.
2. Every next centroid:
   • For each point, find its squared straight-line distance to the nearest centroid chosen so far. Call it $D^2$. A point that is already a centroid has $D^2 = 0$.
   • Pick one point at random, with each point's chance proportional to its $D^2$: a point with twice the $D^2$ is twice as likely to be picked.
3. Repeat step 2 until k centroids have been chosen.

So that everyone gets the same answer, the random numbers have been drawn in advance. draws holds k numbers, each at least 0 and less than 1. Use them like this:

• First centroid: the point at index int(draws[0] * len(points)).
• Centroid number $c$ (for $c = 1, 2, \dots$): add up every point's $D^2$ to get a total $S$, and set a target of draws[c] $\times S$. Then go through the points in order, keeping a running sum of their $D^2$ values, and pick the first point whose running sum is greater than the target.

Task: write kmeans_pp_starts(points, k, draws) and return the indices of the chosen points, in the order they were chosen.

• Every point is a list of coordinates, and all points have the same number of them.
• The points always include at least k different positions, so there is always a valid next centroid.

The running sum is the standard trick for drawing at random with uneven chances. Lay all the $D^2$ values end to end along a line of length $S$, drop a pin at draws[c] $\times S$, and take whichever point's stretch the pin lands in. Far-away points own long stretches, so they are hard to miss.