Use Distance Matrix in scipy.cluster.hierarchy.linkage()?

Question

I have a distance matrix n*n M where M_ij is the distance between object_i and object_j. So as expected, it takes the following form:

   /  0     M_01    M_02    ...    M_0n\    | M_10    0      M_12    ...    M_1n |    | M_20   M_21     0      ...    M2_n |    |                ...                 |    \ M_n0   M_n2    M_n2    ...      0 /  

Now I wish to cluster these n objects with hierarchical clustering. Python has an implementation of this called scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean').

Its documentation says:

y must be a {n \choose 2} sized vector where n is the number of original observations paired in the distance matrix.

y : ndarray

A condensed or redundant distance matrix. A condensed distance matrix is a flat array containing the upper triangular of the distance matrix. This is the form that pdist returns. Alternatively, a collection of m observation vectors in n dimensions may be passed as an m by n array.

I am confused by this description of y. Can I directly feed my M in as the input y?

---

Update

@hongbo-zhu-cn has raised this issue up in GitHub. This is exactly what I am concerning about. However, as a newbie to GitHub, I don't know how it works and therefore have no idea how this issue is dealt with.

Answer 1

It seems that indeed we cannot directly pass the redundant square matrix in, although the documentation claims we can do so.

To benefit anyone who faces the same problem in the future, I write my solution as an additional answer here. So the copy-and-paste guys can just proceed with the clustering.

Use the following snippet to condense the matrix and happily proceed.

import scipy.spatial.distance as ssd # convert the redundant n*n square matrix form into a condensed nC2 array     distArray = ssd.squareform(distMatrix) # distArray[{n choose 2}-{n-i choose 2} + (j-i-1)] is the distance between points i and j 

Please correct me if I am wrong.

Answer 2

For now you should pass in the 'condensed distance matrix', i.e. just the upper triangle of the distance matrix in vector form:

y = M[np.triu_indices(n,1)] 

From the discussion of @hongbo-zhu-cn's pull request it looks as though the solution will be to add an extra keyword argument to the linkage function that will allow the user to explicitly specify that they are passing in an n x n distance matrix rather than an m x n observation matrix.