# Is 'symmetry' the only requirement for a distance matrix to perform hierarchical clustering with complete linkage?

I have a dissimilarity measure for pairwise comparison of my subjects and want to perform hierarchical cluster analysis with complete linkage.

The dissimilarity measure is not a distance metric. It does satisfy the following properties:

• d(X,Y) = large negative number, when X = Y
• d(X,Y) becomes larger when X is less 'similar' to Y
• d(X,Y) = d(Y,X), the dissimilarity matrix is symmetric.

So compared to a distance metric, only the 'symmetry' requirement is satisfied.

Are the above three properties nevertheless sufficient for hierarhcical clustering with complete linkage?

I have tried to run hclust in R with as distance matrix my matrix with pariwise dissimilarity measures and it seemed to work fine.

If one can provide me with a reference that contains the answer that would be great!

• are you plugging your measure where the distance is required? – Aksakal Jun 11 '20 at 16:05
• yes, this is what I intend to do – PEVER Jun 12 '20 at 14:14
• You always can add a constant to make your "large negative value" zero. But even this is not needed for complete linkage because this linkage simply selects the greatest distance at each step; it does not make any arithmetic computations. Complete linkage works with any symmetric matrix. – ttnphns Jun 14 '20 at 18:19

I don't see why the algorithms won't work (in a sense that they won't throw exceptions). Since the objective is to look for the clusters with smallest $$\max_{x\in X, y\in Y} d(x,y)$$ and merge them at each step, I bet that the only property of the distance that they rely on is that $$d(X,Y)$$ is larger for further objects. Your dissimilarity metric has that.
However, implicitly the complete linkage assumes the metric space, i.e. $$d(x,y)\le d(x,z)+d(z,y)$$. Why? Because otherwise in order to determine the farthest points in the clusters it wouldn't be enough to look for points $$x,y$$ with largest $$d(x,y)$$. It would be possible to find a closer path between these points through a point $$z$$ in one of the clusters. Then either a) the definition of what is the linkage metric between clusters is not the same with your dissimilarity metric vis-a-vis a proper distance or b) you have to modify the algorithms so they calculate the linkage metric that accounts for possible shorter paths.