Agglomerative clustering

The hierarchical methods so far discussed are called agglomerative. Good results can also be obtained with hierarchical divisive methods, i.e., methods that first divide the set of all objects in two so that two clusters result. Then each cluster is again divided in two, etc., until all objects are separated. These methods also lead to a hierarchy. They present certain computational advantages [21,22]. 

Fig. 30.13. Agglomerative methods will first link A and B, so that meaningless clusters may result. The non-hierarchical K=2 clustering will yield clusters I and II.

Blashfield, R. K. (1976). Mixture model tests of cluster analysis Accuracy of four agglomerative hierarchical methods. Psychological Bulletin, 83, 377-388. 

Agglomerative methods In the first level of the hierarchy, each of the n objects forms a separate cluster, resulting in n clusters. In the next level the two closest clusters are merged, and so on, until finally all objects are in one single cluster. 

Coming back to agglomerative clustering, we can now outline an algorithm ... 

There are two main types of clustering techniques hierarchical and nonhierarchical. Hierarchical cluster analysis may follow either an agglomerative or a divisive scheme agglomerative techniques start with as many clusters as objects and, by means of repeated similarity-based fusion steps, they reach a final situation with a unique cluster containing all of the objects. Divisive methods follow exactly the opposite procedure they start from an all-inclusive cluster and then perform a number of consecutive partitions until there is a bijective correspondence between clusters and objects (see Fig. 2.12). In both cases, the number of clusters is defined by the similarity level selected. 

FIGURE 2.12 Scheme of agglomerative and divisive clustering approaches illustrated with five objects described by two variables. 

Cluster analysis (CA) performs agglomerative hierarchical clustering of objects based on distance measures of dissimilarity or similarity. The hierarchy of clusters can be represented by a binary tree, called a dendrogram. A final partition, i.e. the cluster assignment of each object, is obtained by cutting the tree at a specified level [24],... 

As indicated, agglomerative methods start with single objects or pairs of objects step by step clusters are formed which are finally united in one cluster. Divisive methods, on the other hand, start from the one cluster of all objects and divide it step by step. One drawback of the commonly used agglomerative methods is that clusters formed may not be broken up in a subsequent step. With certain algorithms this sometimes leads to so-called inversions in the dendrogram, i.e. crossing lines in the diagram. 

Further details of agglomerative, and several other clustering strategies may be found in the book by MASSART and KAUFMAN [1983] or, along with remarks on the treatment of situations with missing values, in the monograph by MUCHA [1992]. Finally, it may be of interest that OZAWA [1983] even proposed a hierarchical cluster algorithm based on an asymmetric distance matrix. 

The principle of unsupervised learning consists in the partition of a data set into small groups to reflect, in advance, unknown groupings [YARMUZA, 1980] (see also Section 5.3). The results of the application of methods of hierarchical agglomerative cluster analysis (see also [HENRION et al., 1987]) were representative of the large palette of mathematical algorithms in cluster analysis. 

Results from hierarchical agglomerative cluster analysis according to the algorithm of WARD (see Section 5.3) are illustrated as a dendrogram in Fig. 7-14. Distinction of the months in which the heating of buildings has a large influence from the summer months is clearly demonstrated. November and December of the second year of the in-... 

Fig. 7-14. Dendrogram of the hierarchical agglomerative cluster analysis according to WARD...

The data matrix is subjected to hierarchical agglomerative cluster analysis (CA for the mathematical fundamentals see Section 5.3 further presentation of the algorithms is given by [HENRION et al., 1987]) in order to find out whether territorial structures with different multivariate patterns of heavy metals exist within the test area. 

The most commonly used procedures in environmental studies are clustering performed using hierarchical agglomerative procedures because of the comprehensible graphical output and clear hierarchical relations between clusters.2,3... 

---