0

I have a problem using the hierarchy package in SciPy. Here there is an example of what my distance matrix is:

[[  0.,  40.,  33.,  28.],
 [ 40.,   0.,  35.,  28.],
 [ 33.,  35.,   0.,  28.],
 [ 28.,  28.,  28.,   0.]]

I transform the matrix into a vector and I want a hierarchy that merges the highest value in the matrix, thus it should merge in order ((0-1)-2)-3). To do that I am using the 'complete' parameter, as it is written in the documentation that this is used to take the maximum, but it actually produce: ((0-3)-2)-1)

This is the code the computes the linkage matrix:

Z = linkage(distArray, 'complete')

Any advice?

Guido Muscioni
  • 1,203
  • 3
  • 15
  • 37
  • FYI: The first argument to `linkage` must be either the 1-D array of *condensed* (aka *compressed*) distance data (see, e.g. https://stackoverflow.com/questions/13079563/how-does-condensed-distance-matrix-work-pdist/13079806#13079806), or the original array of points. To convert a symmetric distance array to the condensed form, use `squareform(distArray)`, where `squareform` is imported from `scipy.spatial.distance`. – Warren Weckesser Dec 07 '17 at 14:53

1 Answers1

3

You misunderstood the meaning of 'complete' method. It only means that the distance between two clusters of points, say {A, B} and {C, D}, is taken to be the maximum of pairwise distances AC, AD, BC, BD. This does not change the fact that hierarchical clustering combines nearby clusters, those with smallest distance from each other. There is no clustering method for "combine points if they are very far apart".

If you want large entries in your distance matrix (call it D) to mean "these are similar" then you have to transform D to invert the order relation between distances. In other words, the matrix you have measures similarity of objects and you need a measure of dissimilarity.

The simplest thing to do is to change the sign; linkage does not actually require distances to be positive. 

from scipy.cluster.hierarchy import linkage
from scipy.spatial.distance import squareform

linkage(-squareform(D), 'complete')

returns 

array([[  0.,   1., -40.,   2.],
       [  2.,   4., -33.,   3.],
       [  3.,   5., -28.,   4.]])

indicating linkage ((0-1)-2)-3.

If negative values are an issue, there are other transformations which don't produce negative numbers:

linkage(D.max() - squareform(D), 'complete')

or 

linkage(squareform(D)**(-1), 'complete')

All these will return the same hierarchy as long as 'complete' is the method'.

Of course, now that you know that 'complete' is not necessarily the thing you need, you may want to consider other methods as well, and then the effect of transformation imposed on D may change the outcome. Do what makes sense in your context, considering what D actually represents.

  • I have inverted the relation and all works fine. However, I think that the linkage matrix requires positive numbers, as a lot of time it complains about negative values. – Guido Muscioni Dec 07 '17 at 17:05
  • It didn't complain in this example for me, but if it does, subtracting D from `D.max()` would fix that. Added to the answer. –  Dec 07 '17 at 17:08