Agglomerative Algorithm for Complete-Link Clustering

Step 1

Begin with the disjoint clustering implied by threshold graph G(0), which contains no edges and which places every object in a unique cluster, as the current clustering. Set k = 1.

Step 2

From threshold graph G(k).

If two of the current clusters form a clique (maximally complete subgraph) in G(k), redefine the current clustering by merging these two clusters into a single cluster

Step 3

If k = n(n - 1)/2, so that G(k) is the complete graph on the n nodes, stop. Else, set k = k + 1 and go to step 2.

The single-link clustering on G(v) is defined in terms of connected subgraphs in G(v); the complete-link clustering uses complete subgraphs.

The following figure exhibits the single-link and complete-link hierarchical clusterings for the proximity matrix D1

  
Figure 4: Threshold graphs and dendograms

The entire single-link hierarchy is defined by the first four threshold graphs in the figure. However, the first seven threshold graphs are needed to determine the complete-link hierarchy.

Once the two-cluster complete-link clustering has been obtained, no more explicit threshold graphs need be drawn because the two clusters will merge into the conjoint clustering only when all n(n - 1)/2 edges have been inserted.

This example demonstrates the significance of nesting in the hierarchy. Objects form a clique, or maximally complete subgraph, in threshold graph G(5), but the three objects are not a complete-link cluster. Once complete-link clusters and have been established, object must merge with one of the two established clusters;

Once formed, clusters cannot be dissolved and clusters cannot overlap.