ML7.1 · LESSON 1 OF 6

k-means assignments

Perform a clustering update and explain dimensionality reduction, mixtures and anomaly detection.

THE IDEA

Finding groups when nobody told you the groups

In supervised learning every example comes with an answer. Here there are no answers: just 24 points on a plane. Clustering asks: can we split them into groups so that points in a group are close to each other and far from the other groups? k-means does it with a very simple picture. You choose a number k, and the algorithm keeps k special points called centroids, one per group. Each data point belongs to the group of its nearest centroid. That choice is the assignment step.

"Nearest" means smallest squared Euclidean distance: (x₁ − c₁)² + (x₂ − c₂)². We keep it squared because it avoids a square root and it is the quantity the algorithm is trying to make small. Take one dimension, centres at 0 and 10, and the point 2. Squared distance to 0 is 4, to 10 is 64. So 2 joins the centre at 0. The midpoint 5 is the boundary: points left of it go to 0, points right of it go to 10 (and a tie at exactly 5 goes to the lowest index).

P = 2A = 0B = 10

distance to A, squared: (2 - 0)^2 = 4 distance to B, squared: (2 - 10)^2 = 64 smaller: A -> P joins cluster A

Slide the point P across the boundary and watch the squared distances swap. Then move the centres: the boundary is always halfway between them.

Predict first. Centres are at 0 and 10. Which centre gets the point 6?

In two dimensions: place centroids, then assign

In two dimensions the boundary between two centroids is the straight line halfway between them, perpendicular to the segment that joins them. Click below to place up to four centroids anywhere, then press Assign. Each point takes its centroid's colour and a thin line shows who it chose. The number reported is the within-cluster sum of squares (WCSS): the sum of the squared lengths of those lines. Smaller means tighter groups.

Click the plot to drop up to 4 centroids.

Click to place centroids (up to 4), press Assign, and read the sum of squares. Undo and try other places.

With one centroid in each natural blob you get a clean split; with the best possible centre positions for these three blobs the final sum of squares is 29.126. Place two centroids in the same blob and that blob is cut in half, while two other blobs may be forced to share a centroid. The result still has a number attached to it, but a worse one. Nothing in the assignment step knows what a "natural" group is.

Two things that surprise people

k is your choice. The algorithm cannot tell you how many groups exist. Give it k = 5 on three blobs and it will happily cut them into five pieces.
A centroid can win nobody. If a centroid sits far from all the data, no point is nearer to it than to another centroid, so its cluster is empty. The next lesson shows what the algorithm does with that.

Chapter context

Unsupervised methods expose structure according to their objectives and assumptions. They do not discover a single objectively correct organization of a dataset; changing distance, dimension or density assumptions can change the result.

TRY IT YOURSELF

Part 1. Do it on the plot

Every task ticks from the real state of the plot. Click to place centroids, press Assign, and read the colours and counts.

Click the plot to drop up to 4 centroids.

To do: Click the plot to place exactly three centroids
To do: Press Assign so every point takes the colour of its nearest centroid
To do: Place the three centroids so the assignment recovers the three natural blobs exactly (8 points each)
To do: Add a centroid far from every point, press Assign, and see it get no points (an empty cluster)

Part 2. Do it in code

assign(X, C) returns, for every row of X (n points, d features), the index of the nearest row of C under squared Euclidean distance. A tie goes to the lowest index.
wcss(X, labels, C) returns the sum over all points of the squared distance to its assigned centroid C[labels[i]].
cluster_sizes(labels, k) returns an array of length k with the number of points per cluster, including zeros for empty clusters.

import numpy as np

def assign(X, C):
    # nearest centroid index for each row of X; ties -> lowest index
    pass

def wcss(X, labels, C):
    # sum of squared distances to the assigned centroid
    pass

def cluster_sizes(labels, k):
    # length-k array of counts (zeros allowed)
    pass

X = np.array([[0.0], [2.0], [8.0], [10.0]])
print(assign(X, np.array([[0.0], [10.0]])))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

With centers 0 and 10, which center gets point 2?

ACenter 10, because 2 is closer to 10 than to 0 in squared distance.BCenter 0, because the squared distance to it is 4 and to center 10 is 64.CEither center, because 2 is a tie once the distances are squared.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

J=\sum_i\|x_i-\mu_{c_i}\|^2,\quad \mu_k=\frac1{|C_k|}\sum_{i\in C_k}x_i.

For centered data X, PCA uses leading eigenvectors of $X^TX/(n-1)$ , or an equivalent SVD. Centering and feature scaling are separate choices.

For a Gaussian mixture, EM responsibilities are

r_{ik}=\frac{\pi_k\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)}.

Mixing weights pi are nonnegative and sum to one; each row of responsibilities also sums to one. Weighted sufficient-statistic updates differ from hard k-means assignments.

Worked example

With points [0,2,8,10] and starting centers [0,10], assignments are [0,2] and [8,10]. Updated means are 1 and 9. Squared errors are 1,1,1,1, totaling 4. This example gives one iteration; it does not prove that every initialization finds the best partition.

Reference code

The following example uses the Python standard library and does not call a remote service.

points, centers = [0,2,8,10], [0,10]
groups = [[x for x in points if min(range(2), key=lambda j: (x-centers[j])**2) == i] for i in range(2)]
updated = [sum(group)/len(group) for group in groups]
assert updated == [1,9]
assert sum((x-c)**2 for group,c in zip(groups,updated) for x in group) == 4

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Clusters are objective-dependent. PCA maximizes variance, which may not correspond to useful semantic structure. Anomaly detection is not the same as identifying known fraud classes.