In my clustering problem I'm working with custom similarity measure and looking for any implementation of algorithms with asymmetrical distance or similarity matrix. I'm only interested in those that can offer custom similarity/distance matrix as input or a custom similarity measure function. Language of implementation doesn't really matter as long as it's working. (R would be the best, Python, C++, C, Java, Ruby)

What methods I find particularly interested in.

  1. Taylor-Butina clustering/grouping for asymmetrical similarity. Here is the usage of it. Some R implementations, though not sure if it's usable with asymmetrical matrix.
  2. Tarjan's hierarchical clustering with strong components. Not to be confused strongly connected components algorithm.
  3. Spectral clustering using custom affinity matrix. I'm especially interested in implementation of this one in R.

I found some of the algorithms implemented in Mesa Suite Version 2.0 Grouping Module. However I haven't found any trials or downloads of this program.

Edit : The distance function satisfies triangle inequality.

I think this post would be interesting for all cheminformatics people using R.


1 Answer 1


DBSCAN and OPTICS should work with asymmetric distances as well.

Don't use the DBSCAN implementation in R. It's incredibly slow.

The version in scipy probably doesn't allow you to use arbitrary distances, and it computes the full distance matrix, so it scales badly.

The DBSCAN and OPTICS implementations in ELKI are pretty good, and scale really well when you can use index structures.

  • $\begingroup$ Thank you for reply. Is it possible to get centroids from this type of clustering? – user974514 9 mins ago $\endgroup$
    – user974514
    Commented May 12, 2013 at 14:12
  • $\begingroup$ Well, you can always compute a centroid... The question is, whether the centroid is generally meaningful or not. DBSCAN and OPTICS are designed to find non-spherical, non-convex clusters. However, also for k-means, the centroid could be in a gap of the cluster. If you run k-means on sparse data, the centroids will be anomalous as in much less sparse. So while DBSCAN does not use centroids, the centroids of DBSCAN clusters probably are not much less meaningful than those of k-means. (In fact, they may be better, as DBSCAN removes noise!!) $\endgroup$ Commented May 12, 2013 at 14:12

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.