Bug in ClusteringComponents yielding different results on practically same input?

I am using the image below.

I want to run a simple ClusteringComponents, using the KMeans method and EuclideanDistance DistanceFunction. Just to make sure there is no problem with the implementation of ClusteringComponents with images, I use the data of the Image and operate on the second level of the list obtained via ImageData. So my call to ClusteringComponents looks like this:

ClusteringComponents[
ImageData[ImageResize[image, 500, Resampling -> "NearestLeft"]], 4,
2, Method -> "KMeans",
DistanceFunction -> EuclideanDistance] // Colorize


with image being the image below and the ImageResize is just here for reference, because the resolution in x-direction should already be 500. The result is not what I expect and what it should be when using EuclideanDistance:

And here comes the surprising right result: As the KMeans-algorithm should be invariant under duplication operation, i.e. just instering every entry multiple times, the following code (which is due to ImageResize with Resampling->"NearestLeft" just inserting every entry 4 times) should give the same result as the code before just with twice the resolution:

ClusteringComponents[
ImageData[ImageResize[image, 1000, Resampling -> "NearestLeft"]], 4,
2, Method -> "KMeans",
DistanceFunction -> EuclideanDistance] // Colorize


Output:

At least on my Mac (Mac OS X Mavericks, Mathematica 10.0.0) the results are surprisingly not the same, the second piece of code yielding the "right" result, while the first one is not. Am I missing something or is this a bug?

• The k-means algorithm can get trapped in a local minimum during optimisation, so try using the "RandomSeed" option of ClusteringComponents to vary its initial guess. I found that "RandomSeed" -> 12345 makes the results the same in both cases. – Stephen Luttrell Sep 21 '14 at 17:23

The k-means algorithm can get trapped in a local minimum during optimisation - see here - so try using the "RandomSeed" option of ClusteringComponents to vary its initial guess.
image = <your image>;

• Thanks, I am actually feeling a little bit dumb, that I did not think of that myself. Can anyone think of a similar method that does not run into local optimums (I know that RandomSeed helps, but it has still a random component in it)? – Wizard Sep 22 '14 at 9:03