3
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$
    – zachdj
    Nov 25, 2019 at 16:07
  • 1
    $\begingroup$ I added a picture to my question, I hope it clarifies $\endgroup$
    – Engineer
    Nov 25, 2019 at 16:32
  • $\begingroup$ Thanks! That picture + your description did a great job clarifying the question. $\endgroup$
    – zachdj
    Nov 25, 2019 at 16:45

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Engineer
    Nov 25, 2019 at 16:59
  • $\begingroup$ 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. $\endgroup$
    – zachdj
    Nov 25, 2019 at 17:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – zachdj
    Nov 25, 2019 at 17:15
  • 1
    $\begingroup$ You answered my next question without me needing to ask it, that is pretty good! Thanks, I'll be reading about those metrics now $\endgroup$
    – Engineer
    Nov 25, 2019 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.