Hierarchical Clustering
Hierarchical clustering builds a whole tree of clusters instead of a single partition. You can cut the tree at any height to get the number of clusters you want.
Agglomerative approach
The most common form is agglomerative, meaning bottom up.
- Start with every point as its own cluster.
- Repeatedly merge the two closest clusters into one.
- Continue until a single cluster contains everything.
The record of merges is drawn as a dendrogram, a tree where the height of each join shows how far apart the merged clusters were.
Linkage rules
How you measure distance between clusters is the linkage choice.
- Single linkage uses the closest pair of points and can create long chains.
- Complete linkage uses the farthest pair and favors compact groups.
- Average linkage uses the mean distance between all pairs.
Strengths and costs
You do not need to choose k up front, and the dendrogram reveals structure at many scales. The cost is that naive agglomerative clustering is quadratic or worse in the number of points, so it does not scale to huge datasets.
Key idea
Agglomerative hierarchical clustering merges nearest clusters into a dendrogram you can cut at any level, with no preset k.