# Which hierarchical clustering algorithm?

I have a large distance matrix $3400\times 3400$.

I need to cluster them hierarchically and then cut the tree into clusters (like a partitional approach).

Which algorithm is most sensitive to finding natural clusters in the data based on the distance matrix?

How can I evaluate the result? I am planning on using average silhouette coefficient of the tree at various levels to identify the 'natural' clusters from the tree.

Thanks

• What does it mean "most sensitive to finding natural clusters"?? – Tal Galili May 9 '11 at 18:59
• i mean that the clustering method should be able to find near optimal clusters. Those with high intra similarity and low external similarity (wrt other clusters) – chet May 10 '11 at 16:12
• Hi Chet, I would imagine that if there was only one such algorithm, everyone would simply use that. I suspect that the reason that many different algorithms are still in practice would be because different algorithms will performance differently on different settings of the problem/datasets. Hence, I am not sure anyone can help you choose the "best" algorithm for your problem with the information you've provided so far. Cheers, Tal – Tal Galili May 11 '11 at 8:16

Sounds like you need HAC (hierarchical agglomerative clustering). There are many variants, but the basic idea is that you start with singleton clusters and progressively merge, based on different ways of determining which clusters are the "closest".

For more on HAC, see the wikipedia entry.

Some interesting things you could try out:

1. Take a look at SigClust - it's an R function that allows you to establish the significance of clustering using bootstrapping/monte carlo simulation. SigClust will provide a p-value for the clustering operation between two sets of points. Theoretically, you can run it at every node of your hierarchical clustering tree, but it tends to be time consuming so maybe at nodes of more than 10 points. In either case, if you SigClust consistently provide high p-values for a clustering of points, then those might highlight the natural clusters you are looking for.

2. Try to see whether you can use OREO or optimal re-ordering instead of hierarchical clustering. There isn't an R implementation available as far as I know, but the algorithm does generate very impressive results (at least in the papers that I have read). If you have a background in mathematical programming I'm sure you could get something like this working using CPLEX.

You might want to try "model-based clustering". This algorithm uses "BIC" to determine the number of clusters.

Sincerely