Statistics 4240 - Data Mining

I'm working on the K-means clustering algorithm and my implementation seems to be hitting local minima for the within cluster sum of squares. You mentioned in your slides a couple of ways of dealing with this, but didn't really go into any specific details. Do you have any links to good resources for deterministic annealing and/or genetic algorithms as they apply to this problem? There is no mention of them in the book, I've noticed. Also, in its discussion of the k-means algorithm, the book says that the Hartigan and Wong algorithm "ensures that there is no single switch of an observation from one group to another group that will decrease the objective." (p. 462) But they don't say how this is done. R's implementation clearly does this, but the source is difficult to get at (seems to be FORTRAN, too). Can you offer any suggestions?

The details of the Hartigan-Wong algorithm are here. I don't have much experience with fancier kmeans algorithms but if you search for "k means annealing" on google scholar you get tons of stuff. Running k-means from different starting points is usually a reasonable approach.