METRIC ADMISSIBILITY AND AGGLOMERATIVE CLUSTERING

A new clustering admissibility condition, metric admissibility, is introduced. This admissibility condition is important in clustering applications where it is desired that the cluster distances remain metric (satisfy the triangle inequality). The Lance and Williams infinite family of clustering algorithms is evaluated with respect to this admissibility condition. This family contains most of the commonly used agglomerative clustering algorithms. Necessary and sufficient conditions are given on the parameters of the Lance and Williams cluster distance function in order to assure metric admissibility of the corresponding algorithms.