Data Science Tools & Software - Assignment No. 3

Q1. (Dissimilarity & Linkage)

Given three objects A, B, and C with the following pairwise dissimilarities:

<aside> 📐

$$ P(X)=\begin{pmatrix}0&1&4\\1&0&2\\4&2&0\end{pmatrix} $$

</aside>

1.1. When using single‐linkage (nearest‐neighbor) clustering, which two objects merge first?

• a) A and B
• b) A and C
• c) B and C
• d) They all tie (no unique first pair)

1.2. After the first merge in single‐linkage (from 1.1), what is the distance between the newly formed cluster and the remaining object?

• a) 1
• b) 2
• c) 3
• d) 4

1.3. Using complete‐linkage (farthest‐neighbor) on the same dissimilarity matrix, which two objects merge first?

• a) A and B
• b) A and C
• c) B and C
• d) No unique first pair (tie)

1.4. After merging in complete‐linkage, what is the linkage distance between the new cluster and the remaining object?

• a) 1
• b) 2
• c) 3
• d) 4

1.5. Suppose we treat objects A and B as initial centroids for two clusters (C₁ and C₂) in a “k‐means” style assignment, and object C is left unassigned. If

$x_1 = [1,\;3], \quad x_2 = [2,\;5], \quad x_3 = [3,\;7],$

which cluster does x₃ join (hard assignment) if using Euclidean distance?

• a) C₁ (centroid at x₁)
• b) C₂ (centroid at x₂)
• c) Tied assign arbitrarily
• d) Neither (x₃ becomes a singleton)

1.6. In that same scenario (1.5), if x₃ joins whichever of C₁ or C₂ is closest, what will be the coordinates of the new centroid of the cluster that absorbs x₃?

• a) $[\,2,\;4\,]$
• b) $[\,2.5,\;6\,]$
• c) $[\,3,\;7\,]$
• d) $[\,1.5,\;4\,]$

Q2. (Clustering Cost, Linkage, DBSCAN)

Consider a 2‐D dataset and two cluster centers $m_1 = (1,1)$ and $m_2 = (3,3)$.

2.1. If you replace $m_1$ with the new center $(2,2)$, the cost change (sum of squared distances from points to the closest center) depends on the points’ locations. In general, shifting a center closer to the cluster points will:

• a) Always increase the total cost
• b) Always decrease the total cost
• c) Either increase or decrease, depending on data configuration
• d) Leave the cost unchanged if there are exactly two points

2.2. Given the following 4 points in the plane:

P₁=(1, 4), P₂=(2, 0), P₃=(4, 1), P₄=(0, 2)

When clustering these 4 points with single‐linkage, the first merge occurs between the two with the smallest pairwise distance. Which pair is it?

• a) $(P_1,P_3)$
• b) $(P_1,P_4)$
• c) $(P_2,P_3)$
• d) b or c

2.3. In a k-distance graph for $k=3$ (plotting each point’s distance to its 3rd-nearest neighbor, sorted), a sharp “elbow” typically suggests a good choice of ε (Epsilon) for DBSCAN. If the k-distance plot jumps sharply around value 1.5, a suitable ε for DBSCAN would be around:

• a) 0.5
• b) 1.0
• c) 1.5
• d) 2.0

2.4. If you apply DBSCAN with $ε = √2$ and $\text{MinPts} = 2$ starting from point $(4,4)$, a point is a core point if it has at least MinPts within radius $ε$. Which type of point is $(4,4)$ if its only neighbor within distance $√2$ is $(3,3)$?

• a) Core point
• b) Border point
• c) Noise point
• d) Cannot determine without full dataset

2.5. To produce the same two clusters from single‐linkage as from DBSCAN in 2.4, one must “cut” the dendrogram at a height equal to:

• a) $1$
• b) $√2$
• c) $2$
• d) $2√2$

2.6. If single‐, complete‐, and average‐linkage each produce two clusters, the pairwise distances between those two clusters (i.e., the distance between cluster centroids, or the minimum/maximum distance) will generally satisfy:

• a) single‐linkage distance ≤ average‐linkage distance ≤ complete‐linkage distance
• b) complete‐linkage distance ≤ average‐linkage distance ≤ single‐linkage distance
• c) average‐linkage distance ≤ single‐linkage distance ≤ complete‐linkage distance
• d) single‐linkage distance = average‐linkage distance = complete‐linkage distance