Back to the 2023 paper

Module 4: Cluster Analysis

20237m

Write a short note on Hierarchical Clustering.

(Q.9: short notes on any two of the following)

Worked SolutionAI Assisted

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 (nn clusters) and repeatedly merge the two closest clusters until only one cluster remains. n−1n-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 (2n−1−12^{n-1}-1 possible splits for nn 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 kk 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(n3)O(n^3) time and O(n2)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 kk-NN graph and dynamic modelling), and ROCK (for categorical data).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.