Hierarchical clustering methods using a similarity metric for which d(x, x) != 0, and possibly assymmetric

Question

I want to cluster files based on an information distance, which is obtained by comparing the compressed length of two files separately and the concatenation of the two files, using a real-world compressor like zlib. (In words: given files $x$ and $y$, how easy can you express $x$ in terms of $y$?)

This "metric" does not satisfy $d(x,x) \ne0$, and it does not always satisfy $d(x,y)=d(y,x)$, depending on the compressor used. (But I'm willing to throw away one half of the distance matrix and pretend it's triangular.)

I'm told I cannot use hclust in R, because it always expects $d(x,x)=0$.

See my other question regarding my troubles with R (I'm only a beginner.)

What hierarchical clustering method would be suitable, preferably one that is implemented in R/Python? I only want to cluster up to 30 items right now, so scale is not an issue.

Answer 1

Hierarchical agglomerative clustering should never attempt to use $d(x,x)$ anyway. It's not a possible "merge" of two clusters.

Symmetry is a different thing. Have you considered "fixing" your similarity?

$$ d^\prime(x,y):=\begin{cases} \min\{d(x,y), d(y,x)\} & \text{if }x\neq y \\ 0 & \text{if }x = y \end{cases} $$

As long as your distance matrix fits into main memory this should be easy to do, and then you should be able to run many clustering algorithms (except k-means and Mclust).