COMP5318 — Applied Machine Learning
Week 10: Clustering
Clustering is unsupervised learning: there are no labels, only data, and the goal is to discover groups of similar items. This week works through four families of clustering algorithms — partitional K-means, model-based GMM with EM, hierarchical (agglomerative/divisive) clustering, and density-based DBSCAN — and finishes with internal and external ways to evaluate cluster quality.
Course materials
Week 10 surveys clustering as a family of related algorithms rather than a single method. Read the slides in order — distance measures first, then K-means, then GMM, hierarchical, DBSCAN, evaluation — and try to identify, for each algorithm, the assumptions about cluster shape and the parameters that must be specified up front.
| File | What you should learn from it |
|---|---|
| ml10.pdf | Clustering definition and applications; Euclidean / Manhattan / cosine distance; centroid vs medoid; distance between clusters (single, complete, average link); K-means algorithm and sensitivity to initialisation; K-means++; GMM clustering and the EM intuition; agglomerative and divisive hierarchical clustering and dendrograms; DBSCAN with Eps and MinPts, core / border / noise points; clustering evaluation with cohesion, separation, silhouette coefficient, and the elbow method. |
What clustering is and how we measure similarity
Clustering partitions a set of unlabelled examples into groups so that items in the same cluster are similar to each other and items in different clusters are dissimilar. Everything downstream depends on how we define "similar" — i.e. on the choice of distance measure.
An unsupervised task. Given a set of input vectors and (often) a desired number of clusters \(k\), produce a grouping with high cohesion (small intra-cluster distances) and high separation (large inter-cluster distances).
Distances between points
Euclidean: \(D(A,B) = \sqrt{\sum_i (a_i - b_i)^2}\). Manhattan: \(D(A,B) = \sum_i |a_i - b_i|\). Cosine similarity: \(\cos(A,B) = \frac{A\cdot B}{\|A\|\,\|B\|}\); high cosine = small angle = similar.
Centroid vs medoid
For a cluster of \(N\) points, the centroid is the mean \(\tfrac{1}{N}\sum_i p_i\) — usually not an actual point. The medoid is the most centrally located actual data point.
Single link (MIN)
Distance between two clusters = the smallest pairwise distance across them. Sensitive to chains of close points.
Complete link (MAX)
Distance = the largest pairwise distance. Tends to produce compact, tight clusters.
Average link
Distance = the average pairwise distance between elements of the two clusters. A compromise between single and complete link.
K-means: the workhorse partitional algorithm
K-means is the most widely used clustering algorithm. It requires \(k\) to be specified in advance, then iteratively refines \(k\) centroids so that each point is assigned to its closest centroid.
1. Choose \(k\) initial centroids (typically random data points). 2. Assign every example to the cluster of the closest centroid. 3. Recompute each centroid as the mean of its assigned points. 4. Repeat steps 2–3 until centroids stop changing (or until very few points change cluster).
Sum of Squared Error (SSE)
K-means minimises \(\text{SSE} = \sum_{i=1}^k \sum_{x\in K_i} d(c_i, x)^2\). Different random initialisations give different local minima, so the standard recipe is to run K-means many times and keep the run with the smallest SSE.
K-means++ initialisation
Pick the first centroid uniformly at random. For each subsequent centroid, sample a point with probability proportional to the square of its distance to the nearest already-chosen centroid. Tends to spread centroids out, reducing the chance of poor local minima.
Complexity
\(O(n\,k\,i\,d)\): \(n\) points, \(k\) clusters, \(i\) iterations, \(d\) attributes. Most of the convergence happens in the first few iterations.
Empty clusters
If a cluster ends up empty, restart that centroid — e.g. the point furthest from any current centroid, or a point from the cluster with the highest SSE.
Where K-means fails
Non-spherical clusters, clusters with very different sizes or densities, and data with outliers. K-means implicitly assumes equally-sized round clusters.
Gaussian Mixture Models and the EM algorithm
A GMM is a probabilistic clustering model that assumes the data was generated by a mixture of \(k\) Gaussian distributions, one per cluster. Instead of a hard assignment, each point has a probability of belonging to each cluster.
For each point: first pick cluster \(j\) with probability \(w_j\) (mixing weight, \(\sum_j w_j = 1\)), then sample the point from \(\mathcal{N}(\mu_j, \sigma_j^2)\). The unknowns are the means, variances (or covariance matrices) and mixing weights.
E-step (Expectation)
Given current parameters, compute the responsibility \(P(\text{cluster } j \mid x_i, \theta) = \dfrac{w_j\,P(x_i\mid\theta_j)}{\sum_{j'} w_{j'}\,P(x_i\mid\theta_{j'})}\). This is the soft assignment of each point to each cluster.
M-step (Maximization)
Re-estimate each cluster's parameters using the responsibilities as weights: \(\mu_j = \dfrac{\sum_i x_i\,P(j\mid x_i)}{\sum_i P(j\mid x_i)}\). Update \(\sigma_j\) and \(w_j\) similarly.
GMM vs K-means
K-means' assign step \(\leftrightarrow\) GMM's E-step (crisp vs soft). K-means' update step \(\leftrightarrow\) GMM's M-step (centroid vs distribution parameters).
Elliptical clusters
With full covariance matrices, GMM can fit elliptical or rotated clusters, whereas K-means can only produce roughly spherical Voronoi cells.
Convergence
EM monotonically increases the data log-likelihood. It still finds local optima, so multiple restarts are common.
Hierarchical clustering: dendrograms instead of \(k\)
Hierarchical clustering produces a nested family of clusterings rather than a single partition. It is visualised as a dendrogram — a tree that records each merge or split.
Agglomerative (bottom-up)
Start with each point as its own cluster. Repeatedly merge the two closest clusters until a single cluster remains. The choice of inter-cluster distance (single / complete / average / Ward's) defines the variant.
Divisive (top-down)
Start with all points in one cluster, recursively split clusters until each point is alone. Less common in practice; can be implemented via a minimum spanning tree.
No \(k\) up front
You can "cut" the dendrogram at any height to recover the clustering with that many clusters.
Ward's method
Distance between two clusters = the increase in SSE when they are merged. Tends to produce roughly equal-sized clusters; sensitive to outliers.
Complexity
Time \(O(n^3)\), space \(O(n^2)\). Not incremental — assumes all data is available, and does not scale to very large \(n\).
DBSCAN: density-based clustering
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) defines a cluster as a connected region of high density. It can find clusters of arbitrary shape and identifies outliers as noise.
Eps is the radius of a point's neighbourhood. MinPts is the minimum number of points (including the point itself) required inside that neighbourhood for it to be considered dense.
Core point
Has at least \(\text{MinPts}\) points within distance \(\text{Eps}\). Forms the interior of a cluster.
Border point
Not core, but lies within Eps of at least one core point. Belongs to a cluster but is on its edge.
Noise point
Neither core nor border — discarded as an outlier. DBSCAN's robustness to noise is one of its main strengths.
Cluster formation
Any two core points within Eps go in the same cluster. Each border point joins the cluster of an adjacent core point.
Evaluating clustering quality
All clustering algorithms will return clusters even on random data, so we need ways to judge whether the clusters are actually meaningful.
Unsupervised (internal)
Use the data alone. Cohesion = sum of distances inside clusters; Separation = distance between cluster centroids and the overall centroid. The Silhouette coefficient \(s_i = \frac{b_i - a_i}{\max(a_i, b_i)}\) combines both into one score in \([-1, 1]\).
Supervised (external)
Compare the clustering with a known ground-truth labelling. Metrics include the Adjusted Rand Index (ARI) and Normalised Mutual Information (NMI). Used when labels are available for benchmarking.
Correlation of similarity matrices
Build a "ideal" matrix from the cluster labels (1 if same cluster, 0 otherwise) and correlate it with the data's similarity matrix. High correlation = similar items end up together.
Visual inspection
Reorder the similarity matrix so points in the same cluster are adjacent. Block-diagonal structure indicates good clustering.
Elbow method for \(k\)
Plot SSE (or another internal score) against \(k\). Look for a "knee" where the curve flattens — a good trade-off between \(k\) and within-cluster cohesion.
Study questions to answer before moving on
Five items have pairwise distances given in the lecture table; with initial centroids \(A\) and \(B\), assign \(C, D, E\) to clusters in the first epoch of K-means.
\(C\): \(d(C,A)=7,\,d(C,B)=3\) ⇒ cluster 2. \(D\): \(d(D,A)=10,\,d(D,B)=4\) ⇒ cluster 2. \(E\): \(d(E,A)=1,\,d(E,B)=6\) ⇒ cluster 1.
End of epoch 1: \(\{A, E\}\) and \(\{B, C, D\}\).
Given the lecture's 5-point distance matrix and parameters \(\text{Eps}=1\), \(\text{MinPts}=2\), label every point as core / border / noise and list the resulting clusters.
Neighbourhoods: \(N(A)=\{A,B\}\), \(N(B)=\{B,A\}\), \(N(C)=\{C\}\), \(N(D)=\{D,E\}\), \(N(E)=\{E,D\}\). With \(\text{MinPts}\ge 2\), \(A, B, D, E\) are core; \(C\) is noise (no neighbour within Eps). Clusters: \(\{A,B\}\) and \(\{D,E\}\).
You have a 2D dataset shaped like two interlocking moons, with a small amount of background noise. Which clustering algorithm would you choose — K-means, GMM, agglomerative with average link, or DBSCAN — and why?
DBSCAN. Both K-means and GMM assume convex (spherical or elliptical) clusters and cannot recover crescent shapes. Agglomerative with average link is also poor for elongated, curved clusters. DBSCAN follows density along the moons regardless of shape and labels the background as noise.
Chapter quizzes
Self-test and math questions for this week are in the Quiz Hub (practice or exam mode).