Many machine learning techniques suffer from the curse of local minima, one of them is K-means. I am using a matlab script for a computer vision task. One of the first steps I do is kmeans clustering on an image in the Lab color representation, I only consider the ab components. So I consider my pixels to be a set of ab data points, without using any gemetrical information (i.e. pixel location) of the pixels. However, I guess these are less important details; in essence I am just doing k-means.
My statistically non-deterministic algorithm (read Matlab script) can give a (c) correct result or a (w) wrong result. Fortunately, (c) seems to happen more often, but (w) also happens :(. I can only verify this by hand, the computer is more or less clueless that it computed a wrong answer.
However, the final error of k-means seems to be slightly, but consistently higher in case of (w) compared to case (c). This is the result of running the algorithm multiple times on the same image with the same parameters (k=7). That is:
Runs resulting in (c):
Replicate 1, 36 iterations, total sum of distances = 1.53591e+06.
Replicate 1, 130 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 56 iterations, total sum of distances = 1.53591e+06.
Replicate 1, 129 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 45 iterations, total sum of distances = 1.53591e+06.
Replicate 1, 122 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 42 iterations, total sum of distances = 1.53591e+06.
Replicate 1, 80 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 106 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 125 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 120 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 128 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 108 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 129 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 112 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 120 iterations, total sum of distances = 1.54903e+06.
Replicate 1, 121 iterations, total sum of distances = 1.54903e+06.
Runs resulting in (w):
Replicate 1, 80 iterations, total sum of distances = 1.61651e+06.
Replicate 1, 33 iterations, total sum of distances = 1.61651e+06.
Replicate 1, 62 iterations, total sum of distances = 1.62508e+06.
So my instinct tells me that the prior probability of a (c) is a lot higher than that of a (w), which is good. Since now I could just repeat k-means n times, resulting in a nxk-means algorithm, and select the result with lowest final error. This will likely result in a (c).
However, this seems a rather crude solution. Are there smarter/faster/statistically sounder ways to tackle local optima in k-means?
total sum of distances, given that K-means minimizes sum of squared deviations. $\endgroup$k-means initial,k-means local global. $\endgroup$