Average linkage

There is a wide variety of hierarchical algorithms available and it is impossible to discuss all of them here. Therefore, we shall only explain the most typical ones, namely the single linkage, the complete linkage and the average linkage methods. 

Fig. 30.7. Dendrograms for the data of Tables 30.3-30.7 (a) average linkage (b) single linkage (c) complete linkage.

Successive reduced matrices for the data of Table 4 obtained by average linkage (a)... 

An example of an application is shown in Fig. 30.10. This concerns the classification of 42 solvents based on three solvatochromic parameters (parameters that describe the interaction of the solvents with solutes) [13]. Different methods were applied, among which was the average linkage method, the result of which is shown in the figure. According to the method applied, several clusterings can be found. For instance, the first cluster to split off from the majority of solvents consists of solvents 36, 37, 38, 39, 40, 41, 42 (t-butanol, isopropanol, n-butanol. 

There exist several methods of hierarchical clustering which use diverse measures of distance or similarity, respectively, e.g., single linkage, complete linkage, average linkage, centroid linkage, and Ward s method (Sharaf et al. [1986], Massart et al. [1988], Otto [1998] Danzer et al. [2001]). 

Hierarchical cluster analysis (Section 6.4)—with the result represented by a dendrogram—is a complementary, nonlinear, and widely used method for cluster analysis. The distance measure used was dTANi (Equation 6.5), and the cluster mode was average linkage. The dendrogram in Figure 6.6 (without the chemical structures) was obtained from the descriptor matrix X by... 

FIGURE 6.6 Dendrogram from hierarchical cluster analysis (average linkage) of n = 20 standard amino acids. Distance measure used was dTANi (Equation 6.5) calculated from eight binary substructure descriptors. Four structure pairs with identical descriptors merge at a distance of zero. Clustering widely corresponds to the chemist s point of view. 

Compute the distances between all clusters using complete linkage, single linkage, average linkage, or other methods. 

Similarly, a measure of heterogeneity between two clusters can be based on the maximum, minimum, or average of all pairwise distances between the objects of the two clusters (compare complete, single, and average linkage), or on the pairwise distances between the cluster centers. The latter choice results in a measure of heterogeneity /i / between cluster j and l as... 

From these results, the conformation for the GXS molecule was constructed as A2A1. Here the average linkage torsion angles for the A2 (G-X) and A (X-S) families have been used. A value of... 

Table IV i Average linkage torsion angles (in degrees) and...

Of the four different methods of cluster analysis applied, the method of Ward described in the Clustan User Manual (10), worked best when compared to the single-, complete-, or average-linkage methods. Using Ward s method, two clusters, Gn and Gm, are fused when by pooling the variance within two existing clusters the variance of the so formed clusters increases minimally. The variance or the sum of squares within the classes will be chosen as the index h of a partition. 

Fig. 9-1. Number of clusters as a function of similarity. (Cluster algorithm o average linkage, x according to WARD)...

The problem lies in the model. The Euclidean distance calculation is inappropriate for use with correlated variables because it is based only on pairwise comparisons, without regard to the elongation of data point swarms along particular axes. In effect, Euclidean distance imposes a spherical constraint on the data set (18). When correlation has been removed from the data, (by derivation of standardized characteristic vectors) Euclidean distance and average-linkage cluster analysis return the three groups. 

Science (North-Holland), Amsterdam, 1986, pp. 289-301. Divisive vs. Agglomerative Average Linkage Hierarchical Clustering. 

Other hierarchical algorithms are also known, such as that using the average linkage option. In this algorithm, the first set of clusters is done in the same way as previously described. However, the addition of the third element to a cluster considers the average distance to the elements in the previously formed cluster, and the distance between clusters is the average distance from points in the first cluster and the second cluster. 

Average linkage, the distance is defined as the mean distance between all possible pairs of entities of the two clusters, where redefines the two clusters and xsj defines the entity in cluster s and xtj in cluster t,... 

---