Possible Duplicate:
Clustering with a distance matrix

I have a set of data which I wish to cluster.

I have computed a distance measure between each pair of data, but I am limited in that I am unable to compute a measure between each data point and an 'arbitrary' point in space. In addition, the distance measures do not necessarily satisfy the triangle inequality.

I would like to set as a clustering parameter something like a 'minimum distance for two points to be in the same cluster'. I can then find all the edges that satisfy this similarity measure, and treat each remaining subgraph as one cluster.

However, this means that if point A is similar to point B, and B is similar to C, and C is similar to D, point A will end up in the same cluster as point D, even if A and D are very different.

Does anyone have any suggestions as to how I could use this clustering method, but prevent this 'daisy-chaining' of pairwise-similar vectors?


marked as duplicate by whuber May 29 '12 at 14:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Which distance-based clustering methods have you tried?

It sounds like you are exactly looking for DBSCAN: https://en.wikipedia.org/wiki/DBSCAN

  • $\begingroup$ Yes, this does look good, thanks. I am still concerned that maybe 'core' points could end up being a long distance apart from each other, but I will have a go. $\endgroup$ – Bill Cheatham May 24 '12 at 9:07
  • $\begingroup$ (In addition, the distance-based clustering methods I had tried was the subgraph method I mention. I realise this is now called single-linkage clustering en.wikipedia.org/wiki/Single-linkage_clustering) $\endgroup$ – Bill Cheatham May 24 '12 at 9:11
  • $\begingroup$ Single-linkage is much more prone to the single link effect. In DBSCAN you could have a long chain of core points; and there probably is no sensible "mean" of a cluster. But if you set minPts high enough, the cluster should be, well, density connected by a lot of points. $\endgroup$ – Anony-Mousse May 24 '12 at 13:30

Not really an answer, but it might help. First try to get a true metric, satisfying the triangle inequality... it may be not too hard. Then try clustering your data using a metric tree. I haven't researched carefully the subject, but it seems that the most recent member of that family are cover trees...

  • $\begingroup$ This seems like it would help, but I'm not sure my data is suitable. In reality the 'distances' I have are 'confidences of matching', between 0 and 1. So it may be difficult to scale them appropriately. $\endgroup$ – Bill Cheatham May 24 '12 at 9:09

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