Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
I don't know about PASWStatistics18 but it seems like either the initialisation of the first k centers is different for each run, or a mean is immediately updated after each datapoint (or some datapoints) assignation (like for the online k-means) . – shn Mar 5 '12 at 9:13

2 Answers

up vote 2 down vote

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.

share|improve this answer
can you give link to current help file? – Atilla Ozgur Mar 5 '12 at 6:45
Hierarchical clustering doesn't depend on case order unless there are ties in the diatance matrix. – ttnphns Mar 5 '12 at 7:21
up vote 1 down vote

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 two 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.

share|improve this answer
You will not get a different results using the classical k-means where the means are computed only after each pass over the hole dataset, unless you initialise the first k centers differently for each run, or you update the mean immediately after each datapoint assignation (like for the online k-means) – shn Mar 5 '12 at 9:11
Well, it is a best practise to try different random initializations, instead of using the first k objects (which, when the data set is sorted, are biased). And it very often even results in quite different output, so it is sensible to try different initializations (whether or not MacQueen proposed that) ... – Anony-Mousse Mar 5 '12 at 12:46
You're right, and in this case, if you have all the dataset available beforehand, it will be much better to use a seeding procedure that allow to initialize centers with datapoints that are far from each other, rather than pure random initialization. – shn Mar 5 '12 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.