← All notes · ML revision (DA5400)

L13: Introduction to Clustering — Partitioning Data & Motivation for K-Means

Source: https://www.youtube.com/watch?v=A3UNtCuMm7Y (≈17 min)

Timestamped outline

1. Motivation

• So far the course covered representation learning: PCA and kernel PCA.
• Take 2-D data that sits in a few separate groups. PCA finds the direction of maximum variance and projects every point onto that line.
• The projection keeps most of the variance, but it misses something: inside the subspace the points are still grouped together. They are not spread evenly along the line.
• Clustering asks: given data points, how do we find this group (cluster) structure?

2. Problem statement

• Data: x₁, …, xₙ ∈ ℝᵈ
• Goal: partition the data into K clusters (also called groups, partitions or "boxes").
• Example: x₁…x₅ into 3 boxes. One choice is {x₁,x₂,x₅}, {x₃}, {x₄}. Another is {x₁,x₄}, {x₂}, {x₃,x₅}. There are many valid choices.
• Counting: each point can go into any of K boxes, so there are Kⁿ assignments (3⁵ = 243 here). This is an upper bound because it counts assignments that leave boxes empty, but the true count still grows exponentially.
• So we need a performance measure that scores each partition.

3. Notation: cluster indicators

• Each point xᵢ gets a cluster indicator zᵢ ∈ {1, …, K}.
• zᵢ = k means "xᵢ is in cluster k". For example, if x₁₀ goes in box 4, then z₁₀ = 4.
• Choosing (z₁, …, zₙ) is the same as choosing a partition.
• We want a function f(z₁, …, zₙ; x₁, …, xₙ) that tells us how good that partition is.

4. The objective (goodness of a partition)

Intuition: a good cluster is homogeneous, meaning its points look alike. One way to measure this is how spread out the points are around the cluster's centre.

• If every point in a cluster is identical, each distance to the centre is 0.
• If the points are far apart, the total distance is large.

Objective:

$$ f(z_1,\dots,z_n) = \sum_{i=1}^{n} \lVert x_i - \mu_{z_i} \rVert_2^2 $$

Here μ_{zᵢ} is the mean of the cluster that xᵢ is assigned to.

Cluster mean, written with indicators:

$$ \mu_k = \frac{\sum_{i=1}^{n} \mathbb{1}(z_i = k)\, x_i}{\sum_{i=1}^{n} \mathbb{1}(z_i = k)} $$

• 𝟙(u) = 1 if u is true, otherwise 0.
• Numerator: the sum of the points in cluster k. Denominator: how many points are in cluster k.
• In words, μₖ is the average of box k.

So the objective is the total squared distance from each point to the mean of its own cluster. It is also called the within-cluster sum of squares, or the K-means objective.

5. Worked example (K = 2)

Points x₁…x₅ with z = (1, 2, 1, 1, 2):

• Cluster 1 = {x₁, x₃, x₄}, so μ₁ = (x₁ + x₃ + x₄) / 3
• Cluster 2 = {x₂, x₅}, so μ₂ = (x₂ + x₅) / 2

$$ f = \lVert x_1-\mu_1\rVert^2 + \lVert x_2-\mu_2\rVert^2 + \lVert x_3-\mu_1\rVert^2 + \lVert x_4-\mu_1\rVert^2 + \lVert x_5-\mu_2\rVert^2 $$

6. The optimisation goal

$$ \min_{z_1,\dots,z_n \in \{1,\dots,K\}} \; \sum_{i=1}^{n} \lVert x_i - \mu_{z_i} \rVert^2 $$

Brute force: list every partition, compute f for each, and keep the smallest. There are only finitely many partitions, so this works in principle, but:

• There are Kⁿ candidates. With K = 2 and n = 1000 that is about 2¹⁰⁰⁰ partitions, an astronomically large number.
• The problem is NP-hard. We don't expect any algorithm whose running time is polynomial in n and K (something like n²K³ would count as efficient).

Way forward: we can't expect to find the exact optimum efficiently, so we use a popular heuristic algorithm, K-means (Lloyd's algorithm), which the next lecture covers.

Key takeaways

1. Clustering is unsupervised learning that finds group structure, which PCA's linear subspace does not show.
2. A partition is written as indicators zᵢ ∈ {1..K}.
3. Partition quality is the sum of squared distances from points to their cluster means. Lower is better, because it means the clusters are more homogeneous.
4. Exact minimisation is NP-hard (Kⁿ partitions), which is why we need a heuristic like K-means.

Quick self-check questions

1. How many ways can 6 points be assigned to 4 clusters if empty clusters are allowed? (4⁶ = 4096)
2. Why is Kⁿ only an upper bound on the number of useful partitions?
3. If every point in a cluster is identical, what does that cluster add to the objective?
4. Write μₖ using indicator notation, from memory.
5. Why can't we just enumerate every partition when n = 1000?