0
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ are you plugging your measure where the distance is required? $\endgroup$
    – Aksakal
    Jun 11, 2020 at 16:05
  • $\begingroup$ yes, this is what I intend to do $\endgroup$
    – user288129
    Jun 12, 2020 at 14:14
  • $\begingroup$ 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. $\endgroup$
    – ttnphns
    Jun 14, 2020 at 18:19

1 Answer 1

Reset to default
1
$\begingroup$

Algorithms will produce clusters, but they may not make a sense.

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.

In case, b) I suspect that the problem become computationally much more difficult. It reminds me of "shortest path" type of problems in computer science.

Improve this answer
$\endgroup$
3
  • $\begingroup$ My measure is not a metric. But it has a well-defined meaning. The 'subjects' in my dataset are glass fragments (n = 20) from an unknown number of windows (n <= 20). I use the clustering results to infer the grouping of the glass fragments into windows. My measure is based on the likelihood ratio (it is: minus log LR) for a comparison between two fragments. H1 reads: The two fragments are from the same window. H2 reads: The two fragments are from arbitrary different windows. So a 'cluster' means that all log LRs are larger than a certain treshold value. The 'farthest' pair has lowest log LR? $\endgroup$
    – user288129
    Jun 11, 2020 at 17:13
  • $\begingroup$ imagine that fragment A is white, and B is black, then it's not likely that they;re from the same window. Then you are shown a fragment C that is part white and part black. Now you conclude that the window must have been a mosaic, so your perception of similarity of A and B changes to favorable. That's what non metric measures do. The effect is that the measure of distance between A and B depends on presence of C. Hence, the clustering that is based on distance is not going to work in a logical way with your dissimilarity. $\endgroup$
    – Aksakal
    Jun 11, 2020 at 18:35
  • $\begingroup$ Despite this reasoning is faultless, the complete linkage HAC does not imply metricity and it doesn't bother about shortest paths through third party points. When the distance isn't metric (per violation of the triangular inequality) it simply means the clusters cannot be imagined in a metric space. $\endgroup$
    – ttnphns
    Jun 14, 2020 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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