Level 4 — ApplicationUnsupervised Learning

Unsupervised Learning

⏱ 60 minutes50 marksprintable — key stays hidden on paper

Level 4 (Application: novel problems, no hints) Time limit: 60 minutes Total marks: 50

Q1. K-Means from scratch on a 1-D dataset. (12 marks)

You are given the 1-D dataset: $\{1,\ 2,\ 4,\ 7,\ 11,\ 13\}$ . Run Lloyd's K-Means with $K=2$ , using initial centroids $c_1 = 2$ , $c_2 = 11$ .

(a) Perform iterations until convergence. Show each assignment step and the recomputed centroids. (7) (b) Report the final clusters, final centroids, and the total within-cluster sum of squares (WCSS = inertia). (3) (c) State one concrete reason why K-Means could return a different, worse clustering on this same data, and how K-Means++ mitigates it. (2)

Q2. PCA via eigendecomposition. (14 marks)

A mean-centred dataset has the covariance matrix $\Sigma = \begin{pmatrix} 4 & 2 \\ 2 & 4 \end{pmatrix}.$

(a) Compute the eigenvalues and corresponding unit eigenvectors of $\Sigma$ . (6) (b) State the first principal component direction and compute the proportion of variance explained by it. (3) (c) The point $x = (3, 1)^T$ (already centred) is projected onto the first principal component. Compute its scalar projection (the PC1 score). (3) (d) If we reduce to 1 component, write the reconstruction $\hat{x}$ of this point in the original 2-D space. (2)

Q3. DBSCAN reasoning. (10 marks)

Consider these 2-D points with $\varepsilon = 1.5$ (Euclidean) and $minPts = 3$ (a point is core if its $\varepsilon$ -neighbourhood, including itself, contains $\ge minPts$ points):

$A(0,0),\ B(1,0),\ C(0,1),\ D(5,5),\ E(5,6),\ F(10,10).$

(a) Classify each point as core, border, or noise. Justify using neighbourhood counts. (6) (b) List the clusters DBSCAN produces. (2) (c) Give one advantage of DBSCAN over K-Means demonstrated by this dataset. (2)

Q4. Choosing K and cluster validity. (7 marks)

A practitioner runs K-Means for $K = 1\ldots6$ and records inertia:

K	1	2	3	4	5	6
Inertia	820	310	150	120	100	92

(a) Using the elbow method, identify the recommended $K$ and justify quantitatively (e.g. via marginal drop in inertia). (4) (b) The silhouette score for a single point $i$ is $s(i) = \dfrac{b(i)-a(i)}{\max(a(i),b(i))}$ . For a point with $a(i)=2$ , $b(i)=5$ , compute $s(i)$ and interpret its sign/magnitude. (3)

Q5. Gaussian Mixture Models & EM. (7 marks)

A 1-D two-component GMM has current parameters: means $\mu_1=0,\ \mu_2=4$ , equal variances $\sigma^2=1$ , and mixing weights $\pi_1=\pi_2=0.5$ .

(a) For the data point $x=1$ , compute the responsibility $\gamma_1$ (posterior probability that $x$ belongs to component 1) in the E-step. (5) (b) State one key conceptual difference between the GMM/EM soft assignment and K-Means hard assignment. (2)

Answer keyMark scheme & solutions

Q1 (12 marks)

(a) Iterations (7)

Init: $c_1=2,\ c_2=11$ .

Iter 1 — assign (nearest centroid): distances to 2 vs 11.

1→c1, 2→c1, 4→c1 (|4-2|=2 < |4-11|=7), 7→c1 (|7-2|=5 < |7-11|=4? No: 5>4 → c2). Recheck: 7 to c1 = 5, to c2 = 4 → c2.
11→c2, 13→c2. Cluster1 = {1,2,4}, Cluster2 = {7,11,13}. (2)

Recompute: $c_1=(1+2+4)/3 = 7/3 \approx 2.333$ , $c_2=(7+11+13)/3 = 31/3 \approx 10.333$ . (1)

Iter 2 — assign:

1,2,4 nearest 2.333; 7: |7-2.333|=4.667 vs |7-10.333|=3.333 → c2; 11,13 → c2. No change. (2)

Convergence: assignments unchanged → stop. (2)

(b) Results (3)

Clusters: {1,2,4} and {7,11,13}. (1)
Centroids: $7/3$ and $31/3$ . (1)
WCSS: cluster1: $(1-7/3)^2+(2-7/3)^2+(4-7/3)^2 = (16/9)+(1/9)+(25/9)=42/9=14/3\approx4.667$ . cluster2: $(7-31/3)^2+(11-31/3)^2+(13-31/3)^2=(100/9)+(4/9)+(64/9)=168/9=56/3\approx18.667$ . Total WCSS $=14/3+56/3=70/3\approx23.333$ . (1)

(c) (2) K-Means is sensitive to initialization; a poor random init (e.g. two centroids inside {1,2,4}) can converge to a local minimum with higher inertia. K-Means++ spreads initial centroids by choosing them with probability proportional to squared distance from existing centroids, reducing bad-init risk. (2)

Q2 (14 marks)

(a) Eigen (6) Characteristic eq: $\det(\Sigma-\lambda I)=(4-\lambda)^2-4=0 \Rightarrow (4-\lambda)=\pm2 \Rightarrow \lambda_1=6,\ \lambda_2=2$ . (3)

$\lambda_1=6$ : $(4-6)v_1+2v_2=0\Rightarrow v_1=v_2$ → unit vector $\frac{1}{\sqrt2}(1,1)^T$ . (2)
$\lambda_2=2$ : $v_1=-v_2$ → $\frac{1}{\sqrt2}(1,-1)^T$ . (1)

(b) PC1 & variance (3) PC1 direction: $\frac{1}{\sqrt2}(1,1)^T$ . (1) Proportion explained = $\lambda_1/(\lambda_1+\lambda_2)=6/8=0.75$ (75%). (2)

(c) Projection score (3) $z = u_1^T x = \frac{1}{\sqrt2}(1,1)\cdot(3,1)^T = \frac{4}{\sqrt2}=2\sqrt2\approx2.828$ . (3)

(d) Reconstruction (2) $\hat{x}=z\,u_1 = 2\sqrt2 \cdot \frac{1}{\sqrt2}(1,1)^T = (2,2)^T$ . (2)

Q3 (10 marks)

(a) Classification (6) Neighbourhoods (radius 1.5, incl. self):

A(0,0): B dist 1, C dist 1 → {A,B,C} = 3 ≥ 3 → core. (1)
B(1,0): A dist 1, C dist $\sqrt2\approx1.41$ → {A,B,C} = 3 → core. (1)
C(0,1): A dist 1, B dist 1.41 → {A,B,C}=3 → core. (1)
D(5,5): E dist 1 → {D,E}=2 < 3 → not core; D reachable from core? No core within 1.5 → but D–E mutually. Neither core → noise (D). (1)
E(5,6): {D,E}=2 <3 → not core, not reachable from a core → noise. (1)
F(10,10): isolated, neighbourhood={F}=1 → noise. (1)

(b) Clusters (2) One cluster: {A,B,C}. Points D, E, F are noise. (2)

(c) Advantage (2) DBSCAN detects noise/outliers (D,E,F) and does not force every point into a cluster, unlike K-Means which assigns all points and assumes roughly spherical/equal clusters. (2)

Q4 (7 marks)

(a) Elbow (4) Marginal drops: 820→310 (−510), 310→150 (−160), 150→120 (−30), 120→100 (−20), 100→92 (−8). (2) The large drops stop after K=3; the drop from 3→4 (30) is small relative to earlier drops. The "elbow" is at K=3. (2)

(b) Silhouette (3) $s(i)=\dfrac{5-2}{\max(2,5)}=\dfrac{3}{5}=0.6$ . (2) Positive and fairly large → point is well matched to its own cluster and poorly matched to neighbouring cluster (good clustering for this point). (1)

Q5 (7 marks)

(a) Responsibility (5) Gaussian (equal $\sigma^2=1$ ): density $\propto \exp(-(x-\mu)^2/2)$ .

comp1: $\exp(-(1-0)^2/2)=\exp(-0.5)\approx0.6065$ . (2)
comp2: $\exp(-(1-4)^2/2)=\exp(-4.5)\approx0.0111$ . (1) Equal weights cancel: $\gamma_1=\frac{0.6065}{0.6065+0.0111}=\frac{0.6065}{0.6176}\approx0.9820.$ (2)

(b) (2) GMM/EM assigns each point a soft probability of membership across all components (fractional), whereas K-Means assigns each point entirely to one cluster (hard assignment). GMM also models cluster shape via covariance. (2)

[
  {"claim":"Q1 WCSS = 70/3","code":"c1=Rational(7,3); c2=Rational(31,3); w=sum((x-c1)**2 for x in [1,2,4])+sum((x-c2)**2 for x in [7,11,13]); result = (w==Rational(70,3))"},
  {"claim":"Q2 eigenvalues of Sigma are 6 and 2","code":"M=Matrix([[4,2],[2,4]]); ev=sorted(M.eigenvals().keys()); result = (ev==[2,6])"},
  {"claim":"Q2c projection score = 2*sqrt(2)","code":"u=Matrix([1,1])/sqrt(2); x=Matrix([3,1]); z=(u.T*x)[0]; result = simplify(z-2*sqrt(2))==0"},
  {"claim":"Q4b silhouette = 0.6","code":"a=2; b=5; s=(b-a)/max(a,b); result = (Rational(3,5)==Rational(s).limit_denominator())"},
  {"claim":"Q5 responsibility approx 0.982","code":"g1=exp(Rational(-1,2)); g2=exp(Rational(-9,2)); r=g1/(g1+g2); result = abs(float(r)-0.982) < 0.002"}
]