ElanHR
commented
9 years ago It's hard to give any sort of error bound on non-convex problems (without additional constraints) and thus hard to say/prove that any algorithm will work well with any guarantees.
That said there are a number of extensions to improve performance in these cases but even these aren't guaranteed to give the best solution for non-convex problems. One improvement is simply starting from a number of different initializations and use the best. Someone also suggested another method in class which adds an "exploration" step in our algorithm which means after some number of iterations we "jump" and try to escape our local maximum. In the K-means case this would changing our centroids by a random step size. Larger step sizes have the advantage of being less likely to get stuck in local minima but the disadvantages of being less stable overall.
Training multilayer neural nets is an example for which (in many cases) the objective function is non-convex however it has been shown empirically that we can fairly good results simply training each layer in a greedy fashion (one layer at a time rather than the whole stack at once). Even if this result is not the global optimum, a local optimum is often good enough.
So if K-means is apparently poor at clustering non-convex sets, are there any other algorithms that work well for non-convex problems or any modifications that can be made to K-means to improve its reliability?