Number of merges

Topic: Hierarchical clustering and kernel density estimation · more questions on this topic
‹ Linkage by hand Kernel density by hand ›

How many merges does agglomerative clustering of n observations require? How many distinct clusterings (levels) does the hierarchy contain, including the singletons and the single cluster?

Worked answer (click to show)

Each merge reduces the number of clusters by one, so going from n clusters to 1 takes n-1 merges. The hierarchy contains the clusterings with n,n-1,\ldots,1 clusters: n levels, including the singletons and the single cluster at the top. The dendrogram has n leaves and n-1 internal nodes.