7
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What does it mean "most sensitive to finding natural clusters"?? $\endgroup$
    – Tal Galili
    Commented May 9, 2011 at 18:59
  • $\begingroup$ 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) $\endgroup$
    – chet
    Commented May 10, 2011 at 16:12
  • 3
    $\begingroup$ 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 $\endgroup$
    – Tal Galili
    Commented May 11, 2011 at 8:16

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Sincerely

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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