Nonhierarchical clustering

P Willett, V Wmterman, D Bawden. Implementation of nonhierarchic cluster analysis methods m chemical information systems Selection of compounds for biological testing and clustering of substiaictures search output. I Chem Inf Comput Sci 26 109-118, 1986. 

There are three steps to nonhierarchical cluster analysis. The first is to dioose seedpoints these are approximate points compositions from which to start cluster analysis. Choosing seedpoints is by far the most critical step. Secondly, a cluster-analysis algorithm is applied to define the clusters. Finally, the statistical significance of the clusters must be determined. In other words, are the clusters well resolved or do they overlap The three steps are detailed below. 

Willett, P., Winterman, V., and Bawden, D. (1986) Implementation of nonhierarchic cluster analysis methods in chemical information systems selection of compounds for bilogical testing and clustering of substructures search output. J. Chem. Inf. Comput. Sci. 26, 109-118. 

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. 

Examples of nonhierarchical clustering [22] methods include Gaussian mixture models, means, and fuzzy C means. They can be subdivided into hard and soft clustering methods. Hard classification methods such as means assign pixels to membership of only one cluster whereas soft classifications such as fuzzy C means assign degrees of fractional membership in each cluster. 

The aim of classification by nonhierarchical clustering is to classify the objects under consideration into a certain number of preliminary intended clusters. The clusters are formed simultaneously by partitioning methods, which allow the objects to be rearranged between the clusters. The main disadvantage of nonhierarchical clustering is the absence of a graphical output. 

The trained map can be graphically presented by 2D planes for each variable, with the variable distribution values being indicated by different colors on the different regions of the map. Additionally, the node coordinates (vectors) can be clustered by the nonhierarchical A -means classification algorithm. 

Grouping. The most commonly employed techniques of data analysis in compositional investigations are those that seek to partition a data set into smaller groups that contain samples that are more similar to others in the group than to other samples in the data set. Cluster analysis, including both hierarchical and nonhierarchical variants, encompasses virtually the full range of grouping procedures used in compositional data analysis. 

A basic question of whether hierarchical or nonhierarchical cluster analysis is used deals with the correct or best number of groups in a data set. The notion of best relates not only to a criterion value or large break in a dendrogram, but to the research objectives as well. We can not resist quoting from Everitt (48) what is probably the ultimate word regarding the number of groups ... 

To scan the nearest-neighbor lists and create the clusters in this stage of nonhierarchical clustering, the following three steps are carried out ... 

Implementation of Nonhierarchic Cluster-Analysis Methods in Chemical Information Systems Selection of Compounds for Biological Testing and Clustering of Substructure Search Output. 

Figure 5.16 Clustering selection methods nonhierarchical approaches.

The 83 organic solvents have been grouped into nine classes from the clustering of their principal component values, using a nonhierarchical multivariate taxonomy to progressively classify solvents by means of the discriminating power of the eight descriptors [cf. Fig. 3-6). 

Cluster-Based Methods. Clustering methods have a long history of application in chemical information (60). Any set of descriptors can be used in the clustering, but most typically some form of structural fingerprint is used in conjunction with a similarity measure such as the Tanimoto coefficient (see Section 2.1.4.1). The methods fall into two broad classes, hierarchical and nonhierarchical. 

---