K-Means Clustering

Where We Are

Every classifier so far learned from answers supplied by humans. K-Means begins unsupervised learning: the data arrives, but the labels do not.

1. The problem

Imagine customer points with two features: annual spending and visit frequency. You suspect there are three customer types, but nobody labelled them.

K-Means asks us to choose $K$, then repeatedly performs two steps.

Step A — Assign

Each point joins the nearest centre:

$c_i=\arg\min_k\lVert x_i-\mu_k\rVert^2.$

Step B — Update

Each centre moves to the mean of its assigned points:

$\mu_k=\frac{1}{|C_k|}\sum_{i\in C_k}x_i.$

Then repeat.

assign → move centres → assign again → move again → ...

2. Small numeric example

Points: 1, 2, 8, 9. Start centres at 2 and 8.

Assignment gives {1,2} and {8,9}. New centres are

$\mu_1=1.5,\qquad \mu_2=8.5.$

A second assignment does not change the groups, so the algorithm has converged.

3. What is it minimizing?

K-Means minimizes within-cluster squared distance:

$J=\sum_i\lVert x_i-\mu_{c_i}\rVert^2.$

The assignment step improves $J$ while centres are fixed. The update step improves $J$ while assignments are fixed. Therefore the objective never increases.

But it may stop at a local optimum.

4. Initialization matters

Bad starting centres can produce bad clusters. k-means++ spreads initial centres intelligently and is usually safer than arbitrary random choices.

Run K-Means several times with different initializations and keep the solution with lowest inertia.

5. Geometry assumptions

K-Means prefers roughly spherical, similarly sized clusters under Euclidean distance. It struggles with crescent shapes, different densities, severe outliers and irrelevant dimensions.

That is not a bug in implementation—it follows from the objective.

6. Feature scaling matters

If salary ranges from 20,000–2,000,000 while visit frequency ranges from 1–20, salary dominates Euclidean distance. Standardization can completely change the clustering.

7. From scratch skeleton

for _ in range(max_iter):
    dist = ((X[:, None, :] - centers[None, :, :])**2).sum(axis=2)
    labels = dist.argmin(axis=1)
    new_centers = np.stack([X[labels == k].mean(0) for k in range(K)])

Shape Check

If X has shape [N,D] and centers has [K,D], the broadcasted difference has shape [N,K,D]; summing over features produces [N,K] distances.

What to Remember

K-Means alternates assignment and mean update, minimizing within-cluster squared distance. Its clusters are hard assignments: every point belongs to exactly one group.

Next → Gaussian Mixture Models: what if a point is 70% likely to belong to one cluster and 30% to another?