Mansori

K-Means: Finding Groups Without Labels

About this lesson, for parents and teachers

Nobody told the computer what the groups are. There are no labels at all. Drop a few centroids and watch k-means discover the structure by itself.

Ages 15–18 · about 8 minutes · builds on AI Guesses by Looking at Neighbours

Try this

  1. Tap the map to drop 3 centroids (the stars), then press Step. Every point takes the colour of its nearest centroid.
  2. Press Step again: each centroid jumps to the average of its points. Keep going until it says converged.
  3. Count the blobs, set k to match, and try to reach the best possible inertia.
  4. Drag two centroids into the same blob and run it. K-means gets stuck in a worse answer. Why?

How it works

K-means is an unsupervised learning algorithm: it gets data with no labels and has to find groups, called clusters, by itself. You choose k, the number of clusters, and give it k starting points called centroids. Then it repeats two simple steps, known as Lloyd's algorithm, which this lesson runs for real.

Assign: each point measures its distance to every centroid and joins the nearest one. Update: each centroid moves to the mean (the average x and average y) of the points that joined it. The coloured background shows which centroid is nearest to every spot on the map, a pattern called a Voronoi diagram. When an assign step changes nobody's group, the algorithm has converged.

How good is a clustering? K-means tries to make the inertia small: the sum of squared distances from every point to its own centroid, Σ |x − μ|². Both steps can only lower it or keep it the same, which is why k-means always stops. But it stops at a local minimum. A bad start, such as two centroids in one blob, can leave it stuck with a worse answer.

Engineers handle this in two ways. k-means++ picks starting centroids that are spread far apart, and the algorithm is run several times keeping the lowest inertia. The "best" number shown here was found exactly that way, with 30 restarts in your browser. Choosing k is harder: inertia always drops as k rises, so people look for an "elbow" where adding clusters stops helping much.

Where engineers use this

K-means groups customers by shopping habits, compresses images by reducing them to k colours, organises news stories and documents, and is used to build the codebooks inside some speech and image models.

Words to know

Unsupervised learning
Machine learning on data with no labels, where the algorithm must find structure by itself.
Centroid
The centre of a cluster: the average position of all its points.
Inertia
The total squared distance from each point to its cluster's centroid. Lower means tighter clusters.
Local minimum
A solution no small step can improve, even though a better one exists elsewhere.

Talk about it

Goal: Drop centroids, step the algorithm, and watch unlabeled points organize into clusters.

  • If you set k to 120, one per point, the inertia is 0. Is that a good clustering? Why not?
  • What kinds of data might have no labels but still have useful groups?
  • K-means uses straight-line distance. What shapes of clusters might it struggle with?

Without a screen: Scatter 30 coins or buttons on a table in a few loose piles. Place 3 cups anywhere. Move every coin next to its nearest cup, then move each cup to the middle of its coins. Repeat until nothing changes. Try again with a different cup start.

Curriculum links: CSTA K-12 3A-DA-12 (create computational models that represent relationships in data); AI4K12 Big Idea 3 (Learning); Common Core HSS-ID (interpreting categorical and quantitative data)

Questions

What is k-means clustering in simple terms?
K-means splits data into k groups. It places k centre points, assigns every data point to its nearest centre, moves each centre to the average of its group, and repeats until the groups stop changing.

What is the difference between supervised and unsupervised learning?
Supervised learning trains on examples that come with the right answers, such as photos labelled cat or dog. Unsupervised learning gets no answers and must find patterns, such as clusters, on its own.

How do you choose k in k-means?
There is no perfect rule. A common method is to plot inertia against k and look for an elbow where the curve flattens, or to use a score such as the silhouette coefficient. Knowing the problem often matters most.