# How to deal with the effect of the order of observations in a non hierarchical cluster analysis?

When a non-hierarchical cluster analysis is carried out, the order of observations in the data file determine the clustering results, especially if the data set is small (i.e, 5000 observations). To deal with this problem I usually performed a random reorder of data observations. My problem is that if I replicate the analysis n times, the results obtained are different and sometimes these differences are great.

How can I deal with this problem? Maybe I could run the analysis several times and after consider that one observation belong to the group in which more times was assigned. Has someone a better approach to this problem?

• Your random reordering reminded me of this AI koan: In the days when Sussman was a novice Minsky once came to him as he sat hacking at the PDP-6. "What are you doing?", asked Minsky. "I am training a randomly wired neural net to play Tic-Tac-Toe." "Why is the net wired randomly?", asked Minsky. "I do not want it to have any preconceptions of how to play." Minsky shut his eyes. "Why do you close your eyes?", Sussman asked his teacher. "So the room will be empty." At that moment, Sussman was enlightened. Commented Jul 20, 2010 at 12:40

A "right" answer cannot depend on an arbitrary ordering of some method you are using.

You need to consider all possible orderings (or some representative sample) and estimate your parameters for every case. This will give you distributions for the parameters you are trying to estimate. Estimate the "true" parameter values from these distributions (this will also give you an estimate for your estimator error).

Alternatively use a method that doesn't introduce an ordering.

What you're discovering is a degree of instability in either the algorithm or the data itself. The approach termed 'consensus' or 'ensemble' clustering is a way of dealing with the problem. The problem there is: given a collection of clusterings, find a "consensus" clustering that is in some sense the "average" of the clusterings.

There's a fair bit of work on this topic, and a good place to start is the clustering ensembles paper by Strehl and Ghosh.

Which flat-clustering algorithm are you using? It might also be the case that the different results are because maybe it's not your data but your algorithm itself is non-deterministic (e.g., using K-means with random initialization, or using a model-based clustering with EM or MCMC for inference with random initialization)?

• I used the kmeans R function with a random initialization so the results were different for each clustering attemp. Now I am reading the paper suggested above by Suresh. Commented Sep 18, 2010 at 10:19