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.