COMP4318 · Machine Learning and Data Mining
Clustering
Week 10 covers unsupervised clustering: k-means (and choosing k), Gaussian mixture models with EM, hierarchical/agglomerative clustering and the dendrogram, and density-based clustering (DBSCAN). The exam usually asks you to run a k-means iteration by hand, or to classify DBSCAN points as core/border/noise, or to read a dendrogram. The homework quiz (h10) and tutorial (t10) drill the same by hand.
What this chapter covers
- 01Clustering = unsupervised grouping: high intra-cluster cohesion, low inter-cluster similarity
- 02k-means: assign each point to the nearest centroid, recompute centroids, repeat until stable; SSE compares clusterings
- 03Choosing k and the sensitivity to initial centroids; k-means++ spreads the initial centroids out
- 04GMM with EM: soft assignment in the E-step, re-estimate μ and σ in the M-step; allows elliptical clusters
- 05Hierarchical: agglomerative (merge closest) vs divisive; single/complete/average/Ward link; the dendrogram
- 06DBSCAN: parameters Eps and MinPts; core / border / noise points; finds arbitrary shapes and resists noise
- 07Inter-cluster distance: centroid, single link (MIN), complete link (MAX), average link
- 08Evaluation: cohesion, separation, the silhouette coefficient; every algorithm finds clusters even in random data — validate
One iteration of k-means with Manhattan distance
- +1Manhattan distance of each point to c1 = (1,1) and c2 = (5,4): A → 0 vs 7; B → 1 vs 6; C → 7 vs 0; D → 9 vs 2. Assign each to its nearer centroid.
- +1Resulting clusters: Cluster 1 = {A, B} (nearer c1); Cluster 2 = {C, D} (nearer c2).
- +1Recompute centroid 1 as the mean of its points: c1 = ((1+2)/2, (1+1)/2) = (1.5, 1).
- +1Recompute centroid 2: c2 = ((5+6)/2, (4+5)/2) = (5.5, 4.5). One iteration is complete; you would repeat until the centroids stop moving.
Key terms
- k-means
- A partitional clusterer: pick k centroids, assign each point to the nearest, recompute centroids as cluster means, and repeat until stable; sensitive to the initial centroids.
- SSE (within-cluster)
- Sum of squared distances of points to their centroid, SSE = Σ_k Σ_{x∈Kk} d(cₖ, x)²; used to compare clusterings (lower is better).
- GMM / EM
- A model-based clusterer assuming a mixture of k Gaussians; the EM algorithm alternates a soft-assignment E-step with an M-step re-estimating μ and σ, giving 'soft', possibly elliptical clusters.
- Dendrogram
- The tree produced by agglomerative (bottom-up) hierarchical clustering; cutting it at a height gives a chosen number of clusters.
- DBSCAN
- Density-based clustering with parameters Eps (radius) and MinPts; classifies points as core, border or noise, finds arbitrary shapes and resists noise, but struggles with widely varying density.
- Silhouette coefficient
- An internal validation measure combining cohesion and separation to score how well each point fits its cluster.
Clustering FAQ
How do I choose the number of clusters k?
There is no single answer; common approaches are the elbow method on the SSE-versus-k curve (look for the bend), or a validation measure like the silhouette coefficient. Remember every algorithm will return k clusters even in random data, so validate that the structure is real rather than imposed.
When should I use DBSCAN instead of k-means?
Use DBSCAN when clusters are non-spherical or you expect noise/outliers, since it finds arbitrary shapes and labels sparse points as noise, and you do not need to pre-specify k. Prefer k-means for roughly spherical, similarly sized clusters. DBSCAN struggles when clusters have very different densities or the data are high-dimensional, and it is sensitive to Eps and MinPts.
What's the difference between k-means and a Gaussian mixture model?
k-means makes a hard assignment of each point to its nearest centroid and implicitly assumes spherical clusters. A GMM models the data as a mixture of Gaussians and gives each point a soft (probabilistic) membership via EM, so it can capture elliptical clusters of different sizes. k-means is essentially a hard-assignment special case.
How is the clustering question marked in the exam?
Method by method: computing each point's distance to the centroids, forming the clusters, and recomputing the centroids each earn marks in a k-means iteration; for DBSCAN, correctly labelling core/border/noise from Eps and MinPts; for hierarchical, the correct merge order and dendrogram. Show your distance working.
Exam move
Rehearse a full k-means iteration by hand with a stated distance: distances to every centroid, assignment, then recompute centroids as means — and be ready to say why the result depends on the initial centroids. Practise DBSCAN labelling (core needs ≥ MinPts within Eps; border is within a core's neighbourhood; everything else is noise) and reading an agglomerative dendrogram from a distance matrix. Know the GMM/EM idea (soft assignment) versus k-means (hard). When a k-means step drifts, ask Sia to recompute the assignments and centroids with fresh points.
Working through Clustering in COMP4318? Sia is AskSia’s AI Machine Learning tutor — ask any COMP4318 Clustering question and get a clear, step-by-step explanation grounded in how COMP4318 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
