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

Question

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?

Manuel Ramon

Answer 1

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.

Answer 2

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.

Answer 3

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)?