FIT5202 · Data Processing for Big Data
Machine Learning: Clustering
Week 7 of Monash FIT5202 covers unsupervised clustering with the k-Means algorithm: initialise k centroids, assign each point to the nearest centroid (by Euclidean distance), update each centroid to its cluster mean, and iterate to convergence. It also covers choosing k (the elbow method) and how k-Means is parallelised in Spark by sharing per-cluster sums and counts across processors. Tracing a k-Means iteration and computing a combined centroid are common written-response items.
What this chapter covers
- 01Clustering = unsupervised grouping of similar objects (similar within, dissimilar between clusters)
- 02Euclidean distance d(a,b) = √Σ(aᵢ − bᵢ)² as the similarity measure
- 03k-Means: initialise k centroids, assign to nearest, update to cluster mean, iterate
- 04Convergence: stop when no point changes cluster (stable memberships)
- 05Choosing k (the elbow method)
- 06Parallel k-Means (data parallelism): share per-cluster sums and counts to form a global centroid
- 07New global centroid = total sums / total counts across processors; data does not move
- 08Result-parallel k-Means: each processor owns a cluster, so memberships (and data) can move
One full k-Means iteration in one dimension
- +1Assignment: put each point with the nearer centroid. 2→C1 (|2−3|=1 < 13); 3→C1; 8→C1 (|8−3|=5 < |8−15|=7); 10→C2 (|10−3|=7 > |10−15|=5); 15→C2; 18→C2. So C1 = {2, 3, 8}, C2 = {10, 15, 18}.
- +1Update: set each centroid to its cluster mean. m₁ = (2+3+8)/3 = 13/3 ≈ 4.33; m₂ = (10+15+18)/3 = 43/3 ≈ 14.33.
- +1Re-assign with the new centroids: 2, 3, 8 are all closer to 4.33 (8: |8−4.33| = 3.67 < |8−14.33| = 6.33); 10 is closer to 14.33 (|10−4.33| = 5.67 > |10−14.33| = 4.33); 15, 18 → C2.
- +1No point changed cluster between the two assignments, so the algorithm has converged and we stop.
- +1Result: C1 = {2, 3, 8} with centroid ≈ 4.33, and C2 = {10, 15, 18} with centroid ≈ 14.33.
Key terms
- Clustering
- Unsupervised learning that groups objects so items in a cluster are similar and items in different clusters are dissimilar; there are no target labels.
- Euclidean distance
- The straight-line distance d(a,b) = √Σ(aᵢ − bᵢ)² between two points; in one dimension it reduces to |a − b|. k-Means uses it to find the nearest centroid.
- Centroid
- The mean of the points currently assigned to a cluster; k-Means updates each centroid to this mean every iteration.
- k-Means
- An iterative clustering algorithm: guess k centroids, assign each point to the nearest, recompute centroids as cluster means, and repeat until memberships stop changing.
- Elbow method
- A heuristic for choosing k: plot the within-cluster error against k and pick the 'elbow' where extra clusters stop reducing error much.
- Parallel k-Means (data parallelism)
- Partition the data across processors; each computes per-cluster sums and counts, which are shared so the new global centroid = total sums / total counts. The data itself does not move.
Machine Learning: Clustering FAQ
How does k-Means decide a point's cluster?
It assigns each point to the cluster whose centroid is closest by Euclidean distance. In one dimension that is just the smallest |x − centroid|. After all points are assigned, each centroid moves to the mean of its members, and the process repeats until no point switches cluster.
When does k-Means stop?
When an iteration produces no change in cluster membership (equivalently, the centroids stop moving). That is the convergence condition. In practice a maximum-iterations cap or a small movement tolerance is also used to guarantee termination.
How is k-Means parallelised in Spark without moving the data?
With data parallelism: the data stays partitioned across processors, each processor computes the sum and count of points per cluster on its own partition, and those partial sums and counts are combined so the new global centroid = total sums / total counts. Only small aggregates cross the network, not the data.
Can AI help me trace a k-Means example?
Yes. Sia can build the distance table, do the assign-and-update steps, and check convergence with you, and it can generate a fresh dataset at your level. It explains the method and checks your reasoning; it does not complete graded work, and Monash academic-integrity rules apply.
Exam move
Drill the assign-update loop until it is mechanical: build a small |x − centroid| table, assign to the nearest, recompute each centroid as the mean, and check whether memberships changed. Practise the one-dimensional case first, then the parallel-centroid combine (total sums / total counts) that Spark uses. Note that Week 7 is taught largely through the Week-12 recap, so lean on that material on Moodle, and keep the elbow method for choosing k in mind. Ask Sia for extra datasets to trace through SWOTVAC.
Working through Machine Learning: Clustering in FIT5202? Sia is AskSia’s AI Information Technology tutor — ask any FIT5202 Machine Learning: Clustering question and get a clear, step-by-step explanation grounded in how FIT5202 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
