table constants for the lance-williams update rule for various linkage functionswith ni nm denoting the number of elements in the corresponding clusters linkage single complete group avg ward linkage matrix / / ni ni ni nm ni nm / / nj ni nm ni nm - / / -nm ni nm in practicealgorithm is run until single cluster is obtained instead of returning the label sets of all clustersa linkage matrix is returned that contains the same information at the end of each iteration (line the linkage matrix stores the merged labels and jas well as the (minimaldistance di other information such as the number of elements in the merged cluster can also be stored dendrograms and cluster labels can be directly constructed from the linkage matrix in the following examplethe linkage matrix is returned by the method agg_cluster example (agglomerative hierarchical clusteringthe python code below gives basic implementation of algorithm using the ward linkage function the methods fcluster and dendrogram from the scipy module can be used to identify the labels in cluster and to draw the corresponding dendrogram aggcluster py import numpy as np from scipy spatial distance import cdist def update_distances ( , ,jsizes )distances for merged cluster shape [ np inf np ones( + for in range ( )update distances [ (sizes [ ]sizes [ ])* [ ,ksizes [ ]sizes [ ])* [ ,ksizes [ ]* [ , ]/sizes [isizes [jsizes [ ]infs np inf np ones(narray of infinity [ ,:, [:, ], [ ,:, [:,jinfs ,infs ,infs ,infs deactivate new_d np inf np ones (( + , + )new_d [ : , :nd copy old matrix into new_d new_d [- ,:]new_d [- , add new row and column return new_d def agg_cluster ( ) shape [ sizes np ones(nd cdist (xxmetric 'sqeuclidean 'initialize dist matrix np fill_diagonal (dnp inf np ones( shape [ ]) np zeros (( - , )linkage matrix encodes hierarchy tree for in range ( - )