← All notes · ML revision (DA5400)

L16: Nature of Clusters Produced by K-means (Voronoi Regions & Geometry)

Source: https://www.youtube.com/watch?v=EY03QHaaSBY (≈23 min) Previous: L13 · L14 · L15

The lecture works in 2-D (with K = 2 and then K = 3) and mentions kernel K-means only as a pointer. Section 6 does the full ℝᵈ geometry: hyperplane offsets, a convexity proof, matrix form for the cells, the kernel K-means distance formula, its link to spectral clustering, and a tested demo on concentric circles.

Timestamped outline

1. Setup: what convergence tells us about geometry

At convergence (L15), no point wants to move. So every x assigned to cluster k satisfies

$$ \lVert x-\mu_k\rVert^2 \le \lVert x-\mu_l\rVert^2 \quad \text{for every other } l . $$

Everything in this lecture comes from unpacking that inequality.

2. K = 2: the boundary is a line (a hyperplane in general)

Expand both sides of ‖x − μ₁‖² ≤ ‖x − μ₂‖²:

$$ \lVert x\rVert^2+\lVert\mu_1\rVert^2-2x^\top\mu_1 \;\le\; \lVert x\rVert^2+\lVert\mu_2\rVert^2-2x^\top\mu_2 . $$

The ‖x‖² terms cancel, leaving:

$$ \boxed{\,x^\top(\mu_2-\mu_1)\;\le\;\frac{\lVert\mu_2\rVert^2-\lVert\mu_1\rVert^2}{2}\,} $$

This has the form xᵀw ≤ b, which is linear in x.

Reading the picture (in 2-D):

1. The vector w = μ₂ − μ₁ points from μ₁ towards μ₂.
2. The points with xᵀw = 0 form a line through the origin, perpendicular to w.
3. The right-hand side b = (‖μ₂‖² − ‖μ₁‖²)/2 shifts that line parallel to itself. The sign of b depends on which mean is farther from the origin.
4. Which point lies on the shifted line? The midpoint m = (μ₁ + μ₂)/2:

$$ m^\top(\mu_2-\mu_1)=\tfrac12(\mu_1+\mu_2)^\top(\mu_2-\mu_1)=\tfrac12\big(\lVert\mu_2\rVert^2-\lVert\mu_1\rVert^2\big)=b .\;\checkmark $$

So the boundary passes through the midpoint and is perpendicular to μ₂ − μ₁. It is the perpendicular bisector of the segment from μ₁ to μ₂.

• Cluster 1 is the side containing μ₁; cluster 2 is the other side.
• With K = 2, K-means always splits the data with a straight line. This follows directly from the convergence condition.

3. K = 3 and general K: intersections of half-spaces

• For a point to be in cluster 1, it must be closer to μ₁ than to μ₂ and closer to μ₁ than to μ₃.
• Each condition is one half-space, bounded by a perpendicular bisector. Cluster 1's region is the intersection of the two.
• Do the same for every pair (μ₁μ₂, μ₁μ₃, μ₂μ₃). The plane is split into 3 regions.
• General K: each cluster's region is the intersection of K − 1 half-spaces, one for each of the other means.
• Half-space: one side of a line (2-D) or of a hyperplane (ℝᵈ).
• These regions are Voronoi regions (Voronoi cells). Lloyd's algorithm effectively searches for a good Voronoi partition of the space, and each final cluster lives inside one cell.
• The 2-D pictures are only for visualisation. The algebra is identical in ℝᵈ.

4. Failure case: concentric circles

• Data: one ring of points inside another. The natural clusters are "inner ring" and "outer ring".
• Lloyd's algorithm with K = 2 still converges, but its two clusters must be separated by a straight line. So it slices both rings in half somewhere. The exact angle depends on the data.
• Takeaway: if the true clusters don't have a Voronoi-like (convex, linearly separable) structure, K-means cannot recover them, whatever the initialization.

5. The fix (pointers only, not covered in the course)

• Same idea as kernel PCA: map the data to a higher-dimensional feature space. Clusters that aren't Voronoi-separable in the original space can become separable there.
• Run Lloyd's algorithm in that feature space, using the kernel trick so you never compute the map explicitly. This is kernel K-means.
• Kernel K-means is closely related to spectral clustering: use eigenvectors of the kernel matrix as a new representation, then cluster. This links back to PCA.

6. Going further: ℝᵈ geometry and kernel K-means

This section goes beyond the video.

6.1 The bisector hyperplane in ℝᵈ, made precise

For means μₖ, μₗ ∈ ℝᵈ, the boundary is

$$ H_{kl}=\{x\in\mathbb{R}^d:\; w_{kl}^\top x=b_{kl}\},\quad w_{kl}=\mu_l-\mu_k,\quad b_{kl}=\tfrac12\big(\lVert\mu_l\rVert^2-\lVert\mu_k\rVert^2\big). $$

• This is a (d−1)-dimensional flat: a line in ℝ², a plane in ℝ³, a hyperplane in general.

• Distance from the origin: |b_{kl}| / ‖w_{kl}‖.

• Signed distance of a point x to the boundary:

  $$ s(x)=\frac{w_{kl}^\top x-b_{kl}}{\lVert w_{kl}\rVert}=\frac{\lVert x-\mu_k\rVert^2-\lVert x-\mu_l\rVert^2}{2\lVert\mu_l-\mu_k\rVert}. $$

  s < 0 means x is closer to μₖ. The second form follows from the expansion in §2, and it shows that the margin is a difference of squared distances, scaled by the gap between the centres.

• Reflection check: the mirror image of μₖ across H_{kl} is exactly μₗ. That's the defining property of a perpendicular bisector.

6.2 Voronoi cells in matrix form

Stack the K − 1 inequalities for cluster k:

$$ V_k=\{x:\;A_kx\le c_k\},\qquad A_k=\begin{bmatrix}(\mu_l-\mu_k)^\top\end{bmatrix}_{l\ne k}\in\mathbb{R}^{(K-1)\times d},\quad (c_k)_l=\tfrac12\big(\lVert\mu_l\rVert^2-\lVert\mu_k\rVert^2\big). $$

This is a polyhedron: the same kind of object as the feasible region of a linear program.

Equivalently, define K linear scores

$$ g_k(x)=\mu_k^\top x-\tfrac12\lVert\mu_k\rVert^2 . $$

Then the assignment is simply argmaxₖ gₖ(x), because ‖x − μₖ‖² = ‖x‖² − 2gₖ(x) and ‖x‖² is the same for every k. So K-means assignment is a linear classifier with weights μₖ and bias −½‖μₖ‖². It has the same form as the decision rule of Gaussian LDA with a shared spherical covariance and equal priors.

6.3 Proof that every Voronoi cell is convex (in any d)

Half-spaces are convex. Suppose wᵀx ≤ b and wᵀy ≤ b, and λ ∈ [0, 1]. Then

$$ w^\top(\lambda x+(1-\lambda)y)=\lambda w^\top x+(1-\lambda)w^\top y\le\lambda b+(1-\lambda)b=b . $$

Intersections of convex sets are convex. If a point is in every set, so is every convex combination. So Vₖ, an intersection of K − 1 half-spaces, is convex. ∎

Consequences:

• A K-means cluster can never be ring-shaped, crescent-shaped or "wrap around" another cluster.
• Cells on the outside of the arrangement are unbounded. They extend to infinity, so points very far from all the data still get assigned somewhere.
• The data in cluster k lies inside Vₖ. So the convex hulls of the clusters don't overlap.

6.4 At convergence: centroidal Voronoi tessellation

At a fixed point of Lloyd's algorithm, two things hold together:

1. Each cluster is the set of data points in the Voronoi cell of its centre (the assignment step).
2. Each centre is the mean of the data points in its cell (the update step).

A Voronoi partition whose generators are also the centroids of their own cells is a centroidal Voronoi tessellation (CVT). Lloyd's algorithm was originally invented, for signal quantisation, as a way to compute these. That's why K-means is also called vector quantisation.

6.5 Hidden assumptions behind straight bisectors

The boundary is the midpoint bisector, no matter how big or spread out each cluster is. That builds in some implicit assumptions:

Fixes:

• Standardise the features first.
• Use a Mahalanobis distance, ‖x − μ‖²_Σ⁻¹. If Σ is shared across clusters, the boundaries stay linear, but they are no longer perpendicular bisectors.
• Use per-cluster covariances. The boundaries become quadratic. This leads to Gaussian mixture models.

6.6 Concentric circles: an explicit lift that works

Inner ring radius r₁, outer ring radius r₂. Add one feature:

$$ \phi(x_1,x_2)=(x_1,\;x_2,\;x_1^2+x_2^2)\in\mathbb{R}^3 . $$

In ℝ³ the rings sit at different "heights" (r₁² and r₂²). The plane x₃ = (r₁² + r₂²)/2 separates them, so they are now in different Voronoi cells. Lloyd's algorithm in ℝ³ gives two clusters that look like an inner disc and an outer ring when mapped back to ℝ².

Geometrically: a plane in φ-space is a set aᵀx + c‖x‖² = b, which is a circle in ℝ². Linear in the lifted space means curved in the original space. This is the same principle as kernel PCA.

6.7 Kernel K-means: the distance without ever computing φ

Let φ: ℝᵈ → ℋ, with kernel k(x, y) = ⟨φ(x), φ(y)⟩ and kernel matrix G_{ij} = k(xᵢ, xⱼ). The cluster mean in feature space is μₖ^φ = (1/nₖ) Σ_{j∈Cₖ} φ(xⱼ), which you can't compute directly. But the distance only needs inner products:

$$ \begin{aligned} \lVert\phi(x_i)-\mu_k^\phi\rVert^2 &=\langle\phi(x_i),\phi(x_i)\rangle-\frac{2}{n_k}\sum_{j\in C_k}\langle\phi(x_i),\phi(x_j)\rangle+\frac1{n_k^2}\sum_{j,l\in C_k}\langle\phi(x_j),\phi(x_l)\rangle\\[2pt] &=\underbrace{G_{ii}}_{\text{self}}\;-\;\underbrace{\frac{2}{n_k}\sum_{j\in C_k}G_{ij}}_{\text{avg. similarity to cluster}}\;+\;\underbrace{\frac{1}{n_k^2}\sum_{j,l\in C_k}G_{jl}}_{\text{cluster tightness}} . \end{aligned} $$

Kernel Lloyd's algorithm: repeat "assign each i to argminₖ of the expression above" until nothing changes.

• Step 1 (computing means) disappears. The means are implicit in the cluster sets.
• The L15 convergence proof still holds word for word: Fact 1 is true in any inner-product space.
• Cost: O(n²) memory and time per iteration for G. That's the price of the kernel trick.

Sanity check: with the linear kernel G = XXᵀ, this formula reduces exactly to ordinary K-means.

6.8 Link to spectral clustering (why eigenvectors show up)

Let H ∈ ℝ^{n×K} be the normalised indicator matrix: H_{ik} = 1/√nₖ if i ∈ Cₖ, otherwise 0. Then HᵀH = I_K. Summing the formula in §6.7 over the points in each cluster gives

$$ F_\phi=\sum_k\sum_{i\in C_k}\lVert\phi(x_i)-\mu_k^\phi\rVert^2=\operatorname{tr}(G)-\operatorname{tr}(H^\top G H). $$

Minimising F_φ is the same as maximising tr(HᵀGH) over these discrete H. That's NP-hard (see L13). The standard relaxation: drop the "discrete indicator" requirement and keep only HᵀH = I. Then, by the Rayleigh–Ritz / Ky Fan theorem (the same result behind PCA),

$$ \max_{H^\top H=I}\operatorname{tr}(H^\top GH)=\sum_{k=1}^{K}\lambda_k(G),\quad H^\star=\text{top-}K\text{ eigenvectors of }G . $$

So you compute the top K eigenvectors of the (normalised) kernel or affinity matrix, use their rows as a new K-dimensional representation of each point, and run ordinary K-means on those rows. That is spectral clustering, and it's essentially kernel PCA followed by K-means. This is the connection the lecturer hints at.

6.9 Tested demo: plain vs. lifted vs. kernel K-means

import numpy as np
rng = np.random.default_rng(0)
def ring(r, m):
    t = rng.uniform(0, 2*np.pi, m)
    return np.c_[r*np.cos(t), r*np.sin(t)] + rng.normal(0, 0.1, (m, 2))
X = np.vstack([ring(1, 150), ring(3, 150)]); y = np.r_[np.zeros(150), np.ones(150)]

def kmeans(X, K, seed=0, iters=100):
    r = np.random.default_rng(seed)
    M = X[r.choice(len(X), K, replace=False)]
    for _ in range(iters):
        z = ((X[:, None] - M[None])**2).sum(-1).argmin(1)
        M = np.stack([X[z == k].mean(0) for k in range(K)])
    return z

def kernel_kmeans(G, K, seed=0, iters=100):
    n = len(G); z = np.random.default_rng(seed).integers(K, size=n)
    for _ in range(iters):
        D = np.empty((n, K))
        for k in range(K):
            idx = z == k; nk = idx.sum()
            D[:, k] = np.diag(G) - 2*G[:, idx].sum(1)/nk + G[np.ix_(idx, idx)].sum()/nk**2
        z_new = D.argmin(1)
        if np.array_equal(z_new, z): break
        z = z_new
    return z

acc = lambda z: max((z == y).mean(), (z != y).mean())
print("plain k-means     :", acc(kmeans(X, 2)))
Phi = np.c_[X, (X**2).sum(1)]                    # explicit lift (x1, x2, x1^2+x2^2)
print("k-means on lift   :", acc(kmeans(Phi, 2)))
r2 = (X**2).sum(1); G = X @ X.T + np.outer(r2, r2)   # k(x,y)=xᵀy+‖x‖²‖y‖² = φ(x)ᵀφ(y)
print("kernel k-means    :", max(acc(kernel_kmeans(G, 2, s)) for s in range(5)))

Output when I ran it:

plain k-means     : 0.557   ← a straight line slices both rings (≈ coin flip)
k-means on lift   : 1.0     ← the rings separate in R^3
kernel k-means    : 1.0     ← same result via the kernel trick, never forming φ

Note: a generic degree-2 polynomial kernel (xᵀy + 1)² scored only 0.76 on the same data. It adds x₁², x₂² and x₁x₂ as separate features, which dilutes the radius signal. Choosing the kernel matters. The RBF kernel is the usual default in practice, but it has a bandwidth to tune.

Key takeaways

1. At convergence, every point is closer to its own mean, and that condition is linear in x.
2. K = 2: the boundary is the perpendicular bisector hyperplane of μ₁μ₂, passing through the midpoint with normal μ₂ − μ₁.
3. General K: each cluster lies in an intersection of K − 1 half-spaces. That is a convex Voronoi cell, and the converged result is a centroidal Voronoi tessellation.
4. K-means assignment is a linear classifier with scores μₖᵀx − ½‖μₖ‖².
5. Non-convex clusters (rings, moons) cannot be recovered. Lifting to a feature space or using kernel K-means can fix this, and relaxing kernel K-means gives spectral clustering.

Self-check questions

1. For μ₁ = (0, 0) and μ₂ = (4, 2), write the boundary equation and check that (2, 1) lies on it. (4x₁ + 2x₂ = 10.)
2. Show that the reflection of μₖ across H_{kl} is μₗ.
3. Prove that the intersection of two convex sets is convex. Why does that make K-means clusters convex?
4. With K = 4 in ℝ³, how many half-spaces bound each cell, and what shape are the boundaries? (3 half-spaces each; the boundaries are planes.)
5. Derive the kernel K-means distance formula yourself. Then check that the linear kernel gives back the ordinary formula.
6. A tight cluster of 10 points sits next to a wide cluster of 1000. Where does the bisector fall, and what goes wrong?
7. Why does a plane in φ-space for φ(x) = (x, ‖x‖²) correspond to a circle in ℝ²?