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: Recall how the first merge in agglomerative clustering works.
Agglomerative clustering starts with every point as its own cluster, and at each step it merges the two clusters that are closest under the chosen distance metric. For the very first merge, this just means finding the pair of points with the smallest pairwise Manhattan distance, since no clusters have combined yet.

Step 2: Recall the Manhattan distance formula.
For two points \(A = (a_1, a_2, a_3)\) and \(B = (b_1, b_2, b_3)\), the Manhattan distance is
\[ d(A,B) = |a_1 - b_1| + |a_2 - b_2| + |a_3 - b_3| \]

Step 3: Compute all 6 pairwise distances.
\(d(P1,P2) = |2-3| + |3-1| + |{-1}-1| = 1 + 2 + 2 = 5\)
\(d(P1,P3) = |2-5| + |3-({-2})| + |{-1}-3| = 3 + 5 + 4 = 12\)
\(d(P1,P4) = |2-3| + |3-3| + |{-1}-3| = 1 + 0 + 4 = 5\)
\(d(P2,P3) = |3-5| + |1-({-2})| + |1-3| = 2 + 3 + 2 = 7\)
\(d(P2,P4) = |3-3| + |1-3| + |1-3| = 0 + 2 + 2 = 4\)
\(d(P3,P4) = |5-3| + |{-2}-3| + |3-3| = 2 + 5 + 0 = 7\)

Step 4: Pick the smallest distance.
The distances are 5, 12, 5, 7, 4, and 7. The smallest of these is 4, between P2 and P4, so this pair merges first. Option (A) has distance 5, not the minimum. Options (B) and (C) both have distance 7. Option (D) has the true minimum of 4.

Final Answer:
P2 and P4 merge first. This is option (D).