When does K-means fail

Imagine two concentric circles on a 2-D plot. The K-means algorithm will simply create two halves of each circles and put them in each of the clusters. See the image below:


The left portion of both the circles belong to cluster 1 and the right portion of both the clusters belong to cluster 2. However, you’d like the clustering algorithm to instead cluster two circles into separate clusters.

Sklearn has a good documentation to compare different clustering approaches.