COMP5318 — Week 10 Supplement
Mathematical Foundations
The K-means SSE objective and centroid update, the GMM responsibilities and the E/M steps, and the silhouette coefficient for evaluating clusterings.
K-means: objective and centroid update
K-means minimises the Sum of Squared Errors between every point and its assigned centroid. The assign / update loop is the block-coordinate descent for this objective.
K-means objective (SSE)
\[ J(\mu, c) \;=\; \sum_{i=1}^{n} \|x_i - \mu_{c_i}\|^2 \;=\; \sum_{j=1}^{k}\sum_{x\in K_j} d(x, \mu_j)^2 \]
where \(c_i \in \{1, \ldots, k\}\) is the cluster assignment of point \(x_i\) and \(\mu_j\) is the centroid of cluster \(K_j\).
Centroid update (M-step of K-means)
Fixing assignments, the optimal \(\mu_j\) is the arithmetic mean:
\[ \mu_j \;=\; \frac{1}{|K_j|}\sum_{x\in K_j} x \]
Fixing centroids, the optimal assignment puts each point with its nearest centroid: \(c_i = \arg\min_j \|x_i - \mu_j\|^2\). Iterating the two steps monotonically decreases \(J\), so K-means converges to a local minimum.
GMM: responsibilities and EM
A Gaussian mixture model assumes \(p(x) = \sum_{j=1}^k w_j\,\mathcal{N}(x\mid\mu_j, \Sigma_j)\) with mixing weights \(w_j \ge 0\), \(\sum_j w_j = 1\). The EM algorithm finds a local maximum of the log-likelihood.
E-step: responsibilities
\[ \gamma_{ij} \;=\; P(\text{cluster } j \mid x_i, \theta) \;=\; \frac{w_j\,P(x_i\mid\theta_j)}{\sum_{j'=1}^{k} w_{j'}\,P(x_i\mid\theta_{j'})} \]
\(\gamma_{ij}\) is the soft membership of point \(i\) in cluster \(j\); it satisfies \(\sum_j \gamma_{ij} = 1\) for each \(i\).
M-step: parameter update
Let \(N_j = \sum_{i=1}^n \gamma_{ij}\) be the effective number of points in cluster \(j\). Then
\[ \mu_j \;=\; \frac{1}{N_j}\sum_{i=1}^{n} \gamma_{ij}\,x_i, \quad \Sigma_j \;=\; \frac{1}{N_j}\sum_{i=1}^{n} \gamma_{ij}\,(x_i-\mu_j)(x_i-\mu_j)^\top, \quad w_j \;=\; \frac{N_j}{n}. \]
Each updated mean is the weighted average of the data, weighted by the responsibilities.
K-means is the limiting case of EM where the responsibilities are hard (one cluster gets weight 1, the rest 0) and the covariances are fixed to a small multiple of the identity. EM generalises this to soft assignments and elliptical covariances.
Silhouette coefficient and clustering quality
The silhouette coefficient is the most-cited internal evaluation measure for clusterings. It combines cohesion and separation into a single score per point.
Silhouette of a point
For point \(i\) in cluster \(K\), let
\[ a_i \;=\; \frac{1}{|K|-1}\sum_{j\in K,\, j\ne i} d(x_i, x_j), \qquad b_i \;=\; \min_{K'\ne K} \frac{1}{|K'|}\sum_{j\in K'} d(x_i, x_j). \]
The silhouette coefficient of point \(i\) is
\[ s_i \;=\; \frac{b_i - a_i}{\max(a_i, b_i)} \;\in\; [-1, 1]. \]
\(s_i\) close to \(+1\) means the point sits well inside its cluster; close to \(0\) means it is on the border between two clusters; negative means it is probably in the wrong cluster.
Cohesion, separation and SSE/BSE
For cluster \(K_i\) with centroid \(c_i\) and overall centroid \(c\):
\[ \text{cohesion}(K_i) \;=\; \sum_{x\in K_i} d(x, c_i), \qquad \text{separation}(K_i) \;=\; d(c_i, c). \]
With squared distance, these become \(\text{SSE} = \sum_i \sum_{x\in K_i} d(x, c_i)^2\) (within-cluster) and \(\text{BSE} = \sum_i |K_i|\,d(c_i, c)^2\) (between-cluster).
Plot SSE (or another internal score) against \(k\). The curve typically decreases as \(k\) grows; a sharp "knee" indicates a value of \(k\) beyond which extra clusters give diminishing returns.