Hierarchical Clustering Algorithms

Hierarchical clustering is a family of unsupervised grouping algorithms that build nested clusters, successively merging or splitting them, and represent the result as a tree called a dendrogram. Unlike other methods, it does not produce a single partition but a whole hierarchy: at the root, one cluster gathering all the data; at the leaves, each data point on its own.

Agglomerative and divisive

There are two ways to build that hierarchy. The agglomerative approach (bottom-up) starts with each observation as its own cluster and, at each step, merges the two most similar ones; it is the most common. The divisive approach (top-down) does the opposite: it begins with everything in a single cluster and splits it progressively. In both cases, the process generates a sequence of nested groupings.

The dendrogram

The dendrogram is the tree-shaped diagram that shows in what order and at what distance the clusters were joined: the height of each branch indicates the distance at which the merge occurred. Its great usefulness is that it allows you to choose the number of groups after the fact: you simply “cut” the tree at a given height to obtain as many clusters as there are branches below the cut.

The linkage criteria

The key to the method is how the distance between two clusters is measured, the linkage criterion. Single linkage uses the distance between their closest points and tends to form elongated chains. Complete linkage uses the distance between the farthest points and produces compact groups. Average linkage is a middle ground. And Ward's method (Joe Ward, 1963) merges the clusters that least increase the internal variance, with an objective related to that of k-means; it yields spherical, regularly sized groups.

Advantages and limits

Its virtues are clear: it does not require fixing the number of clusters in advance and the dendrogram offers a visual reading of the data's structure. Its limits, too: it is costly—the computation grows at least with the square of the number of data points—the merges are irreversible (an early mistake is not corrected) and it is sensitive to noise and outliers.