# K-Means initialization

K-Means initializes the centroids randomly, but there are other methods to initialize. In this paper, http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf, they propose randomly choosing a data point initially then choose the other centroids based on the distance from the initial centroid.

My question is: how does this give you the right result? Say my data clusters naturally into three clusters, a noisy cluster around the (x, y) points (1, 1), (0, 0), and (-1, -1). Say I use the method from the paper and initially choose a data point (1.32, 0.98) and mark it as the center of cluster #1. According to the paper, I choose the next centroid based on distance, so the next point will be around (-1, -1). Say the data point chosen for cluster #2 is (-1.12, -0.89). These first two steps make sense, but now I continue on to cluster #3 and again I chose based on distance so I'll end up putting another cluster center very close to cluster #2's center. What am I missing here? Shouldn't the centers be chosen based on the sum of distances from the already initialized cluster centers?

EDIT: Initially, I randomly choose a data point to mark as center of cluster #1. I choose the red point. Now I calculate the distances between red point and all other data points and choose the furthest point away as center of cluster #2. This is the green point. My question is: according to the paper, I repeat this and calculate distances from the red point to all remaining points and take the furthest away, but this puts me back near the green point, but I was trying to get to the center cluster.

• I'm a little confused. Are you asking why the third centroid is initialized near (0, 0) instead of another point far away from the first two (like (-1, 1) or something)? Nov 25, 2019 at 16:07
• I added a picture to my question, I hope it clarifies Nov 25, 2019 at 16:32
• Thanks! That picture + your description did a great job clarifying the question. Nov 25, 2019 at 16:45

The nth centroid is chosen from a distribution proportional to $$D(x)^2$$, but pay careful attention to how $$D(x)$$ is defined. From the paper (top of page 3):

In particular, let $$D(x)$$ denote the shortest distance from a data point to the closest center we have already chosen.

Notice that $$D(x)$$ is the distance from $$x$$ to the nearest centroid. Compare that to the description of how you are choosing the points:

I repeat this and calculate distances from the red point to all remaining points and take the furthest away, but this puts me back near the green point, but I was trying to get to the center cluster.

Instead of computing the distance between all remaining points and the red point, you should instead compute the distance between each point and its nearest centroid.

For the points in the cluster around (1, 1) you'll compute the distance from the red point, and all the distances will be relatively small. Similarly, for the points around (-1, -1), you'll compute the distance from the green point, and all these distances will be pretty small.

However, for points around (0, 0), some of them will be closer to the red centroid and some will be closer to the green centroid, but they are not very close to either one. This means that $$D(x)$$ will be large for points in the (0, 0) cluster, and you are likely to choose one of these points as the next centroid.

Does that make sense?

• Thank you! That helps, I must be more careful when reading these papers. So my guess is there is a way to extend this so that K is not needed and can be found on-the-fly? Like you said, for the third cluster, $D(x)$ will be large but if I try to make a fourth cluster then all of a sudden $D(x)$ will be small for all points Nov 25, 2019 at 16:59
• Unfortunately, there's no definitive way to choose an optimal $K$ on-the-fly, but there are some useful heuristics that will probably work well in practice. One simple idea for your particular example is to set a lower threshold for $D(x)$. You can terminate initialization when the mean $D(x)$ falls below your threshold. Nov 25, 2019 at 17:12
• Of course, the problem now becomes "how do I choose a good lower threshold?" It turns out that there are much better metrics for evaluating clustering quality. For example, you could try several different k and choose the one that minimizes the Davies-Bouldin score or that maximizes the gap statistic. Nov 25, 2019 at 17:15
• You answered my next question without me needing to ask it, that is pretty good! Thanks, I'll be reading about those metrics now Nov 25, 2019 at 17:18