Hierarchical Cluster Analysis

AbstractHierarchicalcluster analysisrefers to a collection of methods that seek to construct a hierarchically arranged sequence of partitions for some given object set. Typically, the methods produce a hierarchy based on some proximity measure defined for every pair of objects. The common agglomerative methods for producing partition hierarchies are discussed along with the characterizing notion of an ultrametric. The hierarchical clustering task is then redefined as one of finding a least‐squares approximation to the proximity measure by an ultrametric structure. A generalization of the ultrametric condition, and thus of hierarchical clustering, is to an additive tree; again, a least‐squares approximation to the proximity measure is sought but now by a structure that satisfies the more general additive tree inequality. Finally, a discussion is given as to how an additive tree explicitly generalizes an ultrametric by being nonuniquely decomposable by an ultrametric plus what might be called a centroid metric.