Linkage Criteria in Hierarchical 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.

Every algorithm in the agglomerative family begins the same way: each point is declared to be its own cluster. If there are twenty data points, the algorithm starts with twenty clusters, each containing exactly one point. Nothing has been grouped yet.

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. Because a merge always reduces the number of clusters by exactly one, the count shrinks step by step. The procedure does not jump straight to a final answer. It moves through a sequence of intermediate arrangements, each one slightly coarser than the one before.

Notice in this trace that the cluster count is the only thing the diagram tracks. Each step removes exactly one cluster, and the arrangement grows coarser as it goes. The diagram does not yet say which two clusters were chosen at each step. That decision is a separate question, and it is where linkage criteria come in.

The phrase 'two most similar clusters' hides a real choice. Points have a natural similarity to one another, but a cluster is a group, and it is not immediately obvious how to say how similar one group is to another group. Once a cluster contains several points, the question changes from how close two points are to how close two groups of points are.

Point-to-point distance alone is not enough. A single distance value between two individual points does not tell the algorithm how to compare a cluster holding three points with a cluster holding two. Without a rule for cluster-to-cluster similarity, the algorithm would have no defined way to pick the next merge once merging has begun.

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 the stopping criterion 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 remains.

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. The stopping condition is checked against the current state of the clusters, not against the original points.