Theory

Cluster Analysis groups data objects based only on information found in data that describes the objects and their relationships. The goal is that the objects within a group be similar to one another and different from the objects in other groups. The greater the similarity in a group and greater the difference between groups, the better or more distinct is the clustering.

There are 2 main types of clustering-Hierarchical and Non-hierarchical.

Hierarchical Clustering : This is based on the core idea of objects being more related to nearby objects than to objects farther away. As such, these algorithms connect "objects" to form "clusters" based on their distance. A cluster can be described largely by the maximum distance needed to connect parts of the cluster. At different distances, different clusters will form, which can be represented using a dendrogram, which explains where the common name "hierarchical clustering" comes from: these algorithms do not provide a single partitioning of the data set, but instead provide an extensive hierarchy of clusters that merge with each other at certain distances. In a dendrogram, the y-axis marks the distance at which the clusters merge, while the objects are placed along the x-axis such that the clusters don't mix.

A hierarchical clustering method produces a classification in which small clusters of very similar molecules are nested within larger clusters of less closely-related molecules.

Hierarchical agglomerative methods generate a classification in a bottom-up manner, by a series of agglomerations in which small clusters, initially containing individual molecules, are fused together to form progressively larger clusters. Hierarchical agglomerative methods are often characterized by the shape of the clusters they tend to find, as exemplified by the following range:

Ø  Single-link - tends to find long, straggly, chained clusters;

Ø  Ward and group-average - tend to find globular clusters;

Ø  Complete-link - tends to find extremely compact clusters.

Hierarchical divisive methods generate a classification in a top-down manner, by progressively sub-dividing the single cluster which represents an entire dataset. Monothetic (divisions based on just a single descriptor) hierarchical divisive methods are generally much faster in operation than the corresponding Polythetic (divisions based on all descriptors) hierarchical divisive and hierarchical agglomerative methods, but tend to give poor results.

Hierarchical methods tend to be very demanding of computational resources, typically  to  for N compounds, since a complete hierarchy of partitions has to be built-up rather than just a single partition.

One problem with these methods is how to choose which clusters or partitions to extract from the hierarchy since display of the full hierarchy is not really appropriate for datasets of more than a few hundred compounds.

Non-hierarchical Clustering : A non-hierarchical method generates a classification by partitioning a dataset, giving a set of (generally) non-overlapping groups having no hierarchical relationships between them. A systematic evaluation of all possible partitions is quite infeasible, and many different heuristics have thus been described to allow the identification of good, but possibly sub-optimal, partitions.

Non-hierarchical methods are generally much less demanding of computational resources than the hierarchic methods, since only a single partition of the dataset has to be formed.

Three of the main categories of non-hierarchical method are single-pass, relocation and nearest neighbor :

Ø  Single-pass methods (e.g. Leader) produce clusters that are dependent upon the order in which the compounds are processed, and so will not be considered further;

Ø  Relocation methods, such as k-means, assign compounds to a user-defined number of seed clusters and then iteratively reassign compounds to see if better clusters result. Such methods are prone to reaching local optima rather than a global optimum, and it is generally not possible to determine when or whether the global optimum solution has been reached;

Ø  Nearest neighbor methods, such as the Jarvis-Patrick method, assign compounds to the same cluster as some number of their nearest neighbors. User-defined parameters determine how many nearest neighbors need to be considered, and the necessary level of similarity between nearest neighbor lists.

Other non-hierarchical methods are generally inappropriate for use on large, high-dimensional datasets such as those used in chemical applications.