GATE DA 2024 | Question 42

MCQ · 2 marks · −0.66

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?

  1. Option A: Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x4 joins x5 at the lowest level, x3 then joins the x4, x5 pair, and finally the x1, x2 pair joins the x3, x4, x5 group at the top. (correct)
  2. Option B: Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x4 joins x5 at the lowest level, x3 then joins the x1, x2 pair, and finally the x1, x2, x3 group joins the x4, x5 pair at the top.
  3. Option C: Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x3 joins x4 at the lowest level, x5 then joins the x3, x4 pair, and finally the x1, x2 pair joins the x3, x4, x5 group at the top.
  4. Option D: Dendrogram over x1, x2, x3, x4, x5: x1 joins x2 and x3 joins x4 at the lowest level, the two pairs then merge, and finally x5 joins the x1, x2, x3, x4 group at the top.

Answer

(A)

Explanation

Single linkage repeatedly merges the two clusters whose closest members are nearest to each other.

  • Distance 1: \(x_{1}\) joins \(x_{2}\), and \(x_{4}\) joins \(x_{5}\).
  • Distance 2: \(x_{3}\) joins \(\{x_{4}, x_{5}\}\) through \(d(x_{3}, x_{4}) = 2\); the pair \(\{x_{1}, x_{2}\}\) is at least 3 from every other point.
  • Distance 3: \(\{x_{1}, x_{2}\}\) joins \(\{x_{3}, x_{4}, x_{5}\}\), for example through \(d(x_{1}, x_{4}) = 3\).

Dendrogram A shows exactly this. B attaches \(x_{3}\) to \(\{x_{1}, x_{2}\}\), where its nearest link is 3, not 2. C and D pair \(x_{3}\) with \(x_{4}\) first, although \(d(x_{4}, x_{5}) = 1\) is smaller than \(d(x_{3}, x_{4}) = 2\).

Answer: A