K-means: What are some good ways to choose an efficient set of initial centroids? When a random initialization of centroids is used, different runs of K-means produce different total SSEs. And it is crucial in the performance of the algorithm. 
What are some effective approaches toward solving this problem? Recent approaches are appreciated.
An approach that yields more consistent results is K-means++.  This approach acknowledges that there is probably a better choice of initial centroid locations than simple random assignment. Specifically, K-means tends to perform better when centroids are seeded in such a way that doesn't clump them together in space. 

In short, the method is as follows:


Choose one of your data points at random as an initial centroid.
Calculate $D(x)$, the distance between your initial centroid and all other data points, $x$.
Choose your next centroid from the remaining datapoints with probability proportional to $D(x)^2$
Repeat until all centroids have been assigned.


Note: $D(x)$ should be updated as more centroids are added.  It should be set to be the distance between a data point and the nearest centroid.

You may also be interested to read this paper that proposes the method and describes its overall expected performance.