Need a little help understanding K-means++ seeding

Question

I have been working on a project that involves using K-means clustering for generating adaptive palettes from images. I understand the general process of K-means clustering, and I understand the reason for using K-means++ seeding, but the initialization algorithm confuses me a little bit.

Here is the algorithm taken from Wikipedia for quick reference:

1. Choose one center uniformly at random from among the data points.
2. For each data point $x$, compute $D(x)$, the distance between $x$ and the nearest center that has already been chosen.
3. Choose one new data point at random as a new center, using a weighted probability distribution where a point $x$ is chosen with probability proportional to $D(x^2)$.
4. Repeat Steps 2 and 3 until $k$ centers have been chosen.
5. Now that the initial centers have been chosen, proceed using standard k-means clustering.

The part that is tripping me up is Step 3. If my understanding is correct, K-means++ seeding is meant to spread the initial clusters out to improve cluster results and also to improve convergence time. I am having a hard time understanding the weighted probability distribution proportional to the squared distance. My first thought was that the initial clusters after the first one would be spread out as far as possible, but I have some sort of feeling that that is not quite right because of $x$ being chosen proportional to the squared distance.

Any help is appreciated, thanks!

Answer 1

I only know the basics of how K-means works but your intuition seems correct. Taken from the wikipedia page:

The intuition behind this approach is that spreading out the k initial cluster centers is a good thing.

So the algorithm opts for large distances among the clusters during initialization. Step 3 describes a weighted probability distribution $ \propto D(x^2)$, so I would assume this:

• Take the distances you have computed in step 2.
• Take their square.
• Compute their sum.
• Divide every squared distance to the sum to acquire a probability distribution according to the square of distances.

Cheers.

Answer 2

In step three, it should read $D(x)^2$. A short example will reveal the gist, which is put short: favor points that have a big distance from existing cluster centers, giving a good spread over the data.

Say there are three points with which D's are 1, 2, 3. The squares are 1, 4, 9. The total of the squares is 15. Now sample according to the proportions 1/15, 4/15 and 9/15 to choose a new center. As you will see, the point with distance three is 9 times more likely to be selected.