<p>How about the pathological case of the two-moons dataset? unsupervised k-means will fail badly. A high quality method I am aware of employs a more probabilistic approach using mutual information and combinatorial optimization. Basically you cast the clustering problem as the problem of finding the optimal [cluster] subset of the full point-set for the case of two clusters.</p>

<p>You can find the <a href="http://arxiv.org/pdf/1111.6453v1.pdf" rel="nofollow">relevant paper here</a> (page 42) and the corresponding <a href="http://www.di.ens.fr/~fbach/submodular/" rel="nofollow">Matlab code here</a> to play with (checkout the two-moons case). If you are interested in a C++ high-performance implementation of that with a speed up of >30x then you can find it <a href="http://hpsfo.bitbucket.org" rel="nofollow">here HPSFO</a>.</p>
Regarding quality of different k-means algorithms
<p>I see that for k-means, we have Lloyd's algorithm, Elkan's algorithm, and we also have hierarchical version of k-means. </p>

<p>For all these algorithms, I see that Elkan's algorithm could provide a boost in term of speed. But what I want to know, is the quality from all these k-means algorithms. Each time, we run these algorithms, the result would be different, due to their heuristic and probabilistic nature. Now, my question is, when it comes to clustering algorithm like k-means, if we want to have a better quality result (as in lesser distortion, etc.) between all these k-means algorithms, which algorithm would be able to give you the better quality? Is it possible to measure such thing?</p>