Clustering hierarchical

Hierarchical clustering is a so-called SAHN-technique (an abbreviation for sequential, gglomerative, Merarchical, n on-overlapping)  

Instead of a distance measure a similarity measure was proposed by 

The result of the clustering is usually presented in a dendogram (Figur 43). The dendogram shows the connections of pattern points and on the ordinate the actual minimum distance for each clustering step. 

Examination of a dendogram in order to separate clusters can be made in different ways either by an algorithm or by the scientist. 

The desired number of clusters can be specified and the dendogram shows the composition of the clusters. 

Hierarchical clustering methods produce small clusters of very similar molecules nested within successively larger clusters of less similar molecules. Visualization of the resultant hierarchy remains an unsolved problem for databases of more than a few hundred molecules. 

All of the SAHN methods can be implemented using a standard stored matrix approach, in which an initial intermolecule similarity matrix is progressively updated as new clusters are formed by the fusion of pairs of molecules and/or clusters molecules. The intercluster similarities are calculated using the Lance—Williams matrix-update formula  

The following example shows how R can be used to carry out a clustering analysis using data stored in an RDBMS. 

The SQL statement above computes the Tanimoto similarity between all pairs of compounds using fingerprint bitstrings stored in the column gfp. The tanimoto function is described in Chapter 8 and shown in the Appendix. This SQL statement uses the Case conditional clause. This is done in order to avoid computing elements unnecessarily. The matrix of similarities is symmetric and the diagonal elements are exactly 1. The sqlQuery R function reads the rows of the similarity matrix into an R data.frame named tani. This is coerced into a matrix of the correct number of rows and columns using the matrix function and further coerced into a distance R object. The R distance object is the lower half of a symmetric distance matrix. Since the tanimoto similarity is used, the distance (or dissimilarity) is represented by 1.0 minus the tanimoto 

Several other statistical tools based on linear and nonlinear methods have been used to analyze array data, including self-organizing maps, k-means clustering, and principal component analysis (Tamayo et al., 1999 Ben-Dor et al., 1999). Each of these tools has merit, and software for some of these is publicly available. However, 

---

As oversimplified cases of the criterion to be used for the clustering of datasets, we may consider some high-quality Kohonen maps, or PCA plots, or hierarchical clustering. 

In a typical appHcation of hierarchical cluster analysis, measurements are made on the samples and used to calculate interpoint distances using an appropriate distance metric. The general distance, is given by... 

Dubois M, Plaisance H, Thome JP, et al. 1996. Hierarchical cluster analysis of environmental pollutants through P450 induction in cultured hepatic cells. Ecotoxicol Environ Saf 34 205-215. 

Figure 8.5 Example dendrogram representing an hierarchical clustering of a set of seven compounds.

Willett P, Winterman V, Bawden DJ. Implementation of non hierarchical cluster-analysis methods in chemical information-systems-selection of compounds for biological testing and clustering of substructure search output. Chem Inf Comp Sci 1986 26 109-18. 

Similarity clustering implies an automated generalization of increments using a similarity hierarchical clustering procedure, followed by the optimization of the generic increments. This procedure combines the advantages of both the constructionist and reductionist approaches, and is a central method in AB/LogP. 

A list of clusterings derived from Fig. 30.1 by non-hierarchical clustering... 

In hierarchical clustering one can obtain any number of clusters K,lhierarchical method MASLOC [27], which selects so-called robust clusters. 

D. L. Massart, L. Kaufman and K.H. Esbensen, Hierarchical non-hierarchical clustering strategy and application to classification of iron-meteorites according to their trace element patterns. Anal. Chem., 54 (1982) 911-917. 

I. Bondarenko, H. Van Malderen, B. Treiger, P. Van Espen and R. Van Grieken, Hierarchical cluster analysis with stopping rules built on Akaike s information criterion for aerosol particle classification based on electron probe X-ray microanalysis. Chemom. Intell. Lab. Syst., 22 (1994) 87-95. 

D.L. Massart, F. Plastria and L. Kaufman, Non-hierarchical clustering with MASLOC. Pattern... 

Several, but not all, of these mathematical methods (e.g. multicriteria decision making. Chapter 26) or problems (the non-hierarchical clustering methods of Chapter 30, which can be treated as allocation models) have been treated earlier. In this chapter, we will briefly discuss the methods that are relevant to chemo-metricians and have not been treated in earlier chapters yet. 

Unlike the simulations which only consider particle-cluster interactions discussed earlier, hierarchical cluster-cluster aggregation (HCCA) allows for the formation of clusters from two clusters of the same size. Clusters formed by this method are not as dense as clusters formed by particle-cluster simulations, because a cluster cannot penetrate into another cluster as far as a single particle can (Fig. 37). The fractal dimension of HCCA clusters varies from 2.0 to 2.3 depending on the model used to generate the structure DLA, RLA, or LTA. For additional details, the reader may consult Meakin (1988). 

Fig. 37. Typical clusters obtained by diffusion-limited aggregation (DLA). Top Two-dimensional diffusion-limited aggregation. Bottom Reaction-limited hierarchical cluster-cluster aggregation (HCCA) (Meakin, 1988 with permission, from the Annual Review of Physical Chemistry, Vol. 39. by Annual Reviews www.Annual/Reviews.org).

Two examples of unsupervised classical pattern recognition methods are hierarchical cluster analysis (HCA) and principal components analysis (PCA). Unsupervised methods attempt to discover natural clusters within data sets. Both HCA and PCA cluster data. 

Fig. 8.7. Schematic representation of hierarchical clustering of the 14 objects shown in Fig. 8.6 the separation lines a and b corresponds to the clusters in 8.6a,b...

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

Non-hierarchical cluster methods have in common with classification methods that pre-information on the number of classes is needed or desired to start an iteration process. In the course of the clustering a rearrangement of objects between several clusters is possible. 

One of the most used techniques of non-hierarchical cluster analysis is the density method (potential method). The high density of objects in the m-dimension that characterizes clusters is estimated by means of a density function (potential function) P. For this, the objects are modelled by Gaus-... 

---