Spanning Tree Clustering

FIGURE 44. Clustering by a minimal spanning tree. The tree is broken into clusters by cutting all segments that are longer than a predetermined value. 

The problem to find the shortest path through a set of points can be formulated as the travelling salesman problem . Suppose a salesman has to visit customers in several towns and he looks for the shortest way through all towns. An exact description of the problem and the solution requires some knowledge in graph theory C189, 240, 386, 4083. 

The calculation is very laborious for more than 100 patterns. 

For cluster analysis also simpler algorithms were proposed which find a short but not necessarily the shortest spanning tree C2683. 

Various methods are possible to break the minimal spanning tree into clusters C240, 4083. In one of the methods all line segments are cutted that are longer than a length supplied by the researcher. This method is particularly effective in the detection of outlying patterns. 

---

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. 

A very different approach to characterize clustering tendency is based on the frequency distributions of the lengths of the edges in the minimum spanning tree connecting the objects in the real data and in uniformly distributed data (Forina et al. 2001). 

The minimal spanning tree also operates on the distance matrix. Here, near by patterns are connected with lines in such a way that the sum of the connecting lines is minimal and no closed loops are constructed. Here too the information on distances is retained, but the mutual orientation of patterns is omitted. Both methods, hierarchical clustering and minimal spanning tree, aim for making clusters in the multi-dimensional space visible on a plane. 

Unsupervised learning methods - cluster analysis - display methods - nonlinear mapping (NLM) - minimal spanning tree (MST) - principal components analysis (PCA) Finding structures/similarities (groups, classes) in the data... 

Graphical methods in connection with pattern recognition algorithms, i.e. geometrical or statistical methods, e.g. minimum spanning tree or cluster analysis, are more powerful methods for explorative data analysis than graphical methods alone. 

In this passage we demonstrate that comparable results may also be obtained when other methods of unsupervised learning, e.g. the non-hierarchical cluster algorithm CLUPOT [COOMANS and MASSART, 1981] or the procedure of the computation of the minimal spanning tree [LEBART et al., 1984], which is similar to the cluster analysis, are applied to the environmental data shown above. 

Purely numerical methods such as hierarchical clustering or the minimal spanning tree compute the similarity of molecules directly in the high-dimensional descriptor space. The results promise higher accuracy (no mapping errors), but their interpretation is less intuitive. 

Figs. 22 and 23 show the results of these calculations. The grouping does not depend mainly on the method used. Selective and nonselective COX inhibitors are well separated on the nonlinear map. Hierarchical clustering analyses form a single branch for the selective group of molecules, and also in the visualization of the minimal spanning tree compounds are lined up in the same way. 

Fig. 23 Classification of the NSAID dataset based on three-dimensional autocorrelation descriptors, a) Hierarchical clustering analysis (HCA). The dark gray cluster includes the COX-2-selective drugs, b) Visualization of the minimal spanning tree (MST). The longest connections are drawn as dotted lines in order to derive classes of compounds.

The use of hierarchical cluster analysis leading to the construction of dendrograms and minimum spanning trees for data sets where the samples analyzed have... 

Generally, useful techniques for finding clusters are "hierarchical clustering" (Chapter 7.2) and "minimal spanning tree" (Chapter 7.3). 

Gower, J.C. and Ross, GJ.S. (1969) Minimum spanning trees and single linkage cluster analysis... 

Fig. 5 Minimum spanning tree (MST) for the theoretical descriptions of the sodium tetramer and subsequent clustering with a distance threshold D-y = 0.4.

Percolation theory describes [32] the random growth of molecular clusters on a d-dimensional lattice. It was suggested to possibly give a better description of gelation than the classical statistical methods (which in fact are equivalent to percolation on a Bethe lattice or Caley tree, Fig. 7a) since the mean-field assumptions (unlimited mobility and accessibility of all groups) are avoided [16,33]. In contrast, immobility of all clusters is implied, which is unrealistic because of the translational diffusion of small clusters. An important fundamental feature of percolation is the existence of a critical value pc of p (bond formation probability in random bond percolation) beyond which the probability of finding a percolating cluster, i.e. a cluster which spans the whole sample, is non-zero. 

Linear regression analysis has pitfalls. There is always the possibility of chance correlations. Hence, we opted to analyze the data using an alternate statistical method, namely cluster analysis. The data were scaled so that each of the descriptors ranged in value between 0 and 1. Minimal tree spanning methods was employed in the determination of clusters (24). 

---