8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Benjamin Bannier Jul 20 '10 at 12:40
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Manuel Ramón Sep 18 '10 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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