Skip to main content

Short note: Hierarchical clustering

Short answer

Hierarchical clustering builds a dendrogram of nested clusters via agglomerative (bottom-up merging) or divisive (top-down splitting) approaches using linkage criteria like single, complete, or average link. It needs no predefined k, gives a deterministic hierarchy, but cannot undo merges, is sensitive to noise, and has O(n²) complexity.

Write a short note on Hierarchical Clustering.

Hierarchical clustering builds a hierarchy (tree) of nested clusters instead of a single partition. The result is displayed as a dendrogram, a tree whose leaves are individual objects and whose height shows the distance at which clusters merge. Any number of clusters can be obtained by cutting the dendrogram horizontally at a chosen level.

Types

  1. Agglomerative (AGNES, bottom-up): start with every object as a separate cluster and repeatedly merge the two closest clusters until one cluster remains.
  2. Divisive (DIANA, top-down): start with one cluster of all objects and repeatedly split the most heterogeneous cluster.

Distance between clusters (linkage)

  • Single link = smallest distance between members of the two clusters (can form chains).
  • Complete link = largest distance (compact clusters).
  • Average link = mean of all pairwise distances.
  • Centroid / Ward's methods.
 distance
   |        ___________
   |      _|__       _|_
   |     |    |     |   |
   +-----a----b-----c---d----  dendrogram

Features

  • No need to give k in advance; gives a rich view of the data structure.
  • Deterministic result (no random starts).
  • Cannot undo a merge or split; sensitive to noise and outliers.
  • Time complexity at least O(n²), memory O(n²) for the distance matrix; not good for very large data.
  • Improved by BIRCH, CURE and Chameleon.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Mining chapter 5 questions →