Cluster Analysis, 5th Edition

Chapter 4

Hierarchical Clustering

4.1 Introduction

In a hierarchical classification the data are not partitioned into a particular number of classes or clusters at a single step. Instead the classification consists of a series of partitions, which may run from a single cluster containing all individuals, to n clusters each containing a single individual. Hierarchical clustering techniques may be subdivided into agglomerative methods, which proceed by a series of successive fusions of the n individuals into groups, and divisive methods, which separate the n individuals successively into finer groupings. Both types of hierarchical clustering can be viewed as attempting to find the optimal step, in some defined sense (see later), at each stage in the progressive subdivision or synthesis of the data, and each operates on a proximity matrix of some kind (see Chapter 3). A useful review of the standard methods has been given by Gordon (1987).

With hierarchical methods, divisions or fusions, once made, are irrevocable so that when an agglomerative algorithm has joined two individuals they cannot subsequently be separated, and when a divisive algorithm has made a split it cannot be undone. As Kaufman and Rousseeuw (1990) colourfully comment: ‘A hierarchical method suffers from the defect that it can never repair what was done in previous steps’. Hawkins et al. (1982) illustrate the problem in the following way. Suppose a single variable is measured on eight objects, giving the results ...