Approximate Evaluation Techniques for the Single-Link and Complete-Link Hierarchical Clustering Procedures

Abstract A technique is presented for testing the hypothesis that a hierarchical sequence of partitions constructed by the single-link or complete-link clustering method could have been obtained because of "noise." Two rank orderings of the object pairs are compared. One of the orderings is obtained from the initial proximity values; the second is derived from the levels at which an object pair first appears within a single subset within the hierarchy. The hypothesis that the given set of proximity values have been assigned randomly is tested by referring the Goodman-Kruskal rank correlation y statistic to an approximate permutation distribution.