Hierarchical methods

The most commonly implemented hierarchical clustering methods are those belonging to the family of sequential agglomerative hierarchical nonoverlapping (SAHN) methods. These are traditionally implemented using 

Calculate the initial proximity matrix containing the pairwise proximities between all pairs of clusters (singletons) in the data set. 

Scan the matrix to find the most similar pair of clusters, and merge them into a new cluster (thus replacing the original pair). 

Update the proximity matrix by inactivating one set of entries of the original pair and updating the other set (now representing the new cluster) with the proximities between the new cluster and all other clusters. 

Repeat steps 2 and 3 until just one cluster remains. 

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. 

Similarity matrix (based on Euclidean distance) for the objects from Table 30.3 

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

The last step consists in the junction of A and D. The resulting dendrogram is given in Fig. 30.7(a). 

The term proximity is used here to include similarity and dissimilarity coefficients in addition to distance measures. Individual proximity measures are not defined in this review full definitions can be found in standard texts and in the articles by Barnard, Downs, and Willett.23,24 We now define the terms centroid and square-error, because they will be used throughout this chapter. For a cluster of s compounds each represented by a vector, let x(r) be the rth vector. The vector of the cluster centroid, x(c), is then defined as 

Note that the centroid is the simple arithmetic mean of the vectors of the cluster members, and this mean is frequently used to represent the cluster as a whole. In situations where a mean is not applicable or appropriate, the median can be used to define the cluster medoid (see Kaufman and Rousseeuw2 for details). The square-error (also called the within-cluster variance], e2, for a cluster is the sum of squared Euclidean distances to the centroid or medoid for all s items in that cluster  

The square-error across all K clusters in a partition is the sum of the square-errors for each of the K clusters. (Note also that the standard deviation would be the square root of the square-error.) 

This chapter concentrates on the classical clustering methods, because they are the methods that have been applied most often in the chemical community. Standard reference works devoted to clustering algorithms include those by Hartigan,26 Murtagh,27 and Jain and Dubes.28 

---

A fourth hierarchical method that is quite popular is Ward s method [Ward 1963]. This method merges those two clusters whose fusion minimises the information toss due to the fusion. Information loss is defined in terms of a function rvhich fdr each cluster i corresponds to the total sum of squared deviations from the mean of the cluster ... 

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]. 

Hierarchical methods are preferred when a visual representation of the clustering is wanted. When the number of objects is not too large, one may even compute a clustering by hand using the minimum spanning tree. 

An advantage of non-hierarchical methods compared to hierarchical methods is that one is not bound by earlier decisions. A simple example of how disastrous this can be is given in Fig. 30.13 where an agglomerative hierarchical method would start by linking A and B. On the other hand, the agglomerative methods allow better visualization, although some visualization methods (e.g. Ref. [28]) have been proposed for non-hierarchical methods. 

In hierarchical clustering one can obtain any number of clusters K,lhierarchical clustering, with the difference that there K is defined a priori by the user. The question then arises which A -clustering is significant. To introduce the problem let us first consider a technique that was proposed for the non-hierarchical method MASLOC [27], which selects so-called robust clusters. 

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

Basically the perturbative techniques can be grouped into two classes time-local (TL) and time-nonlocal (TNL) techniques, based on the Nakajima-Zwanzig or the Hashitsume-Shibata-Takahashi identity, respectively. Within the TL methods the QME of the relevant system depends only on the actual state of the system, whereas within the TNL methods the QME also depends on the past evolution of the system. This chapter concentrates on the TL formalism but also shows comparisons between TL and TNL QMEs. An important way how to go beyond second-order in perturbation theory is the so-called hierarchical approach by Tanimura, Kubo, Shao, Yan and others [18-26], The hierarchical method originally developed by Tanimura and Kubo [18] (see also the review in Ref. [26]) is based on the path integral technique for treating a reduced system coupled to a thermal bath of harmonic oscillators. Most interestingly, Ishizaki and Tanimura [27] recently showed that for a quadratic potential the second-order TL approximation coincides with the exact result. Numerically a hint in this direction was already visible in simulations for individual and coupled damped harmonic oscillators [28]. 

For hierarchical methods there is a formula of LANCE and WILLIAMS [STEINHAU-SEN and LANGER, 1977] which helps the adjustment of certain parameters for some control of the result. 

One effective hierarchical method for multiscale bridging is the use of thermodynamically constrained internal state variables (IS Vs) that can be physically based upon microstructure-property relations. It is a top-down approach, meaning the IS Vs exist at the macroscale but reach down to various subscales to receive pertinent information. The ISV theory owes much of its development to the state variable thermodynamics constructed by Helmholtz [4] and Maxwell [5]. The notion of ISV was introduced into thermodynamics by Onsager [6, 7] and was applied to continuum mechanics by Eckart [8, 9]. 

---