Skip to main content

Hierarchical clustering: AGNES and DIANA

Short answer

Hierarchical clustering creates nested clusters in a dendrogram without a pre-specified number. AGNES (bottom-up) repeatedly merges the closest pair of clusters; DIANA (top-down) splits the cluster with the largest diameter until each object is a singleton.

What is hierarchical clustering? Describe AGNES and DIANA methods of hierarchical clustering approach.

Hierarchical clustering groups data into a tree of nested clusters (a dendrogram), either by merging smaller clusters into larger ones or by splitting a large cluster. The user does not give k in advance; a clustering is obtained by cutting the dendrogram at a chosen level. Merges and splits are final and cannot be undone.

AGNES (Agglomerative Nesting), bottom-up

  1. Treat each object as its own cluster; compute the distance matrix.
  2. Merge the two closest clusters into one.
  3. Update the distances between the new cluster and the others.
  4. Repeat steps 2-3 until all objects are in a single cluster (or the desired k is reached).

The distance between clusters is defined by the linkage:

  • Single link: minimum distance between two objects of different clusters.
  • Complete link: maximum distance.
  • Average link: average of all pairwise distances.
  • Centroid distance.

DIANA (Divisive Analysis), top-down

  1. Start with all objects in one cluster.
  2. Choose the cluster with the largest diameter and split it: the object with the highest average dissimilarity to the others forms a "splinter group"; objects that are closer to the splinter group than to the rest move to it.
  3. Repeat the splitting until each cluster has one object (or until there are k clusters).
 a b c d e
 AGNES (merge)  ->  {a,b} {d,e} -> {a,b,c} {d,e} -> {a..e}
 DIANA (split)  <-  inverse order
BasisAGNESDIANA
DirectionBottom-upTop-down
Startn clusters1 cluster
StepMerge closest pairSplit the largest-diameter cluster
CostO(n²) or moreHigher, as the number of possible splits is exponential

Both cost at least O(n²), so they are not suitable for huge data sets; BIRCH, CURE and Chameleon improve on this.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Mining chapter 5 questions →