Hierarchical partitioning algorithms

The standard hierarchical clustering algorithms produce a whole set of cluster solutions, namely a partitioning of the objects into k 1, n clusters. The partitions are ordered hierarchically, and there are two possible procedures ... 

Many hierarchical clustering algorithms are based on ultrametric partitionings of the objects. As described by Johnson (1967), an ultrametric d between clusters satisfies the usual metric conditions plus the ultrametric inequality,... 

The inputs of both the hierarchical and the partitioning algorithms are the overall dissimilarities obtained at the panel level. We will also outline strategies of analysis where the input data are the individual (i.e. subjects) dissimilarity matrices. In this strategy of analysis, the aim is to obtain what is usually referred to as a consensus partition. That is, a partition that agrees as much as possible with the partitions given by the subjects. 

Two main groups of cluster algorithms can be distinguished hierarchical or nonhier-archical (partitioning) techniques. 

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. 

Next we discuss a fuzzy hierarchical clustering procedure proposed by Dumitrescu. The procedure starts with the computation of a binary fuzzy partition A, A2] of the data set X. To do this, the FNM algorithm or other appropriate procedure may be used. If A j and A 2 do not describe real clusters, we may conjecture there is no structure in X or that the data comprise a single compact cluster. The process then ends. If the fuzzy classes A and A2 correspond to real clusters, we set = v4j,/I2. Assume the cluster structure of each class zl, / = 1,2, is given by a binary fuzzy partition of z4,. We may compute the cluster substructure of Aj using the GFNM algorithm or one of its relatives. There are now two possibilities ... 

The fuzzy hierarchical cross-classification algorithm was used to classify eight mud samples. Each sample was characterized as a vector with 23 components representing chemical analysis. The fuzzy partition tree obtained by using simultaneous classification of muds and their characteristics is shown in Fig. 8. There are six final fuzzy classes in this hierarchy. The classical partition corresponding to the final fuzzy classes of the muds is 111 Krinides Lisbori Ai 2z> Argilla Solare A 2i> Pnkolimni ... 

The fuzzy cross-classification algorithm produces both a fuzzy partition and a fuzzy partition of characteristics compatible with the former. The advantages of this algorithm include the ability to observe not only the fuzzy classes obtained and their relationship, but also the characteristics corresponding to each final class of objects. Each object class may be well described using the corresponding characteristics. These are the characteristics that have contributed to the separation of the respective fuzzy class. Fuzzy divisive hierarchical cross-classification of therapeutic muds based on their physicochemical characteristics allowed an objective interpretation of their origin and maturation and helped in their classification. It also permitted quantitative and qualitative identification of the compo-... 

Clustering problems can have numerous formulations depending on the choices for data structure, similarity/distance measure, and internal clustering criterion. This section first describes a very general formulation, then it details special cases that corresponds to two popular classes of clustering algorithms partitional and hierarchical. 

Partitioning is most appropriate when one is only interested in the subsets or clusters, while hierarchical decomposition is most applicable when one seeks to show similarity relationships between clusters. Section 2.1 formalizes the combinatorics of the partitional strategy and Section 2.2 does the same for hierarchical methods. The formulations we derive here provide the basis for the application of the simulated annealing algorithm to the underl5dng optimization problem as we show in Section 3. 

We applied three hierarchical clustering methods to the same 32 data sets used in the previous section for partitional clustering (1) simulated annealing with the criterion in equation (11) (2) simulated annealing with the criterion in equation (12) and (3) Ward s algorithm. Each method generated a separate dendrogram for each data set. 

Clustering algorithms can be classified into four major approaches hierarchical methods, partitioning-based methods, density-based methods, and grid-based methods. Here, we will focus on the hierarchical cluster approach because it is often used in the context of structure-activity analysis. Recent research has suggested that hierarchical methods perform better than the more commonly used nonhierarchical methods in separating known actives and inactives [41]. 

---