Nonmetric Grouping: Clusters and Cliques

Abstract

A class of related nonmetric (“monotone invariant”) hierarchical grouping methods is presented. The methods are defined in terms of generalized cliques, based on a systematically varying specification of the degree of indirectness of permitted relationships ( i.e. , degree of “chaining”). This approach to grouping is shown to provide a useful framework for grouping methods based on an a priori specification of the properties of the desired subsets, and includes a natural generalization for “complete linkage” and “single linkage” clustering, such as the methods of Johnson [1967]. The central feature of the class of methods is a simple iterative matrix operation on the original disparities (“inverse-proximities” or “dissimilarities”) matrix, and one of the methods also constitutes a very efficient single linkage clustering procedure.