Hierarchical clustering

Hierarchical clustering builds a tree of clusters (a dendrogram) instead of a single partition. The common agglomerative version starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains.

How 'closest' is measured between clusters is the linkage:

• Single: distance between the closest pair of points — finds long chains, sensitive to noise.
• Complete: distance between the farthest pair — compact, similar-sized clusters.
• Average: mean distance over all pairs — a compromise.
• Ward: the merge that least increases total within-cluster variance — similar to k-means.

Cut the dendrogram at a chosen height to get any number of clusters, without re-running. The tree itself is informative — it shows which groups are nearly merged and which are far apart.