Question

Let four points in three-dimensional space be:
\(P1: [2, 3, -1]\), \(P2: [3, 1, 1]\), \(P3: [5, -2, 3]\) and \(P4: [3, 3, 3]\).
Hierarchical Agglomerative Clustering is used to cluster the above points. If Manhattan Distance is used as the distance metric during clustering, which of the following options indicates the two points that will be merged first?

• A. \(P1, P2\)
• B. \(P2, P3\)
• C. \(P3, P4\)
• D. \(P2, P4\)

Hint:

Compute all 6 pairwise Manhattan distances between the points and pick the smallest one.

Answer 1

The Correct Option is D

Step 1: List the coordinates clearly.
$P1 = (2, 3, -1)$, $P2 = (3, 1, 1)$, $P3 = (5, -2, 3)$, $P4 = (3, 3, 3)$. Manhattan distance between two points just adds up the absolute differences along each of the 3 coordinate axes, so we build a small distance table for all pairs.

Step 2: Work out the coordinate-wise differences for each pair.
$P1$ to $P2$: differences are $1, 2, 2 \Rightarrow$ sum $= 5$
$P1$ to $P3$: differences are $3, 5, 4 \Rightarrow$ sum $= 12$
$P1$ to $P4$: differences are $1, 0, 4 \Rightarrow$ sum $= 5$
$P2$ to $P3$: differences are $2, 3, 2 \Rightarrow$ sum $= 7$
$P2$ to $P4$: differences are $0, 2, 2 \Rightarrow$ sum $= 4$
$P3$ to $P4$: differences are $2, 5, 0 \Rightarrow$ sum $= 7$

Step 3: Scan the table for the smallest entry.
Sorting the six distances: $4 < 5 = 5 < 7 = 7 < 12$. The smallest value, 4, belongs to the pair $(P2, P4)$, since their $x$-coordinates already match (difference 0) and their $y$ and $z$ coordinates are each only 2 apart.

Step 4: Apply the clustering rule.
In agglomerative clustering the very first merge always joins the closest pair of individual points. Since $(P2, P4)$ has the smallest Manhattan distance of all six pairs, this is the pair that merges first.

Final Answer:
The pair $(P2, P4)$ merges first, which is option (D).