cluster.hierarchy

These functions cut hierarchical clusterings into flat clusterings or find the roots of the forest formed by a cut by providing the flat cluster ids of each observation.

fcluster
fclusterdata
leaders

These are routines for agglomerative clustering.

linkage
single
complete
average
weighted
centroid
median
ward

These routines compute statistics on hierarchies.

cophenet
from_mlab_linkage
inconsistent
maxinconsts
maxdists
maxRstat
to_mlab_linkage

Routines for visualizing flat clusters.

dendrogram

These are data structures and routines for representing hierarchies as tree objects.

ClusterNode
leaves_list
to_tree
cut_tree
optimal_leaf_ordering

These are predicates for checking the validity of linkage and inconsistency matrices as well as for checking isomorphism of two flat cluster assignments.

is_valid_im
is_valid_linkage
is_isomorphic
is_monotonic
correspond
num_obs_linkage

Utility routines for plotting:

set_link_color_palette

References

[1]”Statistics toolbox.” API Reference Documentation. The MathWorks. http://www.mathworks.com/access/helpdesk/help/toolbox/stats/. Accessed October 1, 2007.
[2]”Hierarchical clustering.” API Reference Documentation. The Wolfram Research, Inc. https://reference.wolfram.com/language/HierarchicalClustering/tutorial/HierarchicalClustering.html. Accessed October 1, 2007.
[3]Gower, JC and Ross, GJS. “Minimum Spanning Trees and Single Linkage Cluster Analysis.” Applied Statistics. 18(1): pp. 54–64. 1969.
[4]Ward Jr, JH. “Hierarchical grouping to optimize an objective function.” Journal of the American Statistical Association. 58(301): pp. 236–44. 1963.
[5]Johnson, SC. “Hierarchical clustering schemes.” Psychometrika. 32(2): pp. 241–54. 1966.
[6]Sneath, PH and Sokal, RR. “Numerical taxonomy.” Nature. 193: pp. 855–60. 1962.
[7]Batagelj, V. “Comparing resemblance measures.” Journal of Classification. 12: pp. 73–90. 1995.
[8]Sokal, RR and Michener, CD. “A statistical method for evaluating systematic relationships.” Scientific Bulletins. 38(22): pp. 1409–38. 1958.
[9]Edelbrock, C. “Mixture model tests of hierarchical clustering algorithms: the problem of classifying everybody.” Multivariate Behavioral Research. 14: pp. 367–84. 1979.
[10]Jain, A., and Dubes, R., “Algorithms for Clustering Data.” Prentice-Hall. Englewood Cliffs, NJ. 1988.
[11]Fisher, RA “The use of multiple measurements in taxonomic problems.” Annals of Eugenics, 7(2): 179-188. 1936
  • MATLAB and MathWorks are registered trademarks of The MathWorks, Inc.
  • Mathematica is a registered trademark of The Wolfram Research, Inc.

Module Contents

Classes

ClusterWarning()
ClusterNode(self,id,left=None,right=None,dist=0,count=1) A tree node class for representing a cluster.

Functions

_warning(s)
_copy_array_if_base_present(a) Copy the array if its base points to a parent array.
_copy_arrays_if_base_present(T) Accept a tuple of arrays T. Copies the array T[i] if its base array
_randdm(pnts) Generate a random distance matrix stored in condensed form.
single(y) Perform single/min/nearest linkage on the condensed distance matrix y.
complete(y) Perform complete/max/farthest point linkage on a condensed distance matrix.
average(y) Perform average/UPGMA linkage on a condensed distance matrix.
weighted(y) Perform weighted/WPGMA linkage on the condensed distance matrix.
centroid(y) Perform centroid/UPGMC linkage.
median(y) Perform median/WPGMC linkage.
ward(y) Perform Ward’s linkage on a condensed distance matrix.
linkage(y,method=”single”,metric=”euclidean”,optimal_ordering=False) Perform hierarchical/agglomerative clustering.
_order_cluster_tree(Z) Return clustering nodes in bottom-up order by distance.
cut_tree(Z,n_clusters=None,height=None) Given a linkage matrix Z, return the cut tree.
to_tree(Z,rd=False) Convert a linkage matrix into an easy-to-use tree object.
optimal_leaf_ordering(Z,y,metric=”euclidean”) Given a linkage matrix Z and distance, reorder the cut tree.
_convert_to_bool(X)
_convert_to_double(X)
cophenet(Z,Y=None) Calculate the cophenetic distances between each observation in
inconsistent(Z,d=2) r
from_mlab_linkage(Z) Convert a linkage matrix generated by MATLAB(TM) to a new
to_mlab_linkage(Z) Convert a linkage matrix to a MATLAB(TM) compatible one.
is_monotonic(Z) Return True if the linkage passed is monotonic.
is_valid_im(R,warning=False,throw=False,name=None) Return True if the inconsistency matrix passed is valid.
is_valid_linkage(Z,warning=False,throw=False,name=None) Check the validity of a linkage matrix.
_check_hierarchy_uses_cluster_before_formed(Z)
_check_hierarchy_uses_cluster_more_than_once(Z)
_check_hierarchy_not_all_clusters_used(Z)
num_obs_linkage(Z) Return the number of original observations of the linkage matrix passed.
correspond(Z,Y) Check for correspondence between linkage and condensed distance matrices.
fcluster(Z,t,criterion=”inconsistent”,depth=2,R=None,monocrit=None) Form flat clusters from the hierarchical clustering defined by
fclusterdata(X,t,criterion=”inconsistent”,metric=”euclidean”,depth=2,method=”single”,R=None) Cluster observation data using a given metric.
leaves_list(Z) Return a list of leaf node ids.
_remove_dups(L) Remove duplicates AND preserve the original order of the elements.
_get_tick_text_size(p)
_get_tick_rotation(p)
_plot_dendrogram(icoords,dcoords,ivl,p,n,mh,orientation,no_labels,color_list,leaf_font_size=None,leaf_rotation=None,contraction_marks=None,ax=None,above_threshold_color=”b”)
set_link_color_palette(palette) Set list of matplotlib color codes for use by dendrogram.
dendrogram(Z,p=30,truncate_mode=None,color_threshold=None,get_leaves=True,orientation=”top”,labels=None,count_sort=False,distance_sort=False,show_leaf_counts=True,no_plot=False,no_labels=False,leaf_font_size=None,leaf_rotation=None,leaf_label_func=None,show_contracted=False,link_color_func=None,ax=None,above_threshold_color=”b”) Plot the hierarchical clustering as a dendrogram.
_append_singleton_leaf_node(Z,p,n,level,lvs,ivl,leaf_label_func,i,labels)
_append_nonsingleton_leaf_node(Z,p,n,level,lvs,ivl,leaf_label_func,i,labels,show_leaf_counts)
_append_contraction_marks(Z,iv,i,n,contraction_marks)
_append_contraction_marks_sub(Z,iv,i,n,contraction_marks)
_dendrogram_calculate_info(Z,p,truncate_mode,color_threshold=None,get_leaves=True,orientation=”top”,labels=None,count_sort=False,distance_sort=False,show_leaf_counts=False,i=None,iv=0.0,ivl=list,n=0,icoord_list=list,dcoord_list=list,lvs=None,mhr=False,current_color=list,color_list=list,currently_below_threshold=list,leaf_label_func=None,level=0,contraction_marks=None,link_color_func=None,above_threshold_color=”b”) Calculate the endpoints of the links as well as the labels for the
is_isomorphic(T1,T2) Determine if two different cluster assignments are equivalent.
maxdists(Z) Return the maximum distance between any non-singleton cluster.
maxinconsts(Z,R) Return the maximum inconsistency coefficient for each
maxRstat(Z,R,i) Return the maximum statistic for each non-singleton cluster and its
leaders(Z,T) Return the root nodes in a hierarchical clustering.
class ClusterWarning
_warning(s)
_copy_array_if_base_present(a)

Copy the array if its base points to a parent array.

_copy_arrays_if_base_present(T)

Accept a tuple of arrays T. Copies the array T[i] if its base array points to an actual array. Otherwise, the reference is just copied. This is useful if the arrays are being passed to a C function that does not do proper striding.

_randdm(pnts)

Generate a random distance matrix stored in condensed form.

pnts : int
The number of points in the distance matrix. Has to be at least 2.
D : ndarray
A pnts * (pnts - 1) / 2 sized vector is returned.
single(y)

Perform single/min/nearest linkage on the condensed distance matrix y.

y : ndarray
The upper triangular of the distance matrix. The result of pdist is returned in this form.
Z : ndarray
The linkage matrix.

linkage: for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

complete(y)

Perform complete/max/farthest point linkage on a condensed distance matrix.

y : ndarray
The upper triangular of the distance matrix. The result of pdist is returned in this form.
Z : ndarray
A linkage matrix containing the hierarchical clustering. See the linkage function documentation for more information on its structure.

linkage: for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

average(y)

Perform average/UPGMA linkage on a condensed distance matrix.

y : ndarray
The upper triangular of the distance matrix. The result of pdist is returned in this form.
Z : ndarray
A linkage matrix containing the hierarchical clustering. See linkage for more information on its structure.

linkage: for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

weighted(y)

Perform weighted/WPGMA linkage on the condensed distance matrix.

See linkage for more information on the return structure and algorithm.

y : ndarray
The upper triangular of the distance matrix. The result of pdist is returned in this form.
Z : ndarray
A linkage matrix containing the hierarchical clustering. See linkage for more information on its structure.

linkage : for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

centroid(y)

Perform centroid/UPGMC linkage.

See linkage for more information on the input matrix, return structure, and algorithm.

The following are common calling conventions:

  1. Z = centroid(y)

    Performs centroid/UPGMC linkage on the condensed distance matrix y.

  2. Z = centroid(X)

    Performs centroid/UPGMC linkage on the observation matrix X using Euclidean distance as the distance metric.

y : ndarray
A condensed 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 a m by n array.
Z : ndarray
A linkage matrix containing the hierarchical clustering. See the linkage function documentation for more information on its structure.

linkage: for advanced creation of hierarchical clusterings.

median(y)

Perform median/WPGMC linkage.

See linkage for more information on the return structure and algorithm.

The following are common calling conventions:

  1. Z = median(y)

    Performs median/WPGMC linkage on the condensed distance matrix y. See linkage for more information on the return structure and algorithm.

  2. Z = median(X)

    Performs median/WPGMC linkage on the observation matrix X using Euclidean distance as the distance metric. See linkage for more information on the return structure and algorithm.

y : ndarray
A condensed 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 a m by n array.
Z : ndarray
The hierarchical clustering encoded as a linkage matrix.

linkage: for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

ward(y)

Perform Ward’s linkage on a condensed distance matrix.

See linkage for more information on the return structure and algorithm.

The following are common calling conventions:

  1. Z = ward(y) Performs Ward’s linkage on the condensed distance matrix y.
  2. Z = ward(X) Performs Ward’s linkage on the observation matrix X using Euclidean distance as the distance metric.
y : ndarray
A condensed 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 a m by n array.
Z : ndarray
The hierarchical clustering encoded as a linkage matrix. See linkage for more information on the return structure and algorithm.

linkage: for advanced creation of hierarchical clusterings. scipy.spatial.distance.pdist : pairwise distance metrics

linkage(y, method="single", metric="euclidean", optimal_ordering=False)

Perform hierarchical/agglomerative clustering.

The input y may be either a 1d compressed distance matrix or a 2d array of observation vectors.

If y is a 1d compressed distance matrix, then y must be a sized vector where n is the number of original observations paired in the distance matrix. The behavior of this function is very similar to the MATLAB linkage function.

A by 4 matrix Z is returned. At the -th iteration, clusters with indices Z[i, 0] and Z[i, 1] are combined to form cluster . A cluster with an index less than corresponds to one of the 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.

The following linkage methods are used to compute the distance between two clusters and . The algorithm begins with a forest of clusters that have yet to be used in the hierarchy being formed. When two clusters and from this forest are combined into a single cluster , and are removed from the forest, and is added to the forest. When only one cluster remains in the forest, the algorithm stops, and this cluster becomes the root.

A distance matrix is maintained at each iteration. The d[i,j] entry corresponds to the distance between cluster and in the original forest.

At each iteration, the algorithm must update the distance matrix to reflect the distance of the newly formed cluster u with the remaining clusters in the forest.

Suppose there are original observations in cluster and original objects in cluster . Recall and are combined to form cluster . Let be any remaining cluster in the forest that is not .

The following are methods for calculating the distance between the newly formed cluster and each .

  • method=’single’ assigns

    for all points in cluster and in cluster . This is also known as the Nearest Point Algorithm.

  • method=’complete’ assigns

    for all points in cluster u and in cluster . This is also known by the Farthest Point Algorithm or Voor Hees Algorithm.

  • method=’average’ assigns

    for all points and where and are the cardinalities of clusters and , respectively. This is also called the UPGMA algorithm.

  • method=’weighted’ assigns

    where cluster u was formed with cluster s and t and v is a remaining cluster in the forest. (also called WPGMA)

  • method=’centroid’ assigns

    where and are the centroids of clusters and , respectively. When two clusters and are combined into a new cluster , the new centroid is computed over all the original objects in clusters and . The distance then becomes the Euclidean distance between the centroid of and the centroid of a remaining cluster in the forest. This is also known as the UPGMC algorithm.

  • method=’median’ assigns like the centroid method. When two clusters and are combined into a new cluster , the average of centroids s and t give the new centroid . This is also known as the WPGMC algorithm.

  • method=’ward’ uses the Ward variance minimization algorithm. The new entry is computed as follows,

    where is the newly joined cluster consisting of clusters and , is an unused cluster in the forest, , and is the cardinality of its argument. This is also known as the incremental algorithm.

Warning: When the minimum distance pair in the forest is chosen, there may be two or more pairs with the same minimum distance. This implementation may choose a different minimum than the MATLAB version.

y : ndarray
A condensed 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 observation vectors in dimensions may be passed as an by array. All elements of the condensed distance matrix must be finite, i.e. no NaNs or infs.
method : str, optional
The linkage algorithm to use. See the Linkage Methods section below for full descriptions.
metric : str or function, optional
The distance metric to use in the case that y is a collection of observation vectors; ignored otherwise. See the pdist function for a list of valid distance metrics. A custom distance function can also be used.
optimal_ordering : bool, optional

If True, the linkage matrix will be reordered so that the distance between successive leaves is minimal. This results in a more intuitive tree structure when the data are visualized. defaults to False, because this algorithm can be slow, particularly on large datasets [2]_. See also the optimal_leaf_ordering function.

New in version 1.0.0.

Z : ndarray
The hierarchical clustering encoded as a linkage matrix.
  1. For method ‘single’ an optimized algorithm based on minimum spanning tree is implemented. It has time complexity . For methods ‘complete’, ‘average’, ‘weighted’ and ‘ward’ an algorithm called nearest-neighbors chain is implemented. It also has time complexity . For other methods a naive algorithm is implemented with time complexity. All algorithms use memory. Refer to [1]_ for details about the algorithms.
  2. Methods ‘centroid’, ‘median’ and ‘ward’ are correctly defined only if Euclidean pairwise metric is used. If y is passed as precomputed pairwise distances, then it is a user responsibility to assure that these distances are in fact Euclidean, otherwise the produced result will be incorrect.

scipy.spatial.distance.pdist : pairwise distance metrics

[1]Daniel Mullner, “Modern hierarchical, agglomerative clustering algorithms”, :arXiv:`1109.2378v1`.
[2]Ziv Bar-Joseph, David K. Gifford, Tommi S. Jaakkola, “Fast optimal leaf ordering for hierarchical clustering”, 2001. Bioinformatics https://doi.org/10.1093/bioinformatics/17.suppl_1.S22
>>> from scipy.cluster.hierarchy import dendrogram, linkage
>>> from matplotlib import pyplot as plt
>>> X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
>>> Z = linkage(X, 'ward')
>>> fig = plt.figure(figsize=(25, 10))
>>> dn = dendrogram(Z)
>>> Z = linkage(X, 'single')
>>> fig = plt.figure(figsize=(25, 10))
>>> dn = dendrogram(Z)
>>> plt.show()
class ClusterNode(id, left=None, right=None, dist=0, count=1)

A tree node class for representing a cluster.

Leaf nodes correspond to original observations, while non-leaf nodes correspond to non-singleton clusters.

The to_tree function converts a matrix returned by the linkage function into an easy-to-use tree representation.

All parameter names are also attributes.

id : int
The node id.
left : ClusterNode instance, optional
The left child tree node.
right : ClusterNode instance, optional
The right child tree node.
dist : float, optional
Distance for this cluster in the linkage matrix.
count : int, optional
The number of samples in this cluster.

to_tree : for converting a linkage matrix Z into a tree object.

__init__(id, left=None, right=None, dist=0, count=1)
__lt__(node)
__gt__(node)
__eq__(node)
get_id()

The identifier of the target node.

For 0 <= i < n, i corresponds to original observation i. For n <= i < 2n-1, i corresponds to non-singleton cluster formed at iteration i-n.

id : int
The identifier of the target node.
get_count()

The number of leaf nodes (original observations) belonging to the cluster node nd. If the target node is a leaf, 1 is returned.

get_count : int
The number of leaf nodes below the target node.
get_left()

Return a reference to the left child tree object.

left : ClusterNode
The left child of the target node. If the node is a leaf, None is returned.
get_right()

Return a reference to the right child tree object.

right : ClusterNode
The left child of the target node. If the node is a leaf, None is returned.
is_leaf()

Return True if the target node is a leaf.

leafness : bool
True if the target node is a leaf node.
pre_order(func=None)

Perform pre-order traversal without recursive function calls.

When a leaf node is first encountered, func is called with the leaf node as its argument, and its result is appended to the list.

For example, the statement:

ids = root.pre_order(lambda x: x.id)

returns a list of the node ids corresponding to the leaf nodes of the tree as they appear from left to right.

func : function
Applied to each leaf ClusterNode object in the pre-order traversal. Given the i-th leaf node in the pre-order traversal n[i], the result of func(n[i]) is stored in L[i]. If not provided, the index of the original observation to which the node corresponds is used.
L : list
The pre-order traversal.
_order_cluster_tree(Z)

Return clustering nodes in bottom-up order by distance.

Z : scipy.cluster.linkage array
The linkage matrix.
nodes : list
A list of ClusterNode objects.
cut_tree(Z, n_clusters=None, height=None)

Given a linkage matrix Z, return the cut tree.

Z : scipy.cluster.linkage array
The linkage matrix.
n_clusters : array_like, optional
Number of clusters in the tree at the cut point.
height : array_like, optional
The height at which to cut the tree. Only possible for ultrametric trees.
cutree : array
An array indicating group membership at each agglomeration step. I.e., for a full cut tree, in the first column each data point is in its own cluster. At the next step, two nodes are merged. Finally all singleton and non-singleton clusters are in one group. If n_clusters or height is given, the columns correspond to the columns of n_clusters or height.
>>> from scipy import cluster
>>> np.random.seed(23)
>>> X = np.random.randn(50, 4)
>>> Z = cluster.hierarchy.ward(X)
>>> cutree = cluster.hierarchy.cut_tree(Z, n_clusters=[5, 10])
>>> cutree[:10]
array([[0, 0],
       [1, 1],
       [2, 2],
       [3, 3],
       [3, 4],
       [2, 2],
       [0, 0],
       [1, 5],
       [3, 6],
       [4, 7]])
to_tree(Z, rd=False)

Convert a linkage matrix into an easy-to-use tree object.

The reference to the root ClusterNode object is returned (by default).

Each ClusterNode object has a left, right, dist, id, and count attribute. The left and right attributes point to ClusterNode objects that were combined to generate the cluster. If both are None then the ClusterNode object is a leaf node, its count must be 1, and its distance is meaningless but set to 0.

Note: This function is provided for the convenience of the library user. ClusterNodes are not used as input to any of the functions in this library.

Z : ndarray
The linkage matrix in proper form (see the linkage function documentation).
rd : bool, optional
When False (default), a reference to the root ClusterNode object is returned. Otherwise, a tuple (r, d) is returned. r is a reference to the root node while d is a list of ClusterNode objects - one per original entry in the linkage matrix plus entries for all clustering steps. If a cluster id is less than the number of samples n in the data that the linkage matrix describes, then it corresponds to a singleton cluster (leaf node). See linkage for more information on the assignment of cluster ids to clusters.
tree : ClusterNode or tuple (ClusterNode, list of ClusterNode)
If rd is False, a ClusterNode. If rd is True, a list of length 2*n - 1, with n the number of samples. See the description of rd above for more details.

linkage, is_valid_linkage, ClusterNode

>>> from scipy.cluster import hierarchy
>>> x = np.random.rand(10).reshape(5, 2)
>>> Z = hierarchy.linkage(x)
>>> hierarchy.to_tree(Z)
<scipy.cluster.hierarchy.ClusterNode object at ...
>>> rootnode, nodelist = hierarchy.to_tree(Z, rd=True)
>>> rootnode
<scipy.cluster.hierarchy.ClusterNode object at ...
>>> len(nodelist)
9
optimal_leaf_ordering(Z, y, metric="euclidean")

Given a linkage matrix Z and distance, reorder the cut tree.

Z : ndarray
The hierarchical clustering encoded as a linkage matrix. See linkage for more information on the return structure and algorithm.
y : ndarray
The condensed distance matrix from which Z was generated. Alternatively, a collection of m observation vectors in n dimensions may be passed as a m by n array.
metric : str or function, optional
The distance metric to use in the case that y is a collection of observation vectors; ignored otherwise. See the pdist function for a list of valid distance metrics. A custom distance function can also be used.
Z_ordered : ndarray
A copy of the linkage matrix Z, reordered to minimize the distance between adjacent leaves.
>>> from scipy.cluster import hierarchy
>>> np.random.seed(23)
>>> X = np.random.randn(10,10)
>>> Z = hierarchy.ward(X)
>>> hierarchy.leaves_list(Z)
array([0, 5, 3, 9, 6, 8, 1, 4, 2, 7], dtype=int32)
>>> hierarchy.leaves_list(hierarchy.optimal_leaf_ordering(Z, X))
array([3, 9, 0, 5, 8, 2, 7, 4, 1, 6], dtype=int32)
_convert_to_bool(X)
_convert_to_double(X)
cophenet(Z, Y=None)

Calculate the cophenetic distances between each observation in the hierarchical clustering defined by the linkage Z.

Suppose p and q are original observations in disjoint clusters s and t, respectively and s and t are joined by a direct parent cluster u. The cophenetic distance between observations i and j is simply the distance between clusters s and t.

Z : ndarray
The hierarchical clustering encoded as an array (see linkage function).
Y : ndarray (optional)
Calculates the cophenetic correlation coefficient c of a hierarchical clustering defined by the linkage matrix Z of a set of observations in dimensions. Y is the condensed distance matrix from which Z was generated.
c : ndarray
The cophentic correlation distance (if Y is passed).
d : ndarray
The cophenetic distance matrix in condensed form. The th entry is the cophenetic distance between original observations and .
inconsistent(Z, d=2)

r Calculate inconsistency statistics on a linkage matrix.

Z : ndarray
The by 4 matrix encoding the linkage (hierarchical clustering). See linkage documentation for more information on its form.
d : int, optional
The number of links up to d levels below each non-singleton cluster.
R : ndarray

A by 5 matrix where the i’th row contains the link statistics for the non-singleton cluster i. The link statistics are computed over the link heights for links levels below the cluster i. R[i,0] and R[i,1] are the mean and standard deviation of the link heights, respectively; R[i,2] is the number of links included in the calculation; and R[i,3] is the inconsistency coefficient,

This function behaves similarly to the MATLAB(TM) inconsistent function.

>>> from scipy.cluster.hierarchy import inconsistent, linkage
>>> from matplotlib import pyplot as plt
>>> X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
>>> Z = linkage(X, 'ward')
>>> print(Z)
[[  5.           6.           0.           2.        ]
 [  2.           7.           0.           2.        ]
 [  0.           4.           1.           2.        ]
 [  1.           8.           1.15470054   3.        ]
 [  9.          10.           2.12132034   4.        ]
 [  3.          12.           4.11096096   5.        ]
 [ 11.          13.          14.07183949   8.        ]]
>>> inconsistent(Z)
array([[ 0.        ,  0.        ,  1.        ,  0.        ],
       [ 0.        ,  0.        ,  1.        ,  0.        ],
       [ 1.        ,  0.        ,  1.        ,  0.        ],
       [ 0.57735027,  0.81649658,  2.        ,  0.70710678],
       [ 1.04044011,  1.06123822,  3.        ,  1.01850858],
       [ 3.11614065,  1.40688837,  2.        ,  0.70710678],
       [ 6.44583366,  6.76770586,  3.        ,  1.12682288]])
from_mlab_linkage(Z)

Convert a linkage matrix generated by MATLAB(TM) to a new linkage matrix compatible with this module.

The conversion does two things:

  • the indices are converted from 1..N to 0..(N-1) form, and
  • a fourth column Z[:,3] is added where Z[i,3] represents the number of original observations (leaves) in the non-singleton cluster i.

This function is useful when loading in linkages from legacy data files generated by MATLAB.

Z : ndarray
A linkage matrix generated by MATLAB(TM).
ZS : ndarray
A linkage matrix compatible with scipy.cluster.hierarchy.
to_mlab_linkage(Z)

Convert a linkage matrix to a MATLAB(TM) compatible one.

Converts a linkage matrix Z generated by the linkage function of this module to a MATLAB(TM) compatible one. The return linkage matrix has the last column removed and the cluster indices are converted to 1..N indexing.

Z : ndarray
A linkage matrix generated by scipy.cluster.hierarchy.
to_mlab_linkage : ndarray

A linkage matrix compatible with MATLAB(TM)’s hierarchical clustering functions.

The return linkage matrix has the last column removed and the cluster indices are converted to 1..N indexing.

is_monotonic(Z)

Return True if the linkage passed is monotonic.

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

Z : ndarray
The linkage matrix to check for monotonicity.
b : bool
A boolean indicating whether the linkage is monotonic.
is_valid_im(R, warning=False, throw=False, name=None)

Return True if the inconsistency matrix passed is valid.

It must be a by 4 array of doubles. The standard deviations R[:,1] must be nonnegative. The link counts R[:,2] must be positive and no greater than .

R : ndarray
The inconsistency matrix to check for validity.
warning : bool, optional
When True, issues a Python warning if the linkage matrix passed is invalid.
throw : bool, optional
When True, throws a Python exception if the linkage matrix passed is invalid.
name : str, optional
This string refers to the variable name of the invalid linkage matrix.
b : bool
True if the inconsistency matrix is valid.
is_valid_linkage(Z, warning=False, throw=False, name=None)

Check the validity of a linkage matrix.

A linkage matrix is valid if it is a two dimensional array (type double) with rows and 4 columns. The first two columns must contain indices between 0 and . For a given row i, the following two expressions have to hold:

I.e. a cluster cannot join another cluster unless the cluster being joined has been generated.

Z : array_like
Linkage matrix.
warning : bool, optional
When True, issues a Python warning if the linkage matrix passed is invalid.
throw : bool, optional
When True, throws a Python exception if the linkage matrix passed is invalid.
name : str, optional
This string refers to the variable name of the invalid linkage matrix.
b : bool
True if the inconsistency matrix is valid.
_check_hierarchy_uses_cluster_before_formed(Z)
_check_hierarchy_uses_cluster_more_than_once(Z)
_check_hierarchy_not_all_clusters_used(Z)
num_obs_linkage(Z)

Return the number of original observations of the linkage matrix passed.

Z : ndarray
The linkage matrix on which to perform the operation.
n : int
The number of original observations in the linkage.
correspond(Z, Y)

Check for correspondence between linkage and condensed distance matrices.

They must have the same number of original observations for the check to succeed.

This function is useful as a sanity check in algorithms that make extensive use of linkage and distance matrices that must correspond to the same set of original observations.

Z : array_like
The linkage matrix to check for correspondence.
Y : array_like
The condensed distance matrix to check for correspondence.
b : bool
A boolean indicating whether the linkage matrix and distance matrix could possibly correspond to one another.
fcluster(Z, t, criterion="inconsistent", depth=2, R=None, monocrit=None)

Form flat clusters from the hierarchical clustering defined by the given linkage matrix.

Z : ndarray
The hierarchical clustering encoded with the matrix returned by the linkage function.
t : float
The threshold to apply when forming flat clusters.
criterion : str, optional

The criterion to use in forming flat clusters. This can be any of the following values:

inconsistent : If a cluster node and all its
descendants have an inconsistent value less than or equal to t then all its leaf descendants belong to the same flat cluster. When no non-singleton cluster meets this criterion, every node is assigned to its own cluster. (Default)
distance : Forms flat clusters so that the original
observations in each flat cluster have no greater a cophenetic distance than t.
maxclust : Finds a minimum threshold r so that
the cophenetic distance between any two original observations in the same flat cluster is no more than r and no more than t flat clusters are formed.
monocrit : Forms a flat cluster from a cluster node c

with index i when monocrit[j] <= t.

For example, to threshold on the maximum mean distance as computed in the inconsistency matrix R with a threshold of 0.8 do:

MR = maxRstat(Z, R, 3)
cluster(Z, t=0.8, criterion='monocrit', monocrit=MR)
maxclust_monocrit : Forms a flat cluster from a

non-singleton cluster node c when monocrit[i] <= r for all cluster indices i below and including c. r is minimized such that no more than t flat clusters are formed. monocrit must be monotonic. For example, to minimize the threshold t on maximum inconsistency values so that no more than 3 flat clusters are formed, do:

MI = maxinconsts(Z, R)
cluster(Z, t=3, criterion='maxclust_monocrit', monocrit=MI)
depth : int, optional
The maximum depth to perform the inconsistency calculation. It has no meaning for the other criteria. Default is 2.
R : ndarray, optional
The inconsistency matrix to use for the ‘inconsistent’ criterion. This matrix is computed if not provided.
monocrit : ndarray, optional
An array of length n-1. monocrit[i] is the statistics upon which non-singleton i is thresholded. The monocrit vector must be monotonic, i.e. given a node c with index i, for all node indices j corresponding to nodes below c, monocrit[i] >= monocrit[j].
fcluster : ndarray
An array of length n. T[i] is the flat cluster number to which original observation i belongs.
fclusterdata(X, t, criterion="inconsistent", metric="euclidean", depth=2, method="single", R=None)

Cluster observation data using a given metric.

Clusters the original observations in the n-by-m data matrix X (n observations in m dimensions), using the euclidean distance metric to calculate distances between original observations, performs hierarchical clustering using the single linkage algorithm, and forms flat clusters using the inconsistency method with t as the cut-off threshold.

A one-dimensional array T of length n is returned. T[i] is the index of the flat cluster to which the original observation i belongs.

X : (N, M) ndarray
N by M data matrix with N observations in M dimensions.
t : float
The threshold to apply when forming flat clusters.
criterion : str, optional
Specifies the criterion for forming flat clusters. Valid values are ‘inconsistent’ (default), ‘distance’, or ‘maxclust’ cluster formation algorithms. See fcluster for descriptions.
metric : str, optional
The distance metric for calculating pairwise distances. See distance.pdist for descriptions and linkage to verify compatibility with the linkage method.
depth : int, optional
The maximum depth for the inconsistency calculation. See inconsistent for more information.
method : str, optional
The linkage method to use (single, complete, average, weighted, median centroid, ward). See linkage for more information. Default is “single”.
R : ndarray, optional
The inconsistency matrix. It will be computed if necessary if it is not passed.
fclusterdata : ndarray
A vector of length n. T[i] is the flat cluster number to which original observation i belongs.

scipy.spatial.distance.pdist : pairwise distance metrics

This function is similar to the MATLAB function clusterdata.

leaves_list(Z)

Return a list of leaf node ids.

The return corresponds to the observation vector index as it appears in the tree from left to right. Z is a linkage matrix.

Z : ndarray
The hierarchical clustering encoded as a matrix. Z is a linkage matrix. See linkage for more information.
leaves_list : ndarray
The list of leaf node ids.
_remove_dups(L)

Remove duplicates AND preserve the original order of the elements.

The set class is not guaranteed to do this.

_get_tick_text_size(p)
_get_tick_rotation(p)
_plot_dendrogram(icoords, dcoords, ivl, p, n, mh, orientation, no_labels, color_list, leaf_font_size=None, leaf_rotation=None, contraction_marks=None, ax=None, above_threshold_color="b")

Set list of matplotlib color codes for use by dendrogram.

Note that this palette is global (i.e. setting it once changes the colors for all subsequent calls to dendrogram) and that it affects only the the colors below color_threshold.

Note that dendrogram also accepts a custom coloring function through its link_color_func keyword, which is more flexible and non-global.

palette : list of str or None

A list of matplotlib color codes. The order of the color codes is the order in which the colors are cycled through when color thresholding in the dendrogram.

If None, resets the palette to its default (which is ['g', 'r', 'c', 'm', 'y', 'k']).

None

dendrogram

Ability to reset the palette with None added in Scipy 0.17.0.

>>> from scipy.cluster import hierarchy
>>> ytdist = np.array([662., 877., 255., 412., 996., 295., 468., 268.,
...                    400., 754., 564., 138., 219., 869., 669.])
>>> Z = hierarchy.linkage(ytdist, 'single')
>>> dn = hierarchy.dendrogram(Z, no_plot=True)
>>> dn['color_list']
['g', 'b', 'b', 'b', 'b']
>>> hierarchy.set_link_color_palette(['c', 'm', 'y', 'k'])
>>> dn = hierarchy.dendrogram(Z, no_plot=True)
>>> dn['color_list']
['c', 'b', 'b', 'b', 'b']
>>> dn = hierarchy.dendrogram(Z, no_plot=True, color_threshold=267,
...                           above_threshold_color='k')
>>> dn['color_list']
['c', 'm', 'm', 'k', 'k']

Now reset the color palette to its default:

>>> hierarchy.set_link_color_palette(None)
dendrogram(Z, p=30, truncate_mode=None, color_threshold=None, get_leaves=True, orientation="top", labels=None, count_sort=False, distance_sort=False, show_leaf_counts=True, no_plot=False, no_labels=False, leaf_font_size=None, leaf_rotation=None, leaf_label_func=None, show_contracted=False, link_color_func=None, ax=None, above_threshold_color="b")

Plot the hierarchical clustering as a dendrogram.

The dendrogram illustrates how each cluster is composed by drawing a U-shaped link between a non-singleton cluster and its children. The top of the U-link indicates a cluster merge. The two legs of the U-link indicate which clusters were merged. The length of the two legs of the U-link represents the distance between the child clusters. It is also the cophenetic distance between original observations in the two children clusters.

Z : ndarray
The linkage matrix encoding the hierarchical clustering to render as a dendrogram. See the linkage function for more information on the format of Z.
p : int, optional
The p parameter for truncate_mode.
truncate_mode : str, optional

The dendrogram can be hard to read when the original observation matrix from which the linkage is derived is large. Truncation is used to condense the dendrogram. There are several modes:

None
No truncation is performed (default). Note: 'none' is an alias for None that’s kept for backward compatibility.
'lastp'
The last p non-singleton clusters formed in the linkage are the only non-leaf nodes in the linkage; they correspond to rows Z[n-p-2:end] in Z. All other non-singleton clusters are contracted into leaf nodes.
'level'

No more than p levels of the dendrogram tree are displayed. A “level” includes all nodes with p merges from the last merge.

Note: 'mtica' is an alias for 'level' that’s kept for backward compatibility.

color_threshold : double, optional
For brevity, let be the color_threshold. Colors all the descendent links below a cluster node the same color if is the first node below the cut threshold . All links connecting nodes with distances greater than or equal to the threshold are colored blue. If is less than or equal to zero, all nodes are colored blue. If color_threshold is None or ‘default’, corresponding with MATLAB(TM) behavior, the threshold is set to 0.7*max(Z[:,2]).
get_leaves : bool, optional
Includes a list R['leaves']=H in the result dictionary. For each , H[i] == j, cluster node j appears in position i in the left-to-right traversal of the leaves, where and .
orientation : str, optional

The direction to plot the dendrogram, which can be any of the following strings:

'top'
Plots the root at the top, and plot descendent links going downwards. (default).
'bottom'
Plots the root at the bottom, and plot descendent links going upwards.
'left'
Plots the root at the left, and plot descendent links going right.
'right'
Plots the root at the right, and plot descendent links going left.
labels : ndarray, optional
By default labels is None so the index of the original observation is used to label the leaf nodes. Otherwise, this is an -sized list (or tuple). The labels[i] value is the text to put under the th leaf node only if it corresponds to an original observation and not a non-singleton cluster.
count_sort : str or bool, optional

For each node n, the order (visually, from left-to-right) n’s two descendent links are plotted is determined by this parameter, which can be any of the following values:

False
Nothing is done.
'ascending' or True
The child with the minimum number of original objects in its cluster is plotted first.
'descendent'
The child with the maximum number of original objects in its cluster is plotted first.

Note distance_sort and count_sort cannot both be True.

distance_sort : str or bool, optional

For each node n, the order (visually, from left-to-right) n’s two descendent links are plotted is determined by this parameter, which can be any of the following values:

False
Nothing is done.
'ascending' or True
The child with the minimum distance between its direct descendents is plotted first.
'descending'
The child with the maximum distance between its direct descendents is plotted first.

Note distance_sort and count_sort cannot both be True.

show_leaf_counts : bool, optional
When True, leaf nodes representing original observation are labeled with the number of observations they contain in parentheses.
no_plot : bool, optional
When True, the final rendering is not performed. This is useful if only the data structures computed for the rendering are needed or if matplotlib is not available.
no_labels : bool, optional
When True, no labels appear next to the leaf nodes in the rendering of the dendrogram.
leaf_rotation : double, optional
Specifies the angle (in degrees) to rotate the leaf labels. When unspecified, the rotation is based on the number of nodes in the dendrogram (default is 0).
leaf_font_size : int, optional
Specifies the font size (in points) of the leaf labels. When unspecified, the size based on the number of nodes in the dendrogram.
leaf_label_func : lambda or function, optional

When leaf_label_func is a callable function, for each leaf with cluster index . The function is expected to return a string with the label for the leaf.

Indices correspond to original observations while indices correspond to non-singleton clusters.

For example, to label singletons with their node id and non-singletons with their id, count, and inconsistency coefficient, simply do:

# First define the leaf label function.
def llf(id):
    if id < n:
        return str(id)
    else:
        return '[%d %d %1.2f]' % (id, count, R[n-id,3])
# The text for the leaf nodes is going to be big so force
# a rotation of 90 degrees.
dendrogram(Z, leaf_label_func=llf, leaf_rotation=90)
show_contracted : bool, optional
When True the heights of non-singleton nodes contracted into a leaf node are plotted as crosses along the link connecting that leaf node. This really is only useful when truncation is used (see truncate_mode parameter).
link_color_func : callable, optional

If given, link_color_function is called with each non-singleton id corresponding to each U-shaped link it will paint. The function is expected to return the color to paint the link, encoded as a matplotlib color string code. For example:

dendrogram(Z, link_color_func=lambda k: colors[k])

colors the direct links below each untruncated non-singleton node k using colors[k].

ax : matplotlib Axes instance, optional
If None and no_plot is not True, the dendrogram will be plotted on the current axes. Otherwise if no_plot is not True the dendrogram will be plotted on the given Axes instance. This can be useful if the dendrogram is part of a more complex figure.
above_threshold_color : str, optional
This matplotlib color string sets the color of the links above the color_threshold. The default is ‘b’.
R : dict

A dictionary of data structures computed to render the dendrogram. Its has the following keys:

'color_list'
A list of color names. The k’th element represents the color of the k’th link.
'icoord' and 'dcoord'
Each of them is a list of lists. Let icoord = [I1, I2, ..., Ip] where Ik = [xk1, xk2, xk3, xk4] and dcoord = [D1, D2, ..., Dp] where Dk = [yk1, yk2, yk3, yk4], then the k’th link painted is (xk1, yk1) - (xk2, yk2) - (xk3, yk3) - (xk4, yk4).
'ivl'
A list of labels corresponding to the leaf nodes.
'leaves'
For each i, H[i] == j, cluster node j appears in position i in the left-to-right traversal of the leaves, where and . If j is less than n, the i-th leaf node corresponds to an original observation. Otherwise, it corresponds to a non-singleton cluster.

linkage, set_link_color_palette

It is expected that the distances in Z[:,2] be monotonic, otherwise crossings appear in the dendrogram.

>>> from scipy.cluster import hierarchy
>>> import matplotlib.pyplot as plt

A very basic example:

>>> ytdist = np.array([662., 877., 255., 412., 996., 295., 468., 268.,
...                    400., 754., 564., 138., 219., 869., 669.])
>>> Z = hierarchy.linkage(ytdist, 'single')
>>> plt.figure()
>>> dn = hierarchy.dendrogram(Z)

Now plot in given axes, improve the color scheme and use both vertical and horizontal orientations:

>>> hierarchy.set_link_color_palette(['m', 'c', 'y', 'k'])
>>> fig, axes = plt.subplots(1, 2, figsize=(8, 3))
>>> dn1 = hierarchy.dendrogram(Z, ax=axes[0], above_threshold_color='y',
...                            orientation='top')
>>> dn2 = hierarchy.dendrogram(Z, ax=axes[1],
...                            above_threshold_color='#bcbddc',
...                            orientation='right')
>>> hierarchy.set_link_color_palette(None)  # reset to default after use
>>> plt.show()
_append_singleton_leaf_node(Z, p, n, level, lvs, ivl, leaf_label_func, i, labels)
_append_nonsingleton_leaf_node(Z, p, n, level, lvs, ivl, leaf_label_func, i, labels, show_leaf_counts)
_append_contraction_marks(Z, iv, i, n, contraction_marks)
_append_contraction_marks_sub(Z, iv, i, n, contraction_marks)
_dendrogram_calculate_info(Z, p, truncate_mode, color_threshold=None, get_leaves=True, orientation="top", labels=None, count_sort=False, distance_sort=False, show_leaf_counts=False, i=None, iv=0.0, ivl=list, n=0, icoord_list=list, dcoord_list=list, lvs=None, mhr=False, current_color=list, color_list=list, currently_below_threshold=list, leaf_label_func=None, level=0, contraction_marks=None, link_color_func=None, above_threshold_color="b")

Calculate the endpoints of the links as well as the labels for the the dendrogram rooted at the node with index i. iv is the independent variable value to plot the left-most leaf node below the root node i (if orientation=’top’, this would be the left-most x value where the plotting of this root node i and its descendents should begin).

ivl is a list to store the labels of the leaf nodes. The leaf_label_func is called whenever ivl != None, labels == None, and leaf_label_func != None. When ivl != None and labels != None, the labels list is used only for labeling the leaf nodes. When ivl == None, no labels are generated for leaf nodes.

When get_leaves==True, a list of leaves is built as they are visited in the dendrogram.

Returns a tuple with l being the independent variable coordinate that corresponds to the midpoint of cluster to the left of cluster i if i is non-singleton, otherwise the independent coordinate of the leaf node if i is a leaf node.

A tuple (left, w, h, md), where:

  • left is the independent variable coordinate of the center of the the U of the subtree
  • w is the amount of space used for the subtree (in independent variable units)
  • h is the height of the subtree in dependent variable units
  • md is the max(Z[*,2]) for all nodes * below and including the target node.
is_isomorphic(T1, T2)

Determine if two different cluster assignments are equivalent.

T1 : array_like
An assignment of singleton cluster ids to flat cluster ids.
T2 : array_like
An assignment of singleton cluster ids to flat cluster ids.
b : bool
Whether the flat cluster assignments T1 and T2 are equivalent.
maxdists(Z)

Return the maximum distance between any non-singleton cluster.

Z : ndarray
The hierarchical clustering encoded as a matrix. See linkage for more information.
maxdists : ndarray
A (n-1) sized numpy array of doubles; MD[i] represents the maximum distance between any cluster (including singletons) below and including the node with index i. More specifically, MD[i] = Z[Q(i)-n, 2].max() where Q(i) is the set of all node indices below and including node i.
maxinconsts(Z, R)

Return the maximum inconsistency coefficient for each non-singleton cluster and its descendents.

Z : ndarray
The hierarchical clustering encoded as a matrix. See linkage for more information.
R : ndarray
The inconsistency matrix.
MI : ndarray
A monotonic (n-1)-sized numpy array of doubles.
maxRstat(Z, R, i)

Return the maximum statistic for each non-singleton cluster and its descendents.

Z : array_like
The hierarchical clustering encoded as a matrix. See linkage for more information.
R : array_like
The inconsistency matrix.
i : int
The column of R to use as the statistic.
MR : ndarray
Calculates the maximum statistic for the i’th column of the inconsistency matrix R for each non-singleton cluster node. MR[j] is the maximum over R[Q(j)-n, i] where Q(j) the set of all node ids corresponding to nodes below and including j.
leaders(Z, T)

Return the root nodes in a hierarchical clustering.

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 of the flat clusters represented in the n-sized flat cluster assignment vector T, this function finds the lowest cluster node in the linkage tree Z such that:

  • leaf descendents belong only to flat cluster j (i.e. T[p]==j for all in where is the set of leaf ids of leaf nodes descendent with cluster node )
  • there does not exist a leaf that is not descendent with that also belongs to cluster (i.e. T[q]!=j for all not in ). If this condition is violated, T is not a valid cluster assignment vector, and an exception will be thrown.
Z : ndarray
The hierarchical clustering encoded as a matrix. See linkage for more information.
T : ndarray
The flat cluster assignment vector.
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.

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

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.