I5 · Machine Learning Foundations

k-Means Clustering

k-means is an unsupervised algorithm that divides data into k clusters. It places k centres, assigns every point to its nearest centre, moves each centre to the mean of its assigned points, and repeats until the assignments stop changing. It aims to minimise the total squared distance between points and their cluster centres.

12 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

A supermarket has a million customers and no labels at all. Can a computer discover, on its own, that there are budget shoppers, weekend families and late-night snackers?

k-means is an unsupervised algorithm that divides data into k clusters. It places k centres, assigns every point to its nearest centre, moves each centre to the mean of its assigned points, and repeats until the assignments stop changing. It aims to minimise the total squared distance between points and their cluster centres.

In simple words

Drop k flags on a map of houses. Each house joins its nearest flag. Then move each flag to the middle of its houses. Repeat. Soon the flags settle in the centres of natural neighbourhoods.

Overview

  • k-means groups data into k clusters, each represented by its centre (centroid).
  • It alternates two steps: assign each point to its nearest centre, then move each centre to the mean of its points.
  • It minimises the within-cluster sum of squared distances, called inertia.
  • k must be chosen, often with the elbow method or silhouette score.
  • Results depend on the starting centres; k-means++ and several restarts (n_init) help.
  • It assumes roughly round clusters of similar size and needs scaled features.

Why it matters

Most real data has no labels. Clustering finds structure on its own: customer segments, groups of similar documents, regions of an image, or patterns to explore before any supervised model is built.

Key terms

Cluster
A group of points that are close to each other.
Centroid
The centre of a cluster: the mean of its points.
Inertia
The total squared distance from points to their centroids; lower means tighter clusters.
Elbow method
Choosing k where adding more clusters stops reducing inertia much.
Silhouette score
A measure from −1 to 1 of how well each point fits its own cluster compared with the nearest other one.
k-means++
A smart way of choosing starting centres spread apart, which improves results.

Types

k-means has several variants, and k is chosen with several types of method. Both are explained here.

1. Standard k-means (Lloyd's algorithm)

The classic assign-and-update algorithm.

  • How it works: Repeat assignment and centre updates until assignments stop changing; each iteration lowers inertia.
  • Example: Segmenting customers by annual spending and number of visits into 4 groups.
  • When to use it: Use it for compact, round clusters in moderate-sized numeric data. Run it several times (n_init) and keep the result with the lowest inertia, because a poor start can give poor clusters.

2. k-means++ initialisation

A smart way to choose starting centres (Arthur and Vassilvitskii, 2007).

  • How it works: The first centre is random; each next centre is chosen with probability proportional to its squared distance from the nearest existing centre, spreading centres out.
  • Example: scikit-learn's KMeans uses k-means++ by default.
  • When to use it: Use it always; it gives better, more consistent results than purely random starts.

3. Mini-batch k-means

A faster version that updates centres using small random batches.

  • How it works: Each step uses, say, 1,000 points instead of all of them, trading a little quality for large speed-ups.
  • Example: Clustering 10 million app users overnight.
  • When to use it: Use it for very large data sets. The clusters are usually very close to those of full k-means.

4. k-medoids and k-modes

Variants that use actual data points (medoids) or modes as centres.

  • How it works: k-medoids works with any distance and is robust to outliers; k-modes handles categorical data using matching dissimilarity.
  • Example: Choosing 5 actual warehouse locations from 200 candidate towns.
  • When to use it: Use them when centres must be real examples, distances are unusual or data is categorical.

5. Choosing k: elbow and silhouette methods

Ways to decide how many clusters to use.

  • How it works: The elbow method plots inertia against k and looks for a bend; the silhouette score (from −1 to 1) measures how well each point fits its cluster versus the next nearest.
  • Example: Inertia drops sharply until k = 4 and only slowly after, suggesting 4 segments.
  • When to use it: Use both, plus domain judgement about how many groups are useful.

Explained in detail

The algorithm step by step

First choose k and place k starting centres. Then alternate two steps. In the assignment step, every point joins the cluster of its nearest centre. In the update step, every centre moves to the average position of the points now in its cluster. Each round can only lower the total squared distance or leave it unchanged, so the process always settles, usually within a few dozen rounds. Stuart Lloyd described the method at Bell Labs in 1957, and the name k-means was coined by James MacQueen in 1967.

Choosing k

MethodHow it worksCaution
Elbow methodPlot inertia for k = 1, 2, 3…; pick the bend where improvement slowsThe elbow is often not obvious
Silhouette scorePick the k with the highest average silhouetteFavours compact, well-separated clusters
Domain knowledgeA marketing team can act on only four segmentsOften the deciding factor in practice

Limits of k-means

  • You must choose k in advance.
  • It assumes roughly round, similar-sized clusters; it fails on long, curved or nested shapes.
  • Results depend on the starting centres; scikit-learn uses k-means++ and runs several starts, keeping the best.
  • Like k-NN, it relies on distance, so features must be scaled.
  • Outliers drag centroids towards them; DBSCAN or k-medoids are more robust alternatives.

Interpreting clusters

k-means tells you which points belong together, not what the groups mean. After clustering customers, a team looks at each centroid: one cluster might spend little but visit often, another spend a lot on weekends. Giving clusters names and checking them against business knowledge is human work, and a cluster that cannot be explained may reflect noise or a quirk of the features rather than a real group. The same algorithm compresses images by grouping similar colours into k representative colours, and groups news articles or customer complaints by topic once text is turned into vectors.

Other clustering methods fill k-means' gaps. Hierarchical clustering builds a tree of merges, so you can choose the number of clusters afterwards by cutting the tree. DBSCAN groups points in dense regions and labels isolated points as noise, so it finds oddly shaped clusters and outliers without being told k. Gaussian mixture models allow oval clusters of different sizes and give each point a probability of belonging to each cluster.

How it works

  1. Scale the features.
  2. Choose a range of k values and run k-means for each.
  3. Compare inertia and silhouette scores, and think about what is useful.
  4. Fit the chosen k and inspect each centroid.
  5. Name and validate the clusters with people who know the domain.

In code

kmeans.py
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

rng = np.random.default_rng(0)
# Three made-up customer groups: (visits per month, spend per visit in hundreds of rupees)
groups = [rng.normal([4, 2], 0.5, (40, 2)), rng.normal([10, 3], 0.6, (40, 2)), rng.normal([3, 9], 0.7, (40, 2))]
X = np.vstack(groups)

for k in range(2, 7):
    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    print(f"k={k}: inertia={km.inertia_:7.1f}  silhouette={silhouette_score(X, km.labels_):.3f}")

best = KMeans(n_clusters=3, n_init=10, random_state=0).fit(X)
print("Centres:", np.round(best.cluster_centers_, 1).tolist())

Output

k=2: inertia=  786.8  silhouette=0.656
k=3: inertia=   89.6  silhouette=0.828
k=4: inertia=   71.5  silhouette=0.676
k=5: inertia=   59.8  silhouette=0.708
k=6: inertia=   49.3  silhouette=0.558
Centres: [[9.9, 3.0], [2.8, 9.0], [4.0, 2.1]]

Try it yourself

Watch k-means find groups

Place the centres, then step through the rounds. Each dot joins its nearest centre, then each centre moves to the middle of its dots.

One round of k-means

Put the steps in order.

  1. 1Place k starting centres
  2. 2Move each centre to the mean of its points
  3. 3Assign each point to its nearest centre
  4. 4Repeat until assignments stop changing

Common mistakes

  • Running k-means on unscaled features.
  • Treating clusters as real categories without checking them.
  • Using k-means for curved or nested cluster shapes.

Check yourself

Question 1

1. What does k-means need that the data does not provide?

Question 2

2. In the update step, each centre moves to…

Question 3

3. Which shape does k-means handle worst?

Summary

  • k-means groups unlabelled data into k clusters by assigning and updating centres.
  • Choose k with the elbow, silhouette and domain knowledge; scale features first.
  • Clusters must be interpreted and validated by people.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Clustering · An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani)