Home / MLT / Week 3

Week 3 · K-means: grouping without labels

Official syllabus line: Unsupervised Learning - Clustering - K-means/Kernel K-means

About 80 minQuiz 1 material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 1 (distance), MLF week 2 (derivative equals zero). MLT week 2 for the kernel version at the end.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine a city needing three new pizza shops. We don't know the neighborhoods, only where houses are. We drop three shops, then each house goes to its nearest shop. Next, each shop moves to the center of its customer crowd. We repeat this, moving shops and re-assigning customers, until nothing changes.
This game is called k-means clustering. Its goal is to group data points without labels. We want to make sure every point is as close as possible to its group's center. Lloyd's algorithm does this: first, we assign each point to its nearest center, then we update each center to be the mean of its assigned points, and repeat until stable.
Let's try a simple example with points on a line: one, two, three, ten, eleven, twelve. We start with two centers. Points one, two, three initially group with the first center, and the rest with the second. We update the first center to be the average of one, two, and three, making it two. The second center becomes the average of its points, eleven. Then, points are reassigned.
Remember, k-means always stops in finite steps, reaching a local minimum, not necessarily the best overall. It doesn't find the global optimum. K-means++ helps by picking spread-out starting centers using squared distance. You cannot choose 'k' just by minimizing the objective; use the elbow method. Keep practicing the steps!

The one-minute story

Think of it like this

A city wants to open 3 pizza shops so that everybody has a shop nearby. Nobody has told you the neighbourhoods; you just have a map of where houses are.

Try this game:

Drop 3 shops anywhere on the map.
Every house walks to its nearest shop. Now each shop has a crowd of customers.
Move each shop to the centre of its own crowd (the average of the houses that chose it).
Houses may now be closer to a different shop. Repeat steps 2 and 3.

After a few rounds nothing changes any more: every shop sits in the middle of its crowd and every house is at its nearest shop. You have just clustered the houses into 3 groups without anyone labelling them. That is k-means.

By the end of this week you can:

state the k-means objective and run Lloyd's algorithm by hand;
prove (in words) that it always converges, and say what it converges to;
seed it well with k-means++;
explain how kernel k-means handles non-round clusters.

Words you need

Cluster - a group of points that are similar to each other.
Centroid (or centre, mean) $\boldsymbol\mu_k$ - the average of the points in cluster $k$ .
$k$ - the number of clusters, chosen by you before you start.
Objective $F$ - the total squared distance from every point to its own centroid. Smaller is a tighter clustering.
Lloyd's algorithm - the "assign, then update" loop.
Local optimum - a result that cannot be improved by small changes, but might not be the best overall.

Idea 1: What is k-means trying to do?

You have points $\mathbf x_1,\dots,\mathbf x_n$ and want to split them into $k$ groups. Let $z_i\in\{1,\dots,k\}$ record which group point $i$ belongs to, and $\boldsymbol\mu_1,\dots,\boldsymbol\mu_k$ be the group centres. The k-means objective is

F(z,\boldsymbol\mu)=\sum_{i=1}^n\big\|\mathbf x_i-\boldsymbol\mu_{z_i}\big\|^2

the sum of squared distances from each point to its own centre. Finding the global minimum over all possible splits is NP-hard (practically impossible for big data), so we use a clever heuristic.

Idea 2: Lloyd's algorithm

The idea

Lloyd's algorithm (what people usually mean by "k-means")

Initialise $k$ centres (random points, or smarter: see k-means++).
Assignment step. Send every point to its nearest centre: $z_i=\arg\min_k\|\mathbf x_i-\boldsymbol\mu_k\|^2$ .
Update step. Move every centre to the mean of the points assigned to it: $\boldsymbol\mu_k=\frac1{|C_k|}\sum_{i\in C_k}\mathbf x_i$ .
Repeat 2 and 3 until the assignments stop changing.

Why it always stops (and where it stops)

Each step solves a small problem exactly:

Assignment step: if the centres are fixed, the best choice of $z_i$ for each point is clearly the nearest centre. So $F$ cannot go up.
Update step: if the groups are fixed, the best centre for a group minimises $\sum(\mathbf x_i-\boldsymbol\mu)^2$ . Setting the derivative to zero (MLF week 2) gives $\boldsymbol\mu=$ the mean. So $F$ cannot go up again.

So $F$ never increases. And there are only finitely many ways to split $n$ points into $k$ groups, so the algorithm cannot keep improving forever: it must stop after a finite number of steps.

Watch out - real exam trap

Be precise about what is guaranteed. Lloyd's algorithm always converges, in finitely many steps, to a local minimum of $F$ . It is not guaranteed to reach the global minimum, and different starting centres can give different final answers.

Solved example: 1. Running Lloyd's algorithm by hand

Question. Cluster the 1-D points $1,\,2,\,3,\,10,\,11,\,12$ into $k=2$ groups, starting with centres $\mu_1=1$ and $\mu_2=2$ . Track the objective.

Solution.

Round 1, assign. $1\to\mu_1$ (distance 0). $2\to\mu_2$ . $3$ : distance to $\mu_1$ is 2, to $\mu_2$ is 1, so $\mu_2$ . $10,11,12\to\mu_2$ . Groups: $\{1\}$ and $\{2,3,10,11,12\}$ . Objective with the current centres: $0+(0+1+64+81+100)=\mathbf{246}$ .

Round 1, update. $\mu_1=1$ . $\mu_2=\frac{2+3+10+11+12}5=7.6$ . Objective now: $0+(31.36+21.16+5.76+11.56+19.36)=\mathbf{89.2}$ .

Round 2, assign. $2$ : distance 1 to $\mu_1$ , 5.6 to $\mu_2\Rightarrow\mu_1$ . $3$ : 2 vs 4.6 $\Rightarrow\mu_1$ . $10$ : 9 vs 2.4 $\Rightarrow\mu_2$ . Groups: $\{1,2,3\}$ and $\{10,11,12\}$ . Objective (centres $1$ and $7.6$ ): $5+36.68=\mathbf{41.68}$ .

Round 2, update. $\mu_1=2$ , $\mu_2=11$ . Objective: $(1+0+1)+(1+0+1)=\mathbf{4}$ .

Round 3. Assignments do not change, so we stop. Final centres $(2,\,11)$ , $F=4$ .

The sequence $246\to89.2\to41.68\to4$ only goes down, exactly as the argument promised. A start like $\mu_1=1,\mu_2=2$ is poor, yet the algorithm recovers here. With three clusters or a nastier layout it might not.

Idea 3: Starting well, k-means++

A bad start can trap Lloyd's algorithm (two centres inside the same blob, an empty blob left). k-means++ chooses starting centres that are spread out:

The idea

Pick the first centre uniformly at random from the data.
For every point $\mathbf x$ , compute $D(\mathbf x)$ , its distance to the nearest centre already chosen.
Pick the next centre from the data with probability proportional to $D(\mathbf x)^2$ .
Repeat until you have $k$ centres. Then run Lloyd's.

Far-away points get a much bigger chance (squared distance), so new centres tend to land in uncovered regions. Guarantee: the expected objective is at most $O(\log k)$ times the best possible, specifically $E[F]\le8(\ln k+2)\,F_{\text{opt}}$ .

Solved example: 2. A k-means++ probability

Question. The first centre is at $0$ . The remaining data points are at $1,\,2,\,3$ (on a line). With what probability is each chosen as the second centre?

Solution. $D=1,\,2,\,3$ , so $D^2=1,\,4,\,9$ , summing to $14$ . Probabilities: $\frac1{14},\;\frac4{14},\;\frac9{14}$ . The farthest point is $9$ times as likely as the nearest.

Idea 4: Choosing $k$ , and what k-means assumes

$F$ always decreases when you add clusters, reaching $0$ at $k=n$ (every point its own centre). So you cannot just pick the smallest $F$ .
The elbow method: plot $F$ against $k$ and choose the "bend" where extra clusters stop helping much.
k-means works best when clusters are round, similar in size and well separated. Long thin or nested shapes (like rings) break it.
It is sensitive to scale (standardise features) and to outliers (a mean is dragged by extremes).
The centre is the mean because of the squared distance. Using absolute distance would give the median (k-medians).

Link to the next week: k-means is the hard-assignment limit of a Gaussian mixture model fitted with EM. Every point belongs to one cluster, instead of having fractional memberships.

Idea 5: Kernel k-means

For ring-shaped clusters, run k-means in the lifted space of MLT week 2. We cannot compute the centre $\boldsymbol\mu_C=\frac1{|C|}\sum_{j\in C}\phi(\mathbf x_j)$ explicitly, but we do not need to: the squared distance from $\phi(\mathbf x)$ to it only needs kernel values:

\|\phi(\mathbf x)-\boldsymbol\mu_C\|^2=k(\mathbf x,\mathbf x)-\frac2{|C|}\sum_{j\in C}k(\mathbf x,\mathbf x_j)+\frac1{|C|^2}\sum_{j\in C}\sum_{l\in C}k(\mathbf x_j,\mathbf x_l)

Then Lloyd's algorithm proceeds as before with this distance: assign each point to the cluster giving the smallest value; there is no explicit centre to update.

Solved example: 3. The formula agrees with ordinary k-means

Question. With the linear kernel $k(x,y)=xy$ , cluster $C=\{1,3\}$ and point $x=2$ , compute the kernel distance.

Solution. $k(2,2)=4$ . $\frac2{2}\big(k(2,1)+k(2,3)\big)=2+6=8$ . $\frac1{4}\big(1+3+3+9\big)=4$ . Total $4-8+4=\mathbf0$ . Indeed the mean of $\{1,3\}$ is $2$ , the point itself. ✓

Your turn

Your turn: 1. One full round

Points on a line: $0,\,2,\,4,\,10$ . Centres start at $1$ and $9$ . Do one assignment and one update. Then give the objective.

Need a hint?

Each point goes to the nearer centre.

Show the full solution

$0\to1$ , $2\to1$ , $4\to1$ (distance 3 vs 5), $10\to9$ . New centres: $\frac{0+2+4}3=2$ and $10$ . Objective: $4+0+4+0=\mathbf8$ .

Your turn: 2. 2-D

Points $A=(0,0)$ , $B=(2,0)$ , $C=(0,2)$ , $D=(10,10)$ with centres $(0,0)$ and $(10,10)$ . Assign, update, and give the objective.

Need a hint?

Distances from each point to both centres.

Show the full solution

$A,B,C\to(0,0)$ ; $D\to(10,10)$ . New centres: $(\frac23,\frac23)$ and $(10,10)$ . Objective: $A$ : $2\cdot\frac49=\frac89$ ; $B$ : $(\frac43)^2+(\frac23)^2=\frac{20}9$ ; $C$ : $\frac{20}9$ ; $D$ : 0. Total $=\frac{48}9=\frac{16}3\approx5.33$ .

Your turn: 3. k-means++ choice

First centre at $0$ ; other points at $1,\,3,\,6$ . What is the probability that $6$ is the second centre?

Need a hint?

$D^2$ for each.

Show the full solution

$D^2=1,\,9,\,36$ , total $46$ . Probability for $6$ : $\frac{36}{46}\approx0.783$ .

Your turn: 4. Objective as

k

grows

A data set of 100 points has $F=500$ for $k=1$ . What is $F$ for $k=100$ ? Can $F$ increase when you go from $k=3$ to $k=4$ (at the optimum)?

Need a hint?

What happens when every point is its own cluster?

Show the full solution

$F=0$ at $k=100$ . The optimal $F$ cannot increase when $k$ grows (you could simply leave a cluster unused), so it is non-increasing. (Lloyd's algorithm itself may land in a worse local minimum for $k=4$ than a good one for $k=3$ , but the best possible value never goes up.)

Your turn: 5. True or false

(a) Lloyd's algorithm always converges in a finite number of steps. (b) It always finds the globally best clustering. (c) The centroid minimising the sum of squared distances is the mean. (d) With the same data and $k$ , different initialisations can give different results.

Need a hint?

Re-read the "why it stops" box.

Show the full solution

(a) True. (b) False, only a local minimum. (c) True. (d) True.

Exam radar

MLT Quiz 1 summaries mention convergence in 22 papers, K-means in 10, k-means++ in 10, initialisation in 9, k-means objective in 8, Lloyd's algorithm in 7, sum of squared distances in 7, and Euclidean distance in 10. End Term papers also revisit K-Means in 12.

Typical items: "does Lloyd's algorithm always converge? to what?" (finite steps, local minimum); a small run of one assignment and update; "k-means++ picks the next centre with probability proportional to ..." (squared distance); and kernel k-means distance computations.

Watch out - real exam trap

Converges $\ne$ globally optimal.
k-means++ probability is proportional to $D(\mathbf x)^2$ (squared), not $D(\mathbf x)$ .
The update uses the mean (squared distance). With absolute distance it would be the median.
$F$ computed after assignment and after update are different numbers; read which one is asked.
More clusters always lowers $F$ ; don't choose $k$ by minimising $F$ .

Quick quiz

In Lloyd's algorithm, the update step moves each centre to...

the nearest data point
the mean of the points assigned to it
the median of all points
a random location

The mean minimises the sum of squared distances within a cluster.

Lloyd's algorithm is guaranteed to...

find the global optimum
converge in a finite number of steps to a local optimum
never change the centres
find the best k

The objective never increases and there are finitely many assignments.

In k-means++, the next centre is chosen with probability proportional to...

the distance D
D squared
1 / D
the same for every point

Squared distance to the nearest chosen centre favours far-away points.

Select all TRUE statements. (select all that apply)

Increasing k never increases the optimal objective.
k-means is sensitive to the scale of the features.
k-means works well for ring-shaped clusters.
The assignment step uses the median.

Rings need kernel k-means, and assignment uses the nearest centre.

Recap

Remember this

Objective $F=\sum\|\mathbf x_i-\boldsymbol\mu_{z_i}\|^2$ . Lloyd: assign to nearest centre, then move centres to means, repeat.
$F$ never increases, finitely many partitions, so it converges in finite steps to a local minimum (not necessarily global).
k-means++: next centre $\propto D(\mathbf x)^2$ ; $E[F]\le8(\ln k+2)F_{\text{opt}}$ .
$F\to0$ as $k\to n$ : use the elbow, not minimum $F$ . Assumes round, similar-sized clusters.
Kernel k-means: distance via kernel values; handles non-linear shapes.

Formulas to keep

$F=\sum_i\|\mathbf x_i-\boldsymbol\mu_{z_i}\|^2$ ; assign $z_i=\arg\min_k\|\mathbf x_i-\boldsymbol\mu_k\|^2$ ; update $\boldsymbol\mu_k=\text{mean}(C_k)$
k-means++: $P(\mathbf x)=D(\mathbf x)^2/\sum D^2$ ; $E[F]\le8(\ln k+2)F_{opt}$
Kernel distance: $k(\mathbf x,\mathbf x)-\frac2{|C|}\sum_jk(\mathbf x,\mathbf x_j)+\frac1{|C|^2}\sum_{j,l}k(\mathbf x_j,\mathbf x_l)$

Connected weeks (learn them together)

MLF week 2 - Slopes, change and the steepest way up: K-means rests on one calculus fact: the average is the number that makes squared distances smallest.
MLP week 12 - Unsupervised learning in sklearn: K-means in scikit-learn.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 34 real questions on this week All Quiz 1 papers

Week 3 · K-means: grouping without labels

The one-minute story

Words you need

Idea 1: What is k-means trying to do?

Idea 2: Lloyd's algorithm

Why it always stops (and where it stops)

Idea 3: Starting well, k-means++

Idea 4: Choosing kkk, and what k-means assumes

Idea 5: Kernel k-means

Your turn

Exam radar

Quick quiz

Recap

Practise with real exam questions

Idea 4: Choosing $k$ , and what k-means assumes