Hierarchical cluster analysis

The main idea...

Hierarchical cluster analysis is an algorithmic approach to find discrete groups with varying degrees of (dis)similarity in a data set represented by a (dis)similarity matrix. These groups are hierarchically organised as the algorithms proceed and may be presented as a dendrogram (Figure 1). Many of these algorithms are greedy (i.e. the optimal local solution is always taken in the hope of finding an optimal global solution) and heuristic, requiring the results of cluster analysis to be evaluated for stability by, for example, bootstrapping procedures.

In ecological analyses, hierarchical clustering may be useful in discretising largely continuous ecological phenomena to aid structure detection and hypothesis generation. If data were collected along a gradient, for example, cluster analysis may help to identify (relatively) distinct regions therein which may correspond to an ecologically meaningful grouping. As always, one must consider carefully whether clustering is suitable and meaningful for the task at hand. If a very smooth response gradient (i.e. very even changes in (dis)similarity between objects) is being scrutinised, ordination procedures may be more appropriate. For further discussion, see Legendre and Legendre (1998).

Figure 1: Schematics of dendrograms representing the results of hierarchical cluster analyses. The position of branch points along a similarity axis indicate the level of shared similarity between clusters and/or individual entitites. These points indicate at what stage clusters were formed during the course of the chosen algorithm. In panel (b), there is evidence of "chaining", or sequential joining of individual entities.

Clustering methods

Agglomerative clustering is a widespread approach to cluster analysis. Agglomerative algorithms successively merge individual entities and clusters that have the highest similarity values. These typically use a linkage criterion (examples below and in Figure 2) to determine the (dis)similarity values for clusters formed during the algorithm's execution. These are valid both for the clustering of objects and of variables provided some measure of (dis)similarity; however, note other clustering techniques may not share this flexibility. Agglomerative algorithms end when all the individual entities and clusters have been merged into a single cluster. Below some common linkage criteria are summarised. 

Figure 2: Examples of rules employed by hierarchical clustering algorithms to create new clusters. a) Single-linkage or nearest-neighbour clustering merges clusters based on the (dis)similarities between their nearest members. b) Complete or farthest-neighbour clustering takes into account the dissimilarities between the most distant members of a cluster. c) Average-linkage clustering, also called the unweighted pair-group method using arithmetic averages (UPGMA), defines the (dis)similarity between clusters as the average pair-wise distance between all their members. Other methods of clustering are available including those which cluster based on minimising information loss on merging clusters (e.g. Ward's method) or probabilistic measures evaluating cluster membership with reference to statistical distributions (e.g. V-type clustering) as well as fuzzy clustering approaches which allow for more relaxed group membership.

Warnings

Walkthroughs featuring canonical correspondence analysis

Implementations

MASAME hierarchical clustering app

    Click here to launch...

References