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:
- Choose one center uniformly at random from among the data points.
- For each data point $x$, compute $D(x)$, the distance between $x$ and the nearest center that has already been chosen.
- 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)$.
- Repeat Steps 2 and 3 until $k$ centers have been chosen.
- 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!