A Graph-Theoretic Approach to Goodness-of-Fit in Complete-Link Hierarchical Clustering

Abstract

The complete-link hierarchical clustering strategy is reinterpreted as a heuristic procedure for coloring the nodes of a graph. Using this framework, the problem of assessing goodness-of-fit in complete-link clustering is approached through the number of “extraneous” edges in the fit of the constructed partitions to a sequence of graphs obtained from the basic proximity data. Several simple numerical examples that illustrate the suggested paradigm are given and some Monte Carlo results presented.