Linkage Criteria in Agglomerative Clustering

Suppose you have a pile of unlabeled data points and no idea how many natural groups they form. Clustering methods answer this kind of question by grouping points that resemble each other. Agglomerative clustering is one family of these methods, and its strategy is unusual. Instead of splitting one big group into smaller ones, it starts at the opposite extreme and builds larger groups up from the bottom.

Every algorithm in the agglomerative family starts in the same place: each data point is treated as a cluster containing only itself. From that starting arrangement, the algorithm repeatedly looks for the two clusters that are most similar to each other and merges them into one. After each merge there is one fewer cluster, and the process continues.

It helps to notice what the procedure never does. It does not start with one big cluster and cut it apart, and it does not need a guess about the final groups before it begins. The final grouping emerges from the sequence of merges themselves. This is why the word agglomerative, meaning gathering together, fits the method well.

The algorithm begins in a state where every point is a cluster of its own. In each step it finds the two clusters that are closest and merges them. The source traces this process on a small two-dimensional dataset. In the first four steps, two single-point clusters are picked and joined into two-point clusters. In step five, one of those two-point clusters picks up a third point. The process continues until nine steps have passed and only three clusters remain. Because three clusters were requested, the algorithm stops there.

Notice what the diagram leaves open. It says the two closest clusters are merged, but it does not say what closest means. The word closest is a placeholder until a linkage criterion gives it a precise meaning. Each merge depends on one question: which two clusters are close enough to join? The algorithm itself does not answer that question. A linkage criterion does, and that single choice changes which groups come out at the end.

Merging cannot go on forever, so the algorithm needs a rule for when to halt. That rule is called the stopping criterion, and it is what ends the loop. The general idea is to keep merging the most similar pair of clusters until the stopping criterion is satisfied.

In scikit-learn, the implementation discussed in the source uses the number of clusters as its stopping criterion. You tell the algorithm how many clusters you want to end up with, and it keeps merging the most similar clusters until only that number is left. The number is therefore an input you supply, not something the algorithm discovers on its own.

The tree above is an illustration rather than output from the source. It shows the idea that the stopping criterion is a cut through the merge history. Merges below the cut are performed, and the clusters that exist at the cut are the final groups. Setting n_clusters to 3 places the cut where three clusters remain.

An important detail is that a linkage criterion always compares two clusters that already exist. It is not a rule for comparing a single point to a single point in isolation at the moment of merging. Early in the process, clusters may still be single points, but the linkage rule still operates on pairs of current clusters. Each time a merge happens, the set of clusters changes, and the comparisons are made again on the new set.

scikit-learn implements three choices of linkage criterion. The three options differ in how they define similarity between clusters, so the same data can produce different merge sequences depending on the one you pick. You select the criterion as a setting when you configure the model.

Ward minimizes the increase in variance that a merge causes. Average linkage uses the average distance between all points in the two clusters. Complete linkage uses the maximum distance between points in the two clusters. Each one looks at the points inside the two candidate clusters in a different way, so each can pick a different pair at the same step.

The source gives a practical default. Ward is the default and works on most datasets. Average or complete linkage may work better when cluster sizes differ greatly. The source's guidance is framed around the balance of cluster sizes, so that is the main factor to weigh when you choose. The source does not give further rules about cluster shape, so treat shape-based judgments as something to check on your own data rather than as settled guidance.

The program below applies agglomerative clustering to a small two-dimensional dataset and asks for three clusters. The data is invented for illustration. The key settings are n_clusters, which is the stopping criterion, and linkage, which is the rule that defines closeness between clusters. The fit_predict call returns a cluster label for each training point.

Changing linkage to average or complete in the same program keeps n_clusters at 3 but may produce a different grouping for the same data, because each criterion defines closeness differently. The labels printed are the final three groups after the merge sequence has run.

A common beginner error is to treat agglomerative clustering like a model that learns a rule and then labels new data. The source is explicit that agglomerative clustering has no predict method for new points. The correct approach is to use fit_predict on the training data to get cluster memberships.