Agglomerative Clustering

Imagine you are handed a pile of data points and asked to sort them into groups, but nobody has told you how many groups to expect or what each group should look like. A natural first move is to ask which points belong together, and then to keep combining the most similar groups until the result is manageable. Agglomerative clustering is a family of algorithms built on exactly this idea.

The word agglomerative refers to the act of gathering things together, and that is the direction the whole procedure moves in. Instead of splitting one large dataset into smaller pieces, the algorithm builds larger and larger groups out of smaller ones.

Agglomerative clustering refers to a collection of clustering algorithms that all build upon the same principles. Each algorithm in the family begins in the same way: every point is declared to be its own cluster. So if there are twenty data points, the algorithm starts with twenty clusters, each containing exactly one point. Nothing has been grouped yet.

This starting point is what gives the family its defining behavior. Because every point begins alone, the first decisions are always about pairs of single points, and the groups grow only through the merges that the algorithm performs afterward.

From that starting arrangement, the algorithm repeats one operation. It finds the two most similar clusters that currently exist and merges them into a single cluster. The procedure does not jump to a final answer. It moves through a sequence of intermediate arrangements, each one slightly coarser than the one before.

Notice that the cluster count is the only thing the loop diagram tracks. What decides which two clusters are merged at each step is a separate question, and it is where the linkage criteria come in. Read the loop as a cycle with an exit: the algorithm keeps returning to the search for the most similar pair until the cluster count matches the stopping condition, and only then does it stop.

Consider a two-dimensional dataset where you want three clusters. The source describes the progression in general terms: two single-point clusters are picked and joined into a two-point cluster, and later one of those two-point clusters is extended to include a third point. The concrete numbers below are an illustration built on that pattern.

The loop has a hidden difficulty. When every cluster holds just one point, asking which two clusters are closest is easy, because it is simply the distance between two points. Once a cluster holds several points, the question becomes ambiguous. A cluster is not a single location, so what does it mean for two clusters to be close?

The answer to that question is the linkage criterion. It specifies exactly how the similarity between two clusters is measured, and the choice of criterion changes which clusters get merged and therefore the final result. A linkage criterion is needed in every merge step, because every merge step compares a pair of clusters that may each contain several points.

Three linkage criteria are implemented in scikit-learn. Each one answers the question of how to measure the closeness of two clusters, and each leads to a different kind of merging behavior. Each criterion summarizes the relationship between two clusters in a different way.

Now test the two distance-based criteria on a case where they should disagree. Suppose four clusters already exist on a number line. Cluster P holds the single point 0. Cluster Q holds the points 1 and 5. Cluster R holds the single point 10. Cluster S holds the points 13 and 14.

Merging cannot go on forever, so the algorithm needs a rule for when to stop. In general terms, the algorithm merges the two most similar clusters until some stopping criterion is satisfied. The source specifies which stopping criterion is implemented in scikit-learn: the number of clusters. The user specifies a target number of clusters, and similar clusters are merged until only that number of clusters remain.

Two things are worth noticing. The algorithm never looked at the target until it was time to decide whether to stop, so the target only controlled when the loop ended. The stopping condition is checked against the current state of the clusters, not against the original points.

A sensible workflow is to begin with Ward, since the source describes it as the default and as working on most datasets. Then look at the expected sizes of your clusters. If the clusters are likely to have very dissimilar numbers of members, for example one group much larger than all the others, average or complete linkage may be worth trying in its place.