Agglomerative Hierarchical Clustering (AHC)

What is Agglomerative Hierarchical Clustering

Agglomerative Hierarchical Clustering (AHC) is a clustering (or classification) method which has the following advantages:

• It works from the dissimilarities between the objects to be grouped together. A type of dissimilarity can be suited to the subject studied and the nature of the data.
• One of the results is the dendrogram which shows the progressive grouping of the data. It is then possible to gain an idea of a suitable number of classes into which the data can be grouped.

How does Agglomerative Hierarchical Clustering work

Agglomerative Hierarchical Clustering (AHC) is an iterative classification method whose principle is simple.

1. The process starts by calculating the dissimilarity between the N objects.
2. Then two objects which when clustered together minimize a given agglomeration criterion, are clustered together thus creating a class comprising these two objects.
3. Then the dissimilarity between this class and the N-2 other objects is calculated using the agglomeration criterion. The two objects or classes of objects whose clustering together minimizes the agglomeration criterion are then clustered together.

This process continues until all the objects have been clustered.

These successive clustering operations produce a binary clustering tree (dendrogram), whose root is the class that contains all the observations. This dendrogram represents a hierarchy of partitions. It is then possible to choose a partition by truncating the tree at a given level, the level depending upon either user-defined constraints (the user knows how many classes are to be obtained) or more objective criteria.

Agglomerative Hierarchical Clustering aggregation methods

To calculate the dissimilarity between two groups of objects A and B, different strategies are possible. XLSTAT offers the following methods:

Simple linkage: The dissimilarity between A and B is the dissimilarity between the object of A and the object of B that are the most similar. Agglomeration using simple linkage tends to contract the data space and to flatten the levels of each step in the dendrogram. As the dissimilarity between two elements of A and of B is sufficient to link A and B, this criterion can lead to very long clusters (chaining effect) while they are not homogeneous.

Complete linkage: The dissimilarity between A and B is the largest dissimilarity between an object of A and an object of B. Agglomeration using complete linkage tends to dilate the data space and to produce compact clusters.

Unweighted pair-group average linkage: The dissimilarity between A and B is the average of the dissimilarities between the objects of A and the objects of B. Agglomeration using Unweighted pair-group average linkage is a good compromise between the two preceding criteria, and provides a fair representation of the data space properties.

Weighted pair-group average linkage: The average dissimilarity between the objects of A and of B is calculated as the sum of the weighted dissimilarities, so that equal weights are assigned to both groups. As with unweighted pair-group average linkage, this criterion provides a fairly good representation of the data space properties.

Flexible linkage: This criterion uses a â parameter that varies between [-1,+1]; this can generate a family of agglomeration criteria. For â = 0 the criterion is weighted pair-group average linkage. When â is near to 1, chain- like clusters result, but as â decreases and becomes negative, more and more dilatation is obtained.

Ward’s method: This method aggregates two groups so that within-group inertia increases as little as possible to keep the clusters homogeneous. This criterion, proposed by Ward (1963), can only be used in cases with quadratic distances, i.e. cases of Euclidian distance and Chi-square distance.

Proximities used in Agglomerative Hierarchical Clustering

The proximity between two objects is measured by measuring at what point they are similar (similarity) or dissimilar (dissimilarity). If the user chooses a similarity, XLSTAT converts it into a dissimilarity as the AHC algorithm uses dissimilarities. The conversion for each object pair consists in taking the maximum similarity for all pairs and subtracting from this the similarity of the pair in question.

XLSTAT proposes several similarities/dissimilarities that are suitable for a particular type of data:

Note: For non-binary categorical variables, it is preferable to first perform a Multiple Correspondence Analysis (MCA) and to consider the coordinates of the observations on the factorial axes as new variables.

Results provided by XLSTAT for Agglomerative Hierarchical Clustering

• Node statistics: This node statistics table shows the data for the successive nodes in the dendrogram. The first node has an index which is the number of objects increased by 1. Hence it is easy to see at any time if an object or group of objects is clustered with another object or group of objects at the level of a new node in the dendrogram.
• Levels bar chart: The level bar chart table displays the statistics for dendrogram nodes.
• Dendrograms: The full dendrogram displays the progressive clustering of objects. If truncation has been requested, a broken line marks the level the truncation has been carried out. The truncated dendrogram shows the classes after truncation.
• Class centroids: This class centroids table shows the class centroids for the various descriptors.
• Distance between the class centroids: The distance between the class centroids table shows the Euclidean distances between the class centroids for the various descriptors.
• Central objects: The central objects table shows the coordinates of the nearest object to the centroid for each class.
• Distance between the central objects: This distance between the central objects table shows the Euclidean distances between the class central objects for the various descriptors.
• Results by class: The descriptive statistics for the classes (number of objects, sum of weights, within-class variance, minimum distance to the centroid, maximum distance to the centroid, mean distance to the centroid) are displayed in the first part of the table. The second part shows the objects.
• Results by object: The results by object table shows the assignment class for each object in the initial object order.