Hierarchical clustering

Hierarchical clustering builds a nested sequence of clusters and represents it using a dendrogram.

• Agglomerative (bottom-up): begin with each point as its own cluster; repeatedly merge the closest clusters using a linkage rule (single, complete, average or Ward).
• Divisive (top-down): begin with all points in one cluster and recursively split them.

The dendrogram's leaves represent observations; branch heights represent merge/split dissimilarity. Cutting the dendrogram at a chosen height produces a flat clustering. Hierarchical clustering need not require K in advance, but naive implementations can be computationally expensive and early merges/splits are generally irreversible.