Unsupervised Learning
K-Means Clustering
Clustering without labels is a loop of two operations that each improve one thing while holding the other fixed — and it always converges, whether or not it converged to anything sensible.
Clustering without labels is a loop of two operations that each improve one thing while holding the other fixed — and it always converges, whether or not it converged to anything sensible.
Stage 1 of 3: Unlabelled data
K-Means clustering with k=3. Iteration 0, phase recentre. Inertia is 676.39.
- Data point
No classes, no ground truth. Just positions. Whatever structure gets found has to come out of the geometry alone.
Unsupervised learning without labels
When you have points in space without any ground truth labels, you can still find structure by alternating between two straightforward steps.
First, you pick random starting locations, called centroids.
Then, you repeat these two steps:
- Assign each point to the centroid nearest to it.
- Recentre each centroid to the mean of all points assigned to it.
This process is called k-means clustering.
Why it always stops
Every time you assign points, the total distance from points to their centroids (the inertia) must go down or stay the same. Every time you recentre a centroid to the mean of its points, the inertia also goes down or stays the same, because the mean is exactly the spot that minimises squared distance.
Since inertia can never drop below zero and both steps only ever reduce it, the algorithm is mathematically guaranteed to stop moving. It converges.
The trap of local minima
Convergence just means it stopped. It does not mean it found the "true" clusters.
Because k-means is deterministic once the initial seeds are placed, everything depends on where those first centroids land. If you seed two centroids inside what looks like one natural cluster, they will carve it in half. The algorithm will happily report that it converged cleanly.
This exposes the fundamental limit of unsupervised learning: it finds a mathematically stable answer, but you are the one who has to decide if it means anything.
Reference
- Assignment
- each point joins the cluster whose centre is nearest
- Update
- each centre moves to the mean of its assigned points
- Inertia
- Σ ‖xᵢ − μ(cluster of i)‖² — total squared distance to own centre
- Convergence
- guaranteed — inertia never increases, so the loop must stop
- But
- convergence is to a local minimum, which depends entirely on the start
- Choosing k
- not learned — inertia always falls as k rises, so it cannot pick k for you
Break it on purpose
Reseed until two centroids land inside the same true cluster. The algorithm converges cleanly, reports a stable inertia, and splits one real group in half while merging two others. Nothing about the run signals that it went wrong — which is why k-means is normally run several times.