K-means clustering

In supervised learning, each training example is a pair (features, label), and the model learns to predict the label. In unsupervised learning you get the features only. There is nothing to predict; the task is to understand how the data is laid out in feature space. The lecture names the two main families: clustering (this week: k-means) and dimensionality reduction (week 10: PCA). Between the two extremes sits semi-supervised learning, where only some points have labels.

The pipeline on slide 7: take raw data (say, images), extract a feature vector for each item, then group the vectors into clusters. The clusters you get can only be as good as the features: if two kinds of objects look the same in feature space, no clustering algorithm can separate them.

Uses (slides 6, 12–13 and Géron): customer segmentation for marketing, image compression and color segmentation, grouping genes or motifs in bioinformatics, land-use maps from satellite data, grouping insurance policy holders, and as a preprocessing step for other models. The professor's example of that last use is the computer-vision bag of visual words (07:59): cluster small image-patch features, treat each cluster center as a "visual word", and describe each image by a histogram of how often each word occurs. That histogram then becomes the input to a classifier.

What makes a clustering good?

Slide 14 gives the two criteria, and the professor asked you to remember them:

• High intra-cluster similarity: each cluster is compact; its points are close to one another.
• Low inter-cluster similarity: different clusters are far apart.

Beyond that, quality is application-dependent and "ultimately subjective" (slide 14): the same data can be grouped several sensible ways. As an aside, the professor pointed out that LDA (linear discriminant analysis, a supervised linear classifier you can look up) uses exactly these two quantities to find a separating direction. A clustering algorithm has the same goal without the labels.

What a clustering algorithm should handle

Slide 15 lists the requirements. The professor stressed three: scalability (millions of points), noise and outliers (real data is never clean), and above all high dimensionality. Recall the curse of dimensionality from week 4: the data needed to cover a space grows exponentially with its dimension, so even millions of 2048-dimensional image features cover that space only thinly. "How can your algorithm deal with a large-scale data set in a high-dimensional space? This is the fundamental challenge" (20:03). The rest: mixed attribute types, clusters of arbitrary shape, needing little domain knowledge to set parameters, not depending on the order of the input, respecting user constraints, and producing clusters a person can interpret.

Families of clustering algorithms

A partitioning algorithm (slide 17) is given k and must find the partition into k clusters that optimizes a criterion. Trying every partition would find the global optimum, but the number of partitions explodes, so in practice you use heuristics. Two classics: k-means represents each cluster by its center (the mean, which usually isn't a data point), and k-medoids represents each cluster by one of its actual points (the medoid).

Imagine you were handed the cluster centers. Labeling the points would be easy: send each one to its closest center. Now imagine you were handed the labels instead. Finding the centers would be easy too: average the points with each label. k-means has neither, so it guesses the centers and then alternates these two easy steps (Géron's framing).

Input: the number of clusters and unlabeled points (slide 29: no bias feature here).

1. Initialize: pick starting centroids at random. (Section 4 explains how.)
2. Assignment step: for each point , set to the index of the centroid closest to .
3. Update step: for each cluster , move to the mean of the points assigned to it.
4. Repeat steps 2–3 until the assignments stop changing (or a maximum number of iterations is reached).

The professor's way to think about the assignment: it's a pseudo-label (25:32). Once every point has a pseudo-label, the update step is just "compute each class's mean", as if the labels were real. Then the labels are recomputed from the new means.

Each assignment step splits the space into Voronoi cells around the centroids, exactly like the 1-NN cells of week 4, except that the "training points" are now the centroids. With the boundary is the perpendicular bisector of the two centroids. This is the picture the professor told you to remember (26:59). Slides 19–28 animate it on 30 points; here is the same process on 6 points you can check by hand.

1. Iteration 1. C and E are nearer ; A, B, D, F are nearer . New means: and .
2. Iteration 2. F switches to cluster 1 (11.25 < 18). Cluster 1 = {C, E, F}, mean ; cluster 2 = {A, B, D}, mean .
3. Iteration 3. C switches to cluster 2 (4 < 5). Cluster 1 = {E, F}, mean ; cluster 2 = {A, B, C, D}, mean .
4. Iteration 4. Every point keeps its cluster, so the centroids don't move: converged with . Checking all 31 ways to split six points into two groups confirms this is the best possible.

Two details the slides skip. Ties: if a point is equally close to two centroids, pick one by a fixed rule (say, the lower index) so the algorithm can't flip back and forth. Empty clusters: if no point is assigned to some centroid, its mean is undefined. Common fixes are to drop that cluster or to re-seed it at the point farthest from its centroid. That's one reason slide 36 insists on , and why starting centroids are usually taken from the data.

The two steps aren't arbitrary. Both are exact minimizations of one cost function, called the distortion (slide 32), the within-cluster SSE (slide 44), or the inertia (Géron, scikit-learn):

Alternating optimization

has two kinds of unknowns: the assignments and the centroids . Minimizing over both at once is hard (SSBD §22.2: finding the exact optimum is NP-hard in general). But fixing one kind makes the other easy. That is alternating optimization, and it is exactly k-means:

• Fix , minimize over : each term involves only point 's own choice, so pick the nearest centroid for each point. That's the assignment step.
• Fix , minimize over : is a convex quadratic in each . Set the gradient to zero:

Why J never increases

Each step solves its own subproblem exactly, so it can't do worse than the solution it started from:

• Assignment step: each point either keeps its centroid or switches to a strictly closer one. Each term stays the same or shrinks.
• Update step: the mean is the minimizer for its cluster, so moving a centroid there can't raise that cluster's sum.

So goes down or stays put at every half-step. And since points can be split into groups in only finitely many ways, and no partition can come back once has dropped below its value, the algorithm must stop after a finite number of iterations (Géron: "it will not oscillate forever"). Usually it takes only a few.

"K-means is very sensitive to initialization" (34:46). Because is not convex, k-means can converge to a local minimum: a clustering that no single assign or update step can improve, but that is worse than the best one. Where you end up depends on where you start.

How to start. The slide 30 version places centroids at random points in space. If they land far from the data, a centroid can end up with no points or get stuck. Slide 36's better default: choose training examples at random and put the centroids on them. That guarantees the starting centroids lie on the data.

1. Assign. Squared distances to A / E: A 0 / 25, B 2 / 13, C 10 / 5, D 8 / 5, E 25 / 0, F 50 / 5. So {A, B} vs {C, D, E, F}, and .
2. Update. and

   so .
3. Assign again. The closest calls are C (6.5 vs 3.31) and D (4.5 vs 2.81), and both stay with . Nothing changes, so k-means stops at , worse than the 9.5 found in Section 2.

This isn't a rare fluke. Of the 15 possible pairs of data points as starting centroids, 5 (AB, AC, AD, AE, BD) end in this local minimum. That's one start in three.

The fix: restart and keep the best

Slide 38: run k-means many times (the slide says 100) from different random starts, compute for each result, and keep the clustering with the lowest . Comparing is fair here because every run uses the same data and the same . scikit-learn does this automatically: n_init sets the number of runs and the lowest-inertia run is kept (Géron).

The local minimum above happened because both starting centroids landed in the same natural group. k-means++ (Arthur & Vassilvitskii, 2007) makes that unlikely by choosing starting centers that tend to be far apart. Only the initialization changes; afterwards it is ordinary k-means.

1. Choose the first center uniformly at random from the data points.
2. For every data point , compute : its distance to the nearest center chosen so far.
3. Choose the next center at random from the data points, picking with probability proportional to :

The far points E and F get 85% of the probability. The bad local minimum happens only if A or D is drawn: . With a uniform second pick it would be . (Averaged over all six possible first picks, the bad outcome drops from 33% for two uniformly random data points to 27% for k-means++; the gain is larger with more clusters. On the 60-point data in the figure above, k-means++ reached the best answer in 1,000 of 1,000 runs, versus 899 for uniformly random data points.) This is why scikit-learn uses k-means++ by default.

k-means needs as input, and "with no prior knowledge it's hard to define K" (37:37). Slide 40's example shows why: two clear columns of points could be 2 clusters, or 4 if each column has an upper and a lower half. Domain knowledge beats any formula (T-shirt sizes S/M/L is a decision about the business, not about the data). Without it, there are two standard tools.

The elbow method

Run k-means (with restarts) for and plot the final against . J always falls as K grows, because more centroids are always at least as close to every point. Look for the elbow: the K after which adding clusters stops buying much. On the 60 points from Section 1:

The silhouette score (Géron)

The elbow is often vague. Géron's more precise alternative scores each point by how much closer it is to its own cluster than to the next-nearest one:

Slide 45 sums k-means up. Strengths: simple, iterative, and the user controls K. Weaknesses: very sensitive to the initial centroids, and hard to guess the right K. The deeper limitation is built into the objective. J measures squared distance to a single center, so k-means looks for round (spherical) clusters of similar size, and every boundary is a straight perpendicular bisector between two centroids. When the true groups look different, k-means still lowers J, but the result is the wrong grouping.

• Elongated or oddly shaped clusters (left): use a Gaussian mixture model (week 9), which fits an ellipse per cluster, or a density-based method like DBSCAN.
• Different sizes or densities (right): same remedies. Géron's ladybug example is the image version: with too few colors, the small red ladybug gets no cluster of its own.
• Feature scale: as with k-NN, squared Euclidean distance lets large-unit features dominate. Standardize features first (Géron's tip; Bishop standardizes before running k-means too).
• Outliers: the mean gets pulled toward outliers. k-medoids (slide 17) is more robust because its center must be an actual data point.
• No natural clusters (slide 31, T-shirt sizing): height and weight form one continuous cloud. k-means still splits it into K pieces (here S/M/L). That can be useful, but the professor's point (28:36) is that no algorithm can discover clusters that aren't there.

Computational cost

• Assignment step: points × centroids distances, each costing , so .
• Update step: each point is added into one mean: .
• Total: for iterations, linear in every factor. is usually small (Géron: k-means is "generally one of the fastest clustering algorithms", though pathological inputs can need very many iterations).

Compare k-NN: each query costs . k-means does comparable work for all points at once, but per iteration and against only centroids.

Speed-ups (the lecture's "think about it"):

• Elkan's accelerated k-means: use the triangle inequality and keep upper and lower bounds on point-to-centroid distances, so most distance computations can be skipped. It's scikit-learn's default.
• Mini-batch k-means (Sculley 2010): update the centroids from a small random batch at each step. It's typically 3–4× faster and works on data that doesn't fit in memory, at the price of a slightly higher J.
• Tree structures (Bishop §9.1) and the hashing ideas from week 4 can speed up the nearest-centroid search when is large.

Both have a "k", both use Euclidean distance, and both produce Voronoi-cell pictures. They solve different problems.

The one real connection: once k-means is trained, labeling a new point is 1-NN classification with the centroids as the stored "training set". That's how KMeans.predict works in scikit-learn.