Model selection for minimum-diameter partitioning

The minimum-diameter partitioning problem (MDPP) seeks to produce compact clusters, as measured by an overall goodness-of-fit measure known as the partition diameter, which represents the maximum dissimilarity between any two objects placed in the same cluster. Complete-linkage hierarchical clustering is perhaps the best-known heuristic method for the MDPP and has an extensive history of applications in psychological research. Unfortunately, this method has several inherent shortcomings that impede the model selection process, such as: (1) sensitivity to the input order of the objects, (2) failure to obtain a globally optimal minimum-diameter partition when cutting the tree at K clusters, and (3) the propensity for a large number of alternative minimum-diameter partitions for a given K. We propose that each of these problems can be addressed by applying an algorithm that finds all of the minimum-diameter partitions for different values of K. Model selection is then facilitated by considering, for each value of K, the reduction in the partition diameter, the number of alternative optima, and the partition agreement among the alternative optima. Using five examples from the empirical literature, we show the practical value of the proposed process for facilitating model selection for the MDPP.