Choosing the Number of Clusters

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.

Because the starting arrangement puts each point in its own cluster, nothing has been grouped yet. The number of clusters at the start equals the number of points. This is the baseline from which every later step departs. The procedure does not begin with a guess about the final groups; it begins with the finest possible arrangement and coarsens it one step at a time.

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. Because a merge always reduces the number of clusters by exactly one, the count shrinks step by step. The procedure moves through a sequence of intermediate arrangements, each one slightly coarser than the one before. The diagram below shows the cluster count falling through repeated merges.

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 there are several linkage criteria, and that each one specifies exactly how the most similar cluster is measured.

The measure of similarity is always defined between two existing clusters. The algorithm never asks how similar a point is to some abstract group; at every merge step it compares a specific pair of clusters that actually exist at that moment. As merges happen, the clusters that exist change, so the comparisons available at later steps can differ from those at the start. This is why the third merge in the example above could compare a cluster containing two points against a single point: both were real clusters at that moment.

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. 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 of clusters remain.

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, not against the original points. The target number of clusters therefore has no effect on which pairs merge; it only controls when the loop ends.

Comparing the arrangement before any merging with the arrangement after merging stops shows what the procedure actually produced. In the six-point example, the start has six single-point clusters and the end has two clusters, each holding several points. The diagram marks which points ended up grouped together.