Unsupervised Learning

Question 1

(a) [3 marks] $J = \sum_{k=1}^{K}\sum_{i \in C_k} \|x_i - \mu_k\|^2$ where $x_i$ is data point, $C_k$ is the set of points assigned to cluster $k$, $\mu_k$ is the centroid of cluster $k$. (1 mark formula, 1 mark symbols, 1 mark stating it is WCSS to be minimized.)

(b) [4 marks] Fix assignments. For cluster $k$, minimize $J_k=\sum_{i\in C_k}\|x_i-\mu_k\|^2$. Take gradient w.r.t. $\mu_k$: $\nabla_{\mu_k} J_k = \sum_{i\in C_k} -2(x_i-\mu_k) = 0$ (2 marks) $\Rightarrow \sum_{i\in C_k}x_i = |C_k|\,\mu_k \Rightarrow \mu_k = \frac{1}{|C_k|}\sum_{i\in C_k}x_i$ (2 marks) So optimal centroid = mean. (Second derivative positive ⇒ minimum.)

(c) [3 marks]

# Assignment step
dists = ((X[:,None,:] - C[None,:,:])**2).sum(axis=2)  # n×k
labels = dists.argmin(axis=1)                          # n
# Update step
for j in range(k):
    if (labels==j).any():
        C[j] = X[labels==j].mean(axis=0)

(2 marks assignment, 1 mark update; handle empty-cluster acceptable.)

(d) [2 marks] Random init can seed multiple centroids in the same region, leaving others unoccupied → bad local minimum (1). K-Means++ picks initial centroids with probability proportional to squared distance from nearest chosen centroid, spreading them out and giving provably better expected WCSS (1).

Question 2

(a) [4 marks] $s(i) = \frac{b(i)-a(i)}{\max(a(i),b(i))}$ (2) $a(i)$ = mean distance from $i$ to other points in its own cluster; $b(i)$ = lowest mean distance from $i$ to points of any other cluster (1). Range $[-1,1]$ (1).

(b) [2 marks] $s = \frac{5.0-2.0}{\max(2.0,5.0)} = \frac{3.0}{5.0} = 0.6$

(c) [3 marks]

• Elbow: plot WCSS vs K, choose "elbow"; simple/cheap but the elbow is often ambiguous/subjective (1.5).
• Silhouette: measures cohesion vs separation, gives clear numeric optimum; but $O(n^2)$ distance computation is expensive on large data (1.5).

Question 3

(a) [3 marks]

• Core point: has ≥ minPts points within radius $\varepsilon$ (1).
• Border point: not core, but within $\varepsilon$ of a core point (1).
• Noise: neither core nor border (1).

(b) [5 marks] Neighbourhoods (points within 1.5, incl. self):

• 1: {1,2} → 2 ≥ 2 → core
• 2: {1,2,3} → 3 → core
• 3: {2,3} → 2 → core
• 8: {8,9} → 2 → core
• 9: {8,9} → 2 → core
• 25: {25} → 1 < 2 → noise

Clusters: {1,2,3} and {8,9}; 25 = noise. (3 for classification, 2 for cluster grouping.)

(c) [2 marks] Advantage: finds arbitrary-shaped clusters and detects outliers, no need to specify K (1). Struggles: clusters of varying density / high-dimensional data where a single $\varepsilon$ fails (1).

Question 4

(a) [5 marks] Projected variance = $w^\top \Sigma w$ with $\Sigma$ the covariance matrix. Maximize subject to $w^\top w=1$: $\mathcal{L}=w^\top\Sigma w - \lambda(w^\top w -1)$ (2) $\frac{\partial\mathcal{L}}{\partial w}=2\Sigma w - 2\lambda w = 0 \Rightarrow \Sigma w = \lambda w$ (2) So $w$ is an eigenvector of $\Sigma$; variance = $w^\top\Sigma w=\lambda$, maximized by largest eigenvalue (1).

(b) [5 marks] Characteristic eqn: $(4-\lambda)^2-4=0 \Rightarrow (4-\lambda)=\pm2$. Eigenvalues: $\lambda_1=6,\ \lambda_2=2$ (2). For $\lambda=6$: $(4-6)w_1+2w_2=0 \Rightarrow w_1=w_2$. Unit vector: $w=\tfrac{1}{\sqrt2}(1,1)^\top$ (3).

(c) [2 marks] $\frac{\lambda_1}{\lambda_1+\lambda_2}=\frac{6}{6+2}=\frac{6}{8}=0.75$

(d) [2 marks] For centered $X=U\Sigma_{SVD}V^\top$, the columns of $V$ (right singular vectors) are the principal directions; singular values relate to eigenvalues by $\lambda_i=\sigma_i^2/(n-1)$.

Question 5

(a) [3 marks] $\log L = \sum_{i=1}^{n}\log\left(\sum_{k=1}^{K}\pi_k\,\mathcal{N}(x_i\mid\mu_k,\Sigma_k)\right)$ $\pi_k\ge0,\ \sum_k\pi_k=1$ mixing weights; $\mathcal{N}$ Gaussian density. (Formula 2, definitions 1.)

(b) [3 marks] $\gamma_{ik}=\frac{\pi_k\,\mathcal{N}(x_i\mid\mu_k,\Sigma_k)}{\sum_{j=1}^{K}\pi_j\,\mathcal{N}(x_i\mid\mu_j,\Sigma_j)}$

(c) [3 marks] The log-likelihood contains a log-of-sum, so setting derivatives to zero gives coupled equations with no closed form (latent assignments unknown) (1.5). EM introduces responsibilities and optimizes a tractable lower bound (Jensen), guaranteeing monotonic increase of likelihood and closed-form M-step updates (1.5).

Question 6

(a) [3 marks] t-SNE preserves local neighbourhood structure — nearby points stay near (1.5). Inter-cluster distances/global geometry are unreliable because t-SNE optimizes a KL divergence on local probabilities and expands dense regions/shrinks sparse ones; cluster sizes and gaps are not meaningful (1.5).

(b) [3 marks] Any two of: (i) faster and scales better to large data; (ii) better preserves global structure; (iii) can transform new points (has a learned mapping); (iv) fewer perplexity-tuning sensitivities. (1.5 each.)

[
{"claim":"Silhouette (5-2)/max(2,5)=0.6","code":"a=2.0;b=5.0;result=abs((b-a)/max(a,b)-0.6)<1e-9"},
{"claim":"Eigenvalues of [[4,2],[2,4]] are 6 and 2","code":"M=Matrix([[4,2],[2,4]]);ev=sorted([complex(e).real for e in M.eigenvals().keys()]);result=ev==[2.0,6.0]"},
{"claim":"First PC direction (1,1)/sqrt2 is eigenvector with eigenvalue 6","code":"M=Matrix([[4,2],[2,4]]);w=Matrix([1,1])/sqrt(2);result=simplify(M*w-6*w)==Matrix([0,0])"},
{"claim":"Explained variance fraction of PC1 = 0.75","code":"result=Rational(6,6+2)==Rational(3,4)"}
]