Clustering Fundamentals

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.

The starting arrangement is the foundation of the whole method. Each algorithm in the agglomerative family begins in the same way: every point is declared to be its own cluster. A cluster containing a single point is still a cluster, so the algorithm has a valid arrangement from its very first moment, even though no grouping has occurred.

Comparing the two arrangements shows what the algorithm is doing. The first arrangement contains five clusters that each hold one point. The second contains three clusters, and two of them now hold more than one point. Each merge combined two existing clusters, so the groups grew while the total number of clusters fell.

From the starting arrangement, the algorithm repeats one operation. It finds the two most similar clusters that currently exist and merges them into a single cluster. A merge always reduces the number of clusters by exactly one, so the count shrinks step by step. 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 this progression tracks. What decides which two clusters are merged at each step is a separate question, and that question is where linkage criteria come in. In the example above, the choice of A and B first, then D and E, is an assumed outcome of a similarity measure, not something the count itself could determine.

The phrase two most similar clusters hides a real choice. Points have a natural similarity to one another, but a cluster is a group, so it is not immediately obvious how to say how similar a group is to another group. The source states that several linkage criteria exist, and that each one defines exactly how the similarity between two clusters is measured. The linkage criterion is therefore the rule that turns pairwise closeness into a verdict about which clusters are closest.

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

The target number of clusters does not influence which pair is merged. It only decides when the loop ends. The stopping check looks at the current state of the clusters, not at the original points, so each pass asks the same question about the arrangement that exists after the previous merge.