# Simulated annealing and k-means

One of my problems https://stackoverflow.com/questions/7783933/clustering-data-outputs-irregular-plot-graph suffers from the curse of dimensionality, which also makes it infeasible for exhaustive search or analytical methods, metaheuristics for combinatorial problems like simulated annealing might help in my endeavour how would I combine simulated annealing with k-means in my example problem?

Sorry for the very short question im still trying to get my head around simulated annealing and how it could possibly help.

Other questions that could help is the comparison of simulated annealing to pca, vds or how it can be used in conjunction. (sorry abit late for me) Edits are welcome if you undertsand my lack of knowledge and what I might be trying to get at.

It sounds like you're carrying out a cluster analysis on a dataset that has a pretty large number of variables; having difficulty obtaining good results because of the large number of variables (the curse of dimensionality, as you mention); and you're considering using an optimization technique such as simulated annealing to carry out a search through your variables to discover whether you might be able to use just a subset - is that right?

If so, that activity is typically called feature selection (sometimes feature extraction), and there's plenty of literature out there that describes how you might approach it. Feature selection involves selecting a subset of the original variables, and is not quite the same as dimensionality reduction, which typically involves creating a small number of linear combinations of the original variables that summarise them (this is what a technique such as PCA or SVD does).

A suggestion I might give is to note that you're trying to search through what is a discrete space (the power set of your variables). Simulated annealing, as an optimization technique, is in my experience more easily applied to searching through continuous spaces. This is particularly true of the implementation in MATLAB Global Optimization Toolbox (since I note you added the MATLAB tag). If you're using MATLAB for this, I'd suggest that a genetic algorithm might be easier to adapt to searching through discrete spaces.

I wrote an article for MATLAB Digest a while ago that applies genetic algorithms to a related problem (classification rather than cluster analysis), which comes with example code. You might find that it's possible to adapt that code to your needs. The article carries out feature selection on a classification problem though, so it's maximizing classification accuracy - you'd need to provide a clustering metric for the algorithm to optimize, such as separation, heterogeneity, or a gap statistic.

Hope that helps!

• Sam thank you very much! Very informative and will help along way!
– G Gr
Nov 21, 2011 at 1:33

Simulated Annealing is heuristic search optimization algorithm. You need to define a loss function. SA will optimize this and will converge to local minumum.

K-means clustering by definition also includes optimization. It minimizes instances' distance to cluster centers. This distance can be eucledean or manhattan distance. Look to http://www.iro.umontreal.ca/~lisa/pointeurs/kmeans-nips7.pdf for its convergence properties and similarities to gradient descent.

From my limited understanding only way to use to SA ve K-Means together is to define K-Means loss differently than distance minimization.

For example you may define a loss function : using different distance metrics or different feature subsets.

Loss Function = sum of metric distance of features and different combinations of features

SA will try to minimize this Loss Function.