GATE 2025 DA Q.30: solution and answer

GATE 2025 · DAQ.30 · 1 mark · MSQ

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}$ .

DIS-1 (C_{1}, C_{2}) = x \in C_{1}, y \in C_{2} max D (x, y)

DIS-2 (C_{1}, C_{2}) = x \in C_{1}, y \in C_{2} min D (x, y)

Which of the following statements is/are correct?

(A)
Single Linkage Clustering uses DIS-1
(B)
Single Linkage Clustering uses DIS-2
(C)
Complete Linkage Clustering uses DIS-2
(D)
Complete Linkage Clustering uses DIS-1

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct options are (B) and (D): single linkage uses DIS-2 (minimum), and complete linkage uses DIS-1 (maximum).

Official answer: B, DSource: Official answer key, GATE 2025 DA (IIT Roorkee)

$DIS-1 (C_{1}, C_{2}) = max_{x \in C_{1}, y \in C_{2}} D (x, y)$ is the dissimilarity between the two farthest points, one from each set.
$DIS-2 (C_{1}, C_{2}) = min_{x \in C_{1}, y \in C_{2}} D (x, y)$ is the dissimilarity between the two closest points, one from each set.
Single linkage defines the distance between two clusters as the smallest pairwise dissimilarity between them, $min_{x \in C_{1}, y \in C_{2}} D (x, y)$ . That is DIS-2, so (B) is correct and (A) is wrong.
Complete linkage defines the distance between two clusters as the largest pairwise dissimilarity between them, $max_{x \in C_{1}, y \in C_{2}} D (x, y)$ . That is DIS-1, so (D) is correct and (C) is wrong.
The correct statements are (B) and (D).

KEY IDEA

Single linkage measures the distance between clusters by their closest pair (a minimum, DIS-2). Complete linkage measures it by their farthest pair (a maximum, DIS-1). Average linkage uses the mean of all pairwise distances.

WATCH OUT FOR

Mixing up the two names, for example reading "single" as "the single farthest point". Single linkage is the nearest-neighbour rule (min) and complete linkage is the farthest-neighbour rule (max).

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 4 Clustering questions, with notes

GATE 2025 DA Q.30: solution and answer

Answer and solution

More Clustering questions