I have data which looks like this. As you can see the data is symmetric and its not exactly a distance matrix. They are log odds ratios. And the diagonal values are higher than non-diagonal elements.

I want to know if normal clustering techniques could be use for such a scenario. When I looked online, all the clustering methods use distance metric and diagonal values are zero. Is there a way for me to adopt this table for clustering analysis.

I just want to know which amino acids are similar to each other and categorize them in to clusters based on their similarity. Can anyone suggest a good clustering technique for this?


  • $\begingroup$ Diagonal elements are 0 because objects have 0 distance from themselves or perhaps more formally cluster centers have 0 distance from themselves. $\endgroup$ – Michael R. Chernick May 22 '12 at 18:17
  • $\begingroup$ How do odds ratio relate to your problem of comparing amino acids? $\endgroup$ – Michael R. Chernick May 22 '12 at 18:18
  • $\begingroup$ If the entries of the matrix are odds ratio, then why aren't the diagonal entries $\infty$? The odds ratio (and therefore the log odds ratio) will be $\infty$. $\endgroup$ – Macro May 22 '12 at 18:40
  • $\begingroup$ because x/x=1 and log(1)=0. But that said, these can't be log odds ratios because they should be 0 on the diagonal and they're not. Maybe something to do with that log(2)/2 bit at the top? $\endgroup$ – conjugateprior May 22 '12 at 19:05
  • 1
    $\begingroup$ I suspect they're not log-odds ratios but log-odds. See en.wikipedia.org/wiki/Substitution_matrix#Log-odds_matrices $\endgroup$ – onestop May 22 '12 at 19:11

All you need to do is to go beyond k-means and hierarchical clustering to somewhat more modern methods (if you consider 1990s to be "modern", that is).

Many clustering methods such as DBSCAN do not require your distance to be metric. The whole notion of a metric is of low relevance for data mining, as databases may contain duplicate records, so at best you have a pseudo-metric anyway.

Many just need some kind of similarity measure. It could even measure similarity instead of distance, that is just a different sign for the threshold to them.

DBSCAN needs a threshold. OPTICS when using the $\xi$ method for extracting clusters also needs them to bear some semantics, i.e. a drop in distance of 10% being interesting enough to start a new nested hierarchical cluster.

If you have a metric (or pseudo-metric), that can bear performance benefits. If you already have a distance matrix, these are moot, because that already means you computed the $O(n^2)$ similarities.

K-means, while very popular, has much stronger restrictions. In particular, the mean must minimize the distances, i.e. updating a cluster center with the mean of the objects must improve the criterion function. This will likely not hold for you, if you can compute distances from mean vectors at all.

You might want to have a look at "Generalized DBSCAN" to understand how loose the dependency on the distance function is. It's just a method for selecting "neighbor" objects. But you can in fact plug in any other definition of "neighbor".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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