`scipy.cluster.hierarchy._hierarchy_impl:leaders`

source: /scipy/cluster/hierarchy/_hierarchy_impl.py:4096

Signature

def leaders(Z, T)

Summary

Return the root nodes in a hierarchical clustering.

Extended Summary

Returns the root nodes in a hierarchical clustering corresponding to a cut defined by a flat cluster assignment vector T. See the fcluster function for more information on the format of T.

For each flat cluster $j$ of the $k$ flat clusters represented in the n-sized flat cluster assignment vector T, this function finds the lowest cluster node $i$ in the linkage tree Z, such that:

leaf descendants belong only to flat cluster j (i.e., T[p]==j for all $p$ in $S (i)$ , where $S (i)$ is the set of leaf ids of descendant leaf nodes with cluster node $i$ )
there does not exist a leaf that is not a descendant with $i$ that also belongs to cluster $j$ (i.e., T[q]!=j for all $q$ not in $S (i)$ ). If this condition is violated, T is not a valid cluster assignment vector, and an exception will be thrown.

Parameters

Z : ndarray: The hierarchical clustering encoded as a matrix. See linkage for more information.
T : ndarray: The flat cluster assignment vector.

Returns

L : ndarray

The leader linkage node id's stored as a k-element 1-D array, where k is the number of flat clusters found in T.

L[j]=i is the linkage cluster node id that is the leader of flat cluster with id M[j]. If i < n, i corresponds to an original observation, otherwise it corresponds to a non-singleton cluster.

M : ndarray

The leader linkage node id's stored as a k-element 1-D array, where k is the number of flat clusters found in T. This allows the set of flat cluster ids to be any arbitrary set of k integers.

For example: if L[3]=2 and M[3]=8, the flat cluster with id 8's leader is linkage node 2.

Notes

Array API support (experimental): This function returns arrays with data-dependent shape. In JAX, at the moment of writing this makes it impossible to execute it inside @jax.jit.

Array API Standard Support

leaders has experimental support for Python Array API Standard compatible backends in addition to NumPy. Please consider testing these features by setting an environment variable SCIPY_ARRAY_API=1 and providing CuPy, PyTorch, JAX, or Dask arrays as array arguments. The following combinations of backend and device (or other capability) are supported.

====================  ====================  ====================
Library               CPU                   GPU
====================  ====================  ====================
NumPy                 ✅                     n/a                 
CuPy                  n/a                   ⛔                   
PyTorch               ✅                     ⛔                   
JAX                   ⚠️ no JIT             ⛔                   
Dask                  ⚠️ merges chunks      n/a                 
====================  ====================  ====================

See dev-arrayapi for more information.

Examples

from scipy.cluster.hierarchy import ward, fcluster, leaders
from scipy.spatial.distance import pdist

✓

Given a linkage matrix ``Z`` - obtained after apply a clustering method to a dataset ``X`` - and a flat cluster assignment array ``T``:

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))

✓

✗

array([[ 0.     ,  1.     ,  1.     ,  2.     ],
       [ 3.     ,  4.     ,  1.     ,  2.     ],
       [ 6.     ,  7.     ,  1.     ,  2.     ],
       [ 9.     , 10.     ,  1.     ,  2.     ],
       [ 2.     , 12.     ,  1.29099,  3.     ],
       [ 5.     , 13.     ,  1.29099,  3.     ],
       [ 8.     , 14.     ,  1.29099,  3.     ],
       [11.     , 15.     ,  1.29099,  3.     ],
       [16.     , 17.     ,  5.7735 ,  6.     ],
       [18.     , 19.     ,  5.7735 ,  6.     ],
       [20.     , 21.     ,  8.16497, 12.     ]])

T = fcluster(Z, 3, criterion='distance')
T

✓

array([1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4], dtype=int32)

`scipy.cluster.hierarchy.leaders` returns the indices of the nodes in the dendrogram that are the leaders of each flat cluster:

L, M = leaders(Z, T)
L

✓

array([16, 17, 18, 19], dtype=int32)

(remember that indices 0-11 point to the 12 data points in ``X``, whereas indices 12-22 point to the 11 rows of ``Z``) `scipy.cluster.hierarchy.leaders` also returns the indices of the flat clusters in ``T``:

✓

array([1, 2, 3, 4], dtype=int32)

Aliases

scipy.cluster.hierarchy.leaders