Hubert's Algorithm

The following algorithms are for generating hierarchical clusterings by the single-link and complete-link methods. When the proximity matrix contains no ties, clusterings are numbered 0, 1, ..., (n-1) and the mth clustering, Wm, contains n - m clusters.

Step 1

Set m = 0. Form the disjoint clustering with clustering number m.

Step 2a

To find the next clustering (with clustering number m + 1) by the single-link method, define the function for the pairs (r, t) of clusters in the current clustering as follows.

= min d(i,j) : the maximal subgraph of G(d(i,j) defined by is connected

Clusters and are merged to form the next clustering in the single-link hierarchy if

= min

Step 2b

The function is used to find clustering number m + 1 by the complete-link method and is defined for all pairs (r, t) of clusters in the current clustering.

= min d(i,j) : the maximal subgraph of G(d(i,j)) defined by is complete

Cluster is merged with cluster under the complete-link method if = min

Step 3

Set m = m + 1 and repeat step 2. Continue until all objects are in a single cluster.

The word "maximal" in the definitions of functions and means that all nodes of the two clusters and must be considered when establishing connectedness or completeness. Only existing clusters can be merged at the next level.