scipy.cluster.hierarchy.is_monotonic

scipy.cluster.hierarchy.is_monotonic(Z)

Return True if the linkage passed is monotonic.

The linkage is monotonic if for every cluster \(s\) and \(t\) joined, the distance between them is no less than the distance between any previously joined clusters.

Parameters

Zndarray

The linkage matrix to check for monotonicity.

Returns

bbool

A boolean indicating whether the linkage is monotonic.

See also

linkage

for a description of what a linkage matrix is.

Examples

>>> from scipy.cluster.hierarchy import median, ward, is_monotonic
>>> from scipy.spatial.distance import pdist

By definition, some hierarchical clustering algorithms - such as scipy.cluster.hierarchy.ward - produce monotonic assignments of samples to clusters; however, this is not always true for other hierarchical methods - e.g. scipy.cluster.hierarchy.median.

Given a linkage matrix Z (as the result of a hierarchical clustering method) we can test programmatically whether it has the monotonicity property or not, using scipy.cluster.hierarchy.is_monotonic:

>>> X = [[0, 0], [0, 1], [1, 0],
...      [0, 4], [0, 3], [1, 4],
...      [4, 0], [3, 0], [4, 1],
...      [4, 4], [3, 4], [4, 3]]

>>> Z = ward(pdist(X))
>>> Z
array([[ 0.        ,  1.        ,  1.        ,  2.        ],
       [ 3.        ,  4.        ,  1.        ,  2.        ],
       [ 6.        ,  7.        ,  1.        ,  2.        ],
       [ 9.        , 10.        ,  1.        ,  2.        ],
       [ 2.        , 12.        ,  1.29099445,  3.        ],
       [ 5.        , 13.        ,  1.29099445,  3.        ],
       [ 8.        , 14.        ,  1.29099445,  3.        ],
       [11.        , 15.        ,  1.29099445,  3.        ],
       [16.        , 17.        ,  5.77350269,  6.        ],
       [18.        , 19.        ,  5.77350269,  6.        ],
       [20.        , 21.        ,  8.16496581, 12.        ]])
>>> is_monotonic(Z)
True

>>> Z = median(pdist(X))
>>> Z
array([[ 0.        ,  1.        ,  1.        ,  2.        ],
       [ 3.        ,  4.        ,  1.        ,  2.        ],
       [ 9.        , 10.        ,  1.        ,  2.        ],
       [ 6.        ,  7.        ,  1.        ,  2.        ],
       [ 2.        , 12.        ,  1.11803399,  3.        ],
       [ 5.        , 13.        ,  1.11803399,  3.        ],
       [ 8.        , 15.        ,  1.11803399,  3.        ],
       [11.        , 14.        ,  1.11803399,  3.        ],
       [18.        , 19.        ,  3.        ,  6.        ],
       [16.        , 17.        ,  3.5       ,  6.        ],
       [20.        , 21.        ,  3.25      , 12.        ]])
>>> is_monotonic(Z)
False

Note that this method is equivalent to just verifying that the distances in the third column of the linkage matrix appear in a monotonically increasing order.