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
 A: Some interesting things you could try out:


*

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

*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.
A: 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. 
A: You might want to try "model-based clustering". This algorithm uses "BIC" to determine the number of clusters. 
Sincerely
