Exam SRM — Clustering & KNN Practice Flashcards

**Answer: (B).** K-means partitions the data into $K$ non-overlapping clusters $C_1,\dots,C_K$ to minimize $\sum_{k=1}^{K} W(C_k)$, where the standard within-cluster variation is the sum of **squared** Euclidean distances of each point to its cluster centroid: $W(C_k)=\sum_{i\in C_k}\lVert x_i-\bar x_k\rVert^{2}$. Choice (A) drops the square (it uses raw distance, not squared). Choice (C) uses only the farthest point, not the full sum. Choice (D) counts cluster sizes, not variation. Choice (E) is wrong because $K$ is **specified in advance**, not optimized jointly — the objective always shrinks to $0$ as $K\to n$, so it cannot be minimized over $K$.

**Answer: (C).** Assign to the nearest centroid; compare **squared** Euclidean distances (square roots preserve the ordering). To $A$: $(3-1)^{2}+(2-1)^{2}=4+1=5$. To $B$: $(3-4)^{2}+(2-3)^{2}=1+1=2$. Since $2<5$, $(3,2)$ is assigned to cluster $B$, with squared distance $2$. Choice (A) reports the (larger) distance to $A$; choice (D) misstates the distance to $B$ as $5$.

**Answer: (D).** Centroid: $\bar x=\left(\dfrac{0+4+0+4}{4},\dfrac{0+0+3+3}{4}\right)=(2,1.5)$. Squared distances to $(2,1.5)$: $(0,0)$: $(-2)^{2}+(-1.5)^{2}=4+2.25=6.25$. $(4,0)$: $2^{2}+(-1.5)^{2}=4+2.25=6.25$. $(0,3)$: $(-2)^{2}+1.5^{2}=4+2.25=6.25$. $(4,3)$: $2^{2}+1.5^{2}=4+2.25=6.25$. $W=4(6.25)=25.0$. (Halving each squared deviation, i.e. using the centroid form but forgetting one axis, yields $12.5$.)

**Answer: (A).** Update the centroids as cluster means: $\bar x_A=\left(\dfrac{1+3}{2},0\right)=(2,0)$ and $\bar x_B=\left(\dfrac{8+12}{2},0\right)=(10,0)$. Reassign $(3,0)$: squared distance to $A=(3-2)^{2}=1$; to $B=(3-10)^{2}=49$. Since $1<49$, it stays in cluster $A$, whose updated centroid is $(2,0)$. Choice (C) gives the correct $B$ centroid but the wrong assignment.

**Answer: (A).** Assign each point to the nearer initial centroid ($2$ or $9$). Points $1,2,3$ are closer to $2$; points $8,9,10$ are closer to $9$. So $A=\{1,2,3\}$, $B=\{8,9,10\}$. Recompute means: $\bar x_A=\dfrac{1+2+3}{3}=2$ and $\bar x_B=\dfrac{8+9+10}{3}=9$. The centroids are unchanged at $2$ and $9$, so the algorithm has already converged. (Choices that shift a centroid assume a point like $3$ or $8$ was misassigned to the far cluster.)

**Answer: (A).** Pairwise distances: $d(P,Q)=2$, $d(Q,R)=5$, $d(P,R)=7$. The smallest is $d(P,Q)=2$, so $P$ and $Q$ merge **first at height $2$**. Under single linkage the distance from $R$ to cluster $\{P,Q\}$ is the **minimum** pairwise distance: $\min(d(P,R),d(Q,R))=\min(7,5)=5$. So the final merge occurs at **height $5$**. Complete linkage would instead give $\max(7,5)=7$ (distractor B); average linkage would give $\frac{7+5}{2}=6$.

**Answer: (B).** Average linkage is the mean of all $|G|\cdot|H|=2\cdot2=4$ cross-cluster pairwise distances: $d(G,H)=\dfrac{4+6+2+8}{4}=\dfrac{20}{4}=5$. For contrast, single linkage gives $\min=2$ (distractor A), complete linkage gives $\max=8$ (distractor D), and forgetting to divide by $4$ leaves the sum $20$ (distractor E).

**Answer: (C).** Centroid linkage uses the Euclidean distance between the two cluster centroids: $d(\bar x_G,\bar x_H)=\sqrt{(7-1)^{2}+(10-2)^{2}}=\sqrt{6^{2}+8^{2}}=\sqrt{36+64}=\sqrt{100}=10$. Adding the coordinate gaps without squaring gives $6+8=14$ (distractor D); forgetting the square root leaves $100$ (distractor E).