The GATE Grind

GATE 2024 DA – Question 42

Machine Learning · Unsupervised learning: clustering · 2 marks · Multiple choice

Consider the table below, where the $(i, j)^{th}$ element of the table is the distance between points $x_i$ and $x_j$. Single linkage clustering is performed on data points $x_1, x_2, x_3, x_4, x_5$.

$x_1$$x_2$$x_3$$x_4$$x_5$
$x_1$01436
$x_2$10353
$x_3$43025
$x_4$35201
$x_5$63510

Which ONE of the following is the correct representation of the clusters produced?

four dendrograms A to D over the leaves $x_1$ to $x_5$. In A, $x_1$ and $x_2$ join, $x_4$ and $x_5$ join, $x_3$ then joins the $\{x_4, x_5\}$ group, and the two groups finally join. In B, $x_3$ joins $\{x_1, x_2\}$ first. In C, $x_3$ and $x_4$ join and then $x_5$ joins them. In D, $x_3$ and $x_4$ join and $x_5$ is added last.
  1. Option A in the figure
  2. Option B in the figure
  3. Option C in the figure
  4. Option D in the figure

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Option A in the figure

Explanation

In single linkage the distance between clusters is the smallest distance between their points. The smallest distance is 1, between $x_1$ and $x_2$ and also between $x_4$ and $x_5$, so these two pairs merge first. Next, the distance from $x_3$ to $\{x_4, x_5\}$ is $\min(2, 5) = 2$, and to $\{x_1, x_2\}$ is $\min(4, 3) = 3$, so $x_3$ joins $\{x_4, x_5\}$ at height 2. Finally $\{x_1, x_2\}$ and $\{x_3, x_4, x_5\}$ join at height $\min(3, 3, 5, 6, 4, 3) = 3$. Dendrogram A shows this order.