what is the meaning of the return values of the scipy.cluster.hierarchy.linkage?

Question

Let assume that we have X matrix as follows:

[[9 0]
[1 4]
[2 3]
[8 5]]

Then,

from scipy.cluster.hierarchy import linkage
Z = linkage(X, method="ward")
print(Z)

The returning matrix is follows:

[[  1.           2.           1.41421356   2.        ]
 [  0.           3.           5.09901951   2.        ]
 [  4.           5.          10.           4.        ]]

What is the meaning of the returning values?

Answer 1

Although this has been answered before, it was a "read the docs" answer. I think it is useful to explain the docs a bit.

From the docs, we read that:

An (n−1) by 4 matrix Z is returned. At the i-th iteration, clusters with indices Z[i, 0] and Z[i, 1] are combined to form cluster n + i. A cluster with an index less than n corresponds to one of the n original observations. The distance between clusters Z[i, 0] and Z[i, 1] is given by Z[i, 2]. The fourth value Z[i, 3] represents the number of original observations in the newly formed cluster.

I think the confusing part is the the first n clusters are singletons ("original observations"). So the first value in Z actually the n+1'th cluster. It is the first cluster to combine two singletons.

So in your example, Z[0] is the 4+1'th cluster. We have

 Z[0] = [  1.           2.           1.41421356   2.        ]

The first two values tell us which clusters were used to create cluster Z[0]. They are cluster_1, the singleton [1,4], and cluster_2, the singleton [2, 3].

The third value gives us the distance between the clusters. We can verify that sqrt((2-1)^2 + (3-4)^2)) = 1.41...

The fourth value tells us how many singletons are in cluster Z[0].

So looking at your last cluster, Z[2], we see that is combines the firs two clusters in Z. Each of them contains two unique singletons, so the Z[2,3] = 4.