GATE DA Clustering Previous Year Questions

GATE DA 2025 | Question 30

MSQ · 1 mark

Let \(C_{1}\) and \(C_{2}\) be two sets of objects. Let \(D(x, y)\) be a measure of dissimilarity between two objects \(x\) and \(y\). Consider the following definitions of dissimilarity between \(C_{1}\) and \(C_{2}\).

\[\begin{aligned} \textbf{DIS-1}(C_{1}, C_{2}) &= \max_{x \in C_{1},\, y \in C_{2}} D(x, y) \\ \textbf{DIS-2}(C_{1}, C_{2}) &= \min_{x \in C_{1},\, y \in C_{2}} D(x, y) \end{aligned}\]

Which of the following statements is/are correct?

Single Linkage Clustering uses DIS-1 Single Linkage Clustering uses DIS-2 Complete Linkage Clustering uses DIS-2 Complete Linkage Clustering uses DIS-1

Explanation

Answer: (B), (D)

In hierarchical clustering, the linkage rule sets the distance between two clusters from the distances between their members.

Single linkage uses the closest pair, one object from each cluster. That is the minimum of \(D(x, y)\), which is DIS-2.
Complete linkage uses the farthest pair. That is the maximum of \(D(x, y)\), which is DIS-1.

Options A and C swap the two rules.

Answer: B, D

GATE DA 2024 | Question 19

MCQ · 1 mark · −0.33

Euclidean distance based \(k\)-means clustering algorithm was run on a dataset of 100 points with \(k = 3\). If the points \(\begin{bmatrix} 1 \\ 1 \end{bmatrix}\) and \(\begin{bmatrix} -1 \\ 1 \end{bmatrix}\) are both part of cluster 3, then which ONE of the following points is necessarily also part of cluster 3?

\(\begin{bmatrix} 0 \\ 0 \end{bmatrix}\) \(\begin{bmatrix} 0 \\ 2 \end{bmatrix}\) \(\begin{bmatrix} 2 \\ 0 \end{bmatrix}\) \(\begin{bmatrix} 0 \\ 1 \end{bmatrix}\)

Explanation

Answer: (D)

\(k\)-means assigns every point to its nearest centroid, so cluster 3 holds the points that are closer to its centroid \(\boldsymbol{c}_{3}\) than to \(\boldsymbol{c}_{1}\) and \(\boldsymbol{c}_{2}\). For each other centroid \(\boldsymbol{c}_{j}\), the condition \(\lVert\boldsymbol{p} - \boldsymbol{c}_{3}\rVert^{2} \leq \lVert\boldsymbol{p} - \boldsymbol{c}_{j}\rVert^{2}\) simplifies to a linear inequality in \(\boldsymbol{p}\), that is, a half-plane. The region of cluster 3 is an intersection of half-planes, so it is convex: with any two of its points it contains the whole segment between them.

The point \((0, 1)\) is the midpoint of \((1, 1)\) and \((-1, 1)\), so it must belong to cluster 3. The points in A, B and C lie off that segment, and another centroid could be nearer to them.

Answer: D

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}\)	0	1	4	3	6
\(x_{2}\)	1	0	3	5	3
\(x_{3}\)	4	3	0	2	5
\(x_{4}\)	3	5	2	0	1
\(x_{5}\)	6	3	5	1	0

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

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.

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.

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.

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.

Explanation

Answer: (A)

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