Clustering and k-means

Every algorithm up to this point was handed the answers. A training set was a list of pairs $\left(\vec{x}^{(i)}, y^{(i)}\right)$ — the input and what the output should have been — and learning meant shrinking the distance between the two. Unsupervised learning removes the $y$. The data is now just ${\vec{x}^{(1)}, \vec{x}^{(2)}, \ldots, \vec{x}^{(m)}}$, and there is no longer a right answer to be close to.

What is left to find is structure. Clustering is the first and most direct version of that question: which of these points belong together? The algorithm below, k-means, is the one people reach for first, and its entire content is two steps repeated until nothing moves.

In one line. Guess $K$ centroids, then repeat: assign every point to its nearest centroid, and move every centroid to the mean of the points that chose it. Both halves lower the same cost $J = \frac{1}{m}\sum_i \lVert \vec{x}^{(i)} - \vec{\mu}_{c^{(i)}}\rVert^2$, so the loop always converges — but only to a local minimum, which is why you run it many times and keep the best.

Learning without labels

Two kinds of training set

The difference is visible in the notation alone, before any algorithm is written:

With labels, the same scatter of points has a line drawn through it separating crosses from circles, and "good" means the line puts them on the right sides. Without labels every point is the same colour, and "good" has to be defined by the geometry of the data itself.

What a clustering algorithm is asked for

Given the points and a number $K$, produce two things:

• an assignment $c^{(i)} \in {1, \ldots, K}$ for every example — which cluster it belongs to;
• a centroid $\vec{\mu}_k \in \mathbb{R}^{n}$ for every cluster — where that cluster sits.

There are $K^m$ possible assignments, so searching them all is hopeless even for a small dataset. What makes k-means work is that it never searches: it alternates between two steps, each of which is the exact solution to half of the problem when the other half is held fixed.

The two-step idea

Fix the centroids and the best assignment is obvious — send each point to whichever centroid is nearest. Fix the assignment and the best centroid is equally obvious — put it at the mean of its points. Neither half is a search. The algorithm is just the two of them, alternating:

Ng's slides show exactly this as two pictures: Step 1, the points take the colour of the nearest cross; Step 2, each cross slides to the middle of its own colour. Run them again and a few points on the boundary switch colour, and the crosses slide a little less. Run them again and nothing moves at all — that is convergence.

Step 1: assign each point to a centroid

Squared Euclidean distance

Each example is given the index of the closest centroid:

The square root is missing on purpose. $\sqrt{\cdot}$ is monotonically increasing, so it cannot change which centroid comes out smallest — and skipping it removes $K$ square roots per example per iteration for free.

Two worked assignments

Why the feature scales matter

$\lVert \cdot \rVert^2$ adds the squared differences of every feature with equal weight, so the feature with the largest numerical range decides the clustering almost by itself. A dataset of house sizes in square feet ($10^3$) and bedroom counts ($10^0$) is, to k-means, a dataset about size alone. Standardize the features first — the same z-score step used before gradient descent in linear regression, and for the same reason: the algorithm assumes the axes are comparable.

Step 2: move each centroid

With the assignments fixed, each centroid moves to the average of the examples that chose it:

Concretely, if cluster 1 currently holds examples 1, 5, 6 and 10, then

$$ \vec{\mu}_1 = \tfrac{1}{4}\left[\vec{x}^{(1)} + \vec{x}^{(5)} + \vec{x}^{(6)} + \vec{x}^{(10)}\right], $$

averaged per feature — the first coordinate of $\vec{\mu}_1$ is the mean of the first coordinates, and so on.

The algorithm in full

The loop

Randomly initialize K cluster centroids  μ₁, μ₂, …, μ_K

Repeat {
    # Step 1 — assign points to cluster centroids
    for i = 1 to m:
        c⁽ⁱ⁾ := index (1…K) of the centroid closest to x⁽ⁱ⁾      # argmin_k ‖x⁽ⁱ⁾ − μ_k‖²

    # Step 2 — move cluster centroids
    for k = 1 to K:
        μ_k := mean of the points assigned to cluster k
}
until no c⁽ⁱ⁾ changes

That is the whole algorithm. There is no learning rate, no gradient, and nothing to tune except $K$ and where you start.

The empty-cluster case

One edge case has no natural answer: if a centroid ends up with no points assigned to it, its mean is $0/0$. Two conventions are used — delete the cluster and continue with $K-1$, or re-initialize that centroid at a random example and carry on. Deleting is the common choice; re-initializing is the one to use when $K$ is fixed by the downstream application.

What it is actually minimising

The distortion

The two steps look like a heuristic. They are not — they are alternating minimisation of one cost, which the course calls the distortion:

The optimisation problem is to minimise $J$ over both sets of variables at once — the assignments $c^{(i)}$ and the centroids $\vec{\mu}_k$.

Why both steps lower it

The argument is short and worth making explicit, because it is the only guarantee k-means offers:

• The assign step changes only the $c^{(i)}$, with the centroids frozen. Each term of the sum involves exactly one example, so the sum is minimised term by term — and $\arg\min_k$ is precisely the choice that minimises that term. It cannot increase $J$.
• The move step changes only the centroids, with the assignments frozen. The terms belonging to one cluster add up to a convex quadratic in that cluster's centroid — the sum of squared distances in Equation 3 — and its derivative vanishes at exactly one place, the mean of those points. It cannot increase $J$ either.

So $J$ never rises. It is bounded below by zero, and there are finitely many possible assignments, so the sequence must stop — k-means always converges. Note carefully what the argument does not say: nothing here claims the value it converges to is the smallest one.

A cost that goes up means a bug. This is the practical use of the fact. If you print $J$ after every half-step and it ever increases, the implementation is wrong — usually a centroid updated with the wrong subset, or assignments computed against the new centroids and then compared with the old cost.

A real run

Thirty points in three well-separated blobs, $K = 3$, cost printed after each half-step:

Four iterations on thirty points, and the final centroids sit at $(1.79, 2.00)$, $(7.48, 3.18)$ and $(4.41, 7.98)$ — the three blobs the data was built from.

Initialization, and getting stuck

Random initialization

The standard choice is the simplest one that cannot land a centroid somewhere absurd:

• pick $K < m$;
• choose $K$ training examples at random, without replacement;
• set $\vec{\mu}_1, \ldots, \vec{\mu}_K$ to those examples.

Starting from real data points guarantees every centroid begins somewhere the data actually is, which a uniform random point in space does not.

Local optima are real

The convergence argument says $J$ stops falling; it says nothing about where. Different starts genuinely end in different places, and the bad ones are visibly bad — one blob split across two centroids while two other blobs share the third.

Running the earlier dataset from eight different random starts:

One start in eight was stuck. That is the whole reason for the next section — and note that nothing in the run reports the failure: the bad run converges just as cleanly as the good ones, and its final $J$ is the only evidence that anything went wrong.

The fix: restart and keep the best

Because $J$ is computable, the failure is detectable, and the remedy is to run the whole algorithm many times and keep the winner:

For i = 1 to 100 {                      # typically 50–1000 restarts
    randomly initialize k-means         # K random training examples
    run k-means to convergence          # get c⁽¹⁾…c⁽ᵐ⁾ and μ₁…μ_K
    compute the distortion  J(c⁽¹⁾,…,c⁽ᵐ⁾, μ₁,…,μ_K)
}
Pick the set of clusters with the lowest J

Fifty restarts is usually plenty; a thousand costs little on a small dataset and buys insurance on a hard one. The cost of a restart is one full run, and runs are cheap — the example above converged in four iterations.

Choosing $K$

Nothing so far says how many clusters there should be. Because the data has no labels, there is often no single right answer — Ng's own slide shows the same scatter cut convincingly into two clusters or into four, and both readings are defensible.

The elbow method

Run k-means for a range of $K$, plot the best distortion against $K$, and look for the point where the curve stops dropping steeply and flattens out:

The method is honest about its own weakness: on real data the curve is often a smooth slide with no bend at all, and then it tells you nothing. The right $K$ is frequently ambiguous.

Why you cannot just minimise $J$

The obvious idea — try every $K$ and keep the one with the lowest distortion — always picks the largest $K$ you allow. Adding a centroid can only reduce the distortion, and at $K = m$ every point is its own cluster and $J = 0$. Figure 8 shows it happening: $J$ keeps falling past the elbow, all the way down to $0.2412$ at $K = 8$, and none of that fall means anything.

Never choose $K$ to minimise $J$. $J$ is the right tool for comparing restarts at the same $K$, and the wrong tool for comparing different $K$.

Choosing for the downstream purpose

The usable answer is that clustering is nearly always a means to something else, so let the something else decide. Ng's example is t-shirt sizing: cluster customers by height and weight, and $K = 3$ gives S/M/L while $K = 5$ gives XS/S/M/L/XL. Neither is statistically better — the trade is between a better fit per customer and the cost of manufacturing five sizes. That is a business decision, and the data cannot make it.

The same shape of argument decides $K$ for image compression, another standard use: cluster the pixel colours and store each pixel as the index of its centroid. $K$ is then literally the size of the palette, and it is chosen against a file-size budget and how bad the result is allowed to look.

The general rule. Evaluate the clustering by how well it serves the task it feeds, not by how tight the clusters are. Where there is no downstream task, the elbow and a look at the clusters is all there is — and that is a legitimate reason to be unsure.

Where this goes next

k-means answers "which points belong together". The second unsupervised algorithm answers a different question about the same unlabelled data: which points do not belong at all?

• Anomaly detection fits a model of what normal data looks like — a Gaussian per feature — and flags any new example whose probability $p(\vec{x})$ falls below a threshold $\epsilon$. It is unsupervised in the same sense as k-means (the training data has no labels), but it is usually evaluated with a small number of labelled anomalies, which makes tuning $\epsilon$ a genuinely different exercise from choosing $K$.
• The two share the assumption that geometry means something: k-means uses distance to a centroid, anomaly detection uses probability under a fitted density. Both are only as good as the feature scaling underneath them.

Backwards from here: linear regression has the feature-scaling machinery this note assumes, and model development has the train/cv/test discipline that the next note needs in order to pick $\epsilon$.