Hierarchical clustering algorithms and the various linkages
Basic principle
Given N objects to be clustered and an N*N distance matrix (or similarity matrix), the basic steps of hierarchical clustering (see S.C. Johnson in 1967) are as follows:
Assign each object to its own cluster, giving N clusters, each containing just one object. The distance between clusters is the distance between the objects they contain.Find the two closest clusters and merge them into one, so the total number of clusters decreases by one.Recompute the distances between the new cluster and all the old clusters.Repeat steps 2 and 3 until everything has been merged into a single cluster (containing all N objects).Depending on how step 3 is done, hierarchical clustering methods can be divided into several types: single-linkage, complete-linkage and average-linkage clustering, among others.
Single-linkage clustering (also called the connectedness or minimum method):
The distance between clusters equals the minimum distance between objects in the two clusters; if similarity is used instead, it is the maximum similarity between any object in one cluster and any object in the other.
Complete-linkage clustering (also called the diameter or maximum method):
The distance between groups equals the maximum distance between objects in the two groups.
Average-linkage clustering:
The distance between groups equals the average distance between objects in the two groups.
A variant of average-link clustering is R. D’Andrade's (1978) UCLUS method, which uses the median distance; it is somewhat more robust than the average distance to the influence of outlying data objects.
This kind of hierarchical clustering is called the “agglomerative” method, because it iteratively merges all the clusters. There is also a “divisive” hierarchical clustering method, which works the other way round: it first puts all objects in a single cluster and keeps splitting it into smaller clusters. The divisive method is rarely used.
The whole clustering process actually builds a tree. During construction, a threshold can be set in step 2: when the distance between the two closest clusters exceeds this threshold, the iteration can stop. The other key step is step 3; there are quite a few ways to measure the similarity between two clusters. Three are introduced here:
SingleLinkage: also called nearest-neighbor. It takes the distance between the two closest samples of the two clusters as the distance between the two sets; in other words, the smaller the distance between the two closest samples, the greater the similarity between the two clusters. It tends to cause what is called the Chaining effect: two clusters that are clearly far apart “overall” get merged just because a few of their points are close together, and after such a merge the chaining effect grows further, eventually producing rather loose clusters.
CompleteLinkage: this is the exact opposite extreme of Single Linkage. It takes the distance between the two farthest points of the two sets as the distance between them. Its effect is also the opposite: it is very restrictive. Even if two clusters are already very close, as long as there are uncooperative points, it stubbornly refuses to merge them, which is not a great approach either. The common problem with both of these similarity definitions is that they only consider certain particular data points and ignore the overall characteristics of the data within each cluster.
Average-linkage: this method takes the pairwise distances between all points in the two sets and averages them, which gives relatively more reasonable results.
A variant of average-linkage takes the median of the pairwise distances, which, compared with the mean, does a better job of removing the interference of individual outlying samples.