Agglomerative cluster analysis methods

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. 

One of the cluster analysis methods is the agglomerative method (Everitt et al. 2001). Using this approach, a distance threshold parameter is continuously increased. At the first step, the two nearest objects are identified, and at this stage, only their distance is below the threshold. These two objects are xmited and the location of the unified object is the arithmetic mean of the coordinates. By increasing the threshold further and further, objects are united until only one object remains. The similarity of the objects is indicated by the order of the aggregations. 

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

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. 

The outcome of agglomerative hierarchical cluster analysis is a crisp cluster membership function, which can take only the values 0 (no membership) or 1 (membership). Other non-hierarchical clustering techniques such as k-means cluster (KMC) analysis still follow this concept, whereas fuzzy C-means (FCM) clustering returns fuzzy class memberships. The latter method thus departs from the classical (0 or 1) two-valued logic and uses soft linguistic system variables, i.e. degrees of class membership values varying between 0 and 1. 

One of the most intuitive ways to describe how cluster analysis works in practice is by referring to the agglomerative hierarchical cluster analysis (HCA) method. Beside the common preliminary steps already discussed, that is definition of the metric (Euclidean, Mahalanobis, Manhattan distance, etc.) and calculation of the distance matrix and the corresponding similarity matrix, the analysis continues according to a recursive procedure such as... 

Agglomerative hierarchical clustering is one of the most utilized clustering methods for the analysis of biological data (Quackenbush, 2001 D Haeseleer,... 

---