Short Note on Hierarchical Clustering

1. Definition

Hierarchical clustering creates a nested hierarchy (a tree) of clusters in which clusters at one level are merged (or split) to form clusters at the next level. The result is usually displayed as a dendrogram - a tree diagram whose vertical axis shows the distance (or dissimilarity) at which each merge/split occurs. Cutting the dendrogram at any height gives a flat clustering with a chosen number of clusters.

2. Two approaches

1. Agglomerative (bottom-up, the most common): start with each object as a singleton cluster ($n$ clusters) and repeatedly merge the two closest clusters until only one cluster remains. $n-1$ merges are needed.
2. Divisive (top-down): start with one cluster containing all objects and repeatedly split the least homogeneous cluster until every object is a singleton. It is less used because deciding which cluster to split is computationally harder ($2^{n-1}-1$ possible splits for $n$ objects).

3. How "closest" is measured - linkage criteria

• Single linkage (minimum distance): distance between the two nearest members of the two clusters. Fast, can find elongated (non-elliptical) clusters, but suffers from the chaining effect - a few noise points can link two large clusters.
• Complete linkage (maximum distance): distance between the two farthest members. Produces compact, equally sized clusters, but is sensitive to outliers.
• Average linkage (UPGMA): average of all pairwise distances between the members of the two clusters - a compromise between single and complete linkage.
• Ward's method: merges the pair whose merge increases the total within-cluster variance the least; tends to give clusters of similar size.
• Centroid linkage: distance between the centres (means) of the two clusters.

4. Illustration

 distance
    |                    +--------------------+
 4  |                    |
    |              +-----+-----+
 3  |              |           |
    |        +-----+-----+     |
 2  |        |     |     |     |
    |   +----+--+ +--+ +--+    |
 1  |   |    |  | |  | |  |    |
    +---+----+--+ +--+ +--+----+-----------> objects
        o1   o2   o3  o4  o5   o6

Clusters {o1,o2} and {o3,o4} form first, then merge into one cluster at a higher level, and the whole set joins at the top; cutting at height 2 gives, say, three clusters.

5. Merits, demerits and variants

• Merits: no need to prespecify the number of clusters $k$ in advance; the dendrogram is easy to interpret and shows the natural nesting of groups at several abstraction levels.
• Demerits: merge/split decisions are irreversible (an early wrong merge cannot be undone); a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory to maintain the distance matrix, so it does not scale well to very large data sets; sensitive to noise and to the choice of linkage.
• Scalable variants: BIRCH (clustering feature tree, incremental), CURE (uses well-scattered representative points), CHAMELEON (uses a $k$-NN graph and dynamic modelling), and ROCK (for categorical data).