K-Means Clustering variable results depending on sort order of data I'm using PASWStatistics18 and K-Means clustering data that I'd previously clustered using an earlier version of SPSS... My problem is that I'm getting different cluster results depending on how the data file is sorted.  I can't remember this being an issue in the earlier versions of SPSS, but I can't repeat the same results, using the same data file, again!  Only by using the saved cluster centres can I get close to the original result.
Have others had similar isues?  Am I doing something wrong?
 A: This is a well-known property of k-means. The initialization is usually randomized, so you might even get (and in fact, intend to get) different results for multiple runs. It is a common best practise with k-means to run it multiple times, and choose the one with the minimum average distances (or by some other internal metric).
DBSCAN is mostly order independent. Only for fringe points that could belong to two different clusters, the cluster assignment is not stable (unless you extend DBSCAN to support multi-assignments or use some other stable tie-braking rule).
In general, it actually is even a good idea to shuffle your dataset before doing any kind of analysis. Say your method fails completely, and returns the data set in its original order. If the data was sorted before, the output will look meaningful. So always shuffle your data. 
A: Actually SPSS has acknowledged, going back at least to version 13 (ca. 2003) that cluster solutions will be affected by sort order.  This applies not only to K-means but to its other clustering algorithms as well.  You'll find this information in the Help files and possibly in the Tutorial.  When using cluster analysis in SPSS I always create a random number and sort by that first.
