Lab 10 — K-Means and Clustering

Overview of the lab

Unsupervised learning
Clustering
The K-means algorithm
Example: K-means step by step
How well does it fit the data?
Does it always work?
How many clusters? Elbow method and silhouette analysis
K-means variants: K-medians, K-medoids, K-modes, K-means++, soft K-means
Hierarchical methods: divisive and agglomerative
Cluster evaluation metrics
K-means in Python

Unsupervised learning

We have data $D = \{x_1, \dots, x_N\}$, each example a vector of features $x_i = (a_1, a_2, \dots, a_M)^T$, but no labels. A model with parameters $\{\theta_1, \dots, \theta_L\}$ is fit to the data and maps an input $x$ to an output $y$. Nobody tells us the correct $y$: the model has to discover structure in $D$ by itself.

Clustering: $y$ is categorical, the group (cluster) the example belongs to. This lab.
Dimensionality reduction: $x \in \mathbb{R}^M \Rightarrow y \in \mathbb{R}^K$ with $K < M$, a shorter description of the same example (e.g. PCA).

💡 Compare with supervised learning (KNN, Naive Bayes, decision trees): there, every training example comes with its correct label, and the model learns to reproduce it.

The problem

Clustering

Group the data so that points in the same cluster are similar (close) and points in different clusters are dissimilar (far apart).

Try it: where are the clusters?

Look at the unlabelled data first. What is the shape of each cluster? How many clusters are there? Then reveal the clusters that generated the data, and the answer K-means gives with K = 4.

The clustering problem

Given a set of data samples $x_1, \dots, x_N$,
assign the data to $K$ clusters: partitioning the dataset, also called segmentation.
$K$ may be given, or chosen automatically.

Techniques fall into:

Combinatorial techniques: work directly on the data (K-means, hierarchical clustering).
Mixture modelling: assume the data is IID (independent and identically distributed) and model the underlying probability density function (pdf), e.g. a mixture of Gaussians.
Mode seeking, also known as bump hunting: look for the peaks of the density.

Clustering techniques

We will focus on:

K-means
Gaussian mixture modelling, also called soft K-means
Hierarchical clustering: agglomerative / divisive

These techniques are used regularly, often as part of a much larger system that might include supervised learning, e.g. to discretise a continuous input to make classification easier, or to represent a pdf for a Bayes classifier.

Algorithm

K-means

A wonderfully simple algorithm:

K-means(data, K):
    initialise K cluster centres m_1, …, m_K
    repeat until done:
        assign each data point to the nearest cluster centre      # assignment step
        replace each cluster centre with the mean of the          # update step
            data points assigned to it

K-means concepts

Assume the data is 2-D and was generated from $K$ clusters.
We model the problem with $K$ prototype vectors $m_1, \dots, m_K$. We call them means, and you will see why.
We assign a data point $x$ to a cluster based on distance: $x$ goes to the closest prototype.

📐 Assignment step

\[ y = \arg\min_{k = 1 \dots K} \; \text{Distance}(x, m_k) \]

How do we define distance? Usually the Euclidean distance $\lVert x - m_k \rVert$. This is similar to nearest-neighbour classification, with the $K$ prototypes as the only "training points".

K-means update

We update each prototype using the points that were assigned to it, by taking their average / centroid / mean:

📐 Update step

\[ m'_k = \frac{1}{N_k} \sum_{x_i \text{ assigned to } k} x_i \qquad k = 1 \dots K \]

$m'_k$ is the new prototype, $N_k$ the number of points assigned to cluster $k$.

Example

Example: K-means step by step

Three true clusters, $K = 3$. The centres are initialised by randomly selecting data points, and the first choice is unlucky: two centres start in the top-left cluster and one in the right cluster. Step through the algorithm: each step is either an assignment (points take the colour of the nearest centre; the shading shows the region of each centre) or an update (each centre jumps to the mean of its points; the thin line is its path).

$K$3

Log

💡 Click on the plot to place the initial centres yourself (the first K clicks after Reset).

🎬 Video: K-means clustering: how it works (Victor Lavrenko).

Question time

How well does it fit the data?
When should we terminate? Will it always terminate?
Does it always work?
How do we tell how many clusters there are (i.e. what is $K$)?

Objective

How well does it fit the data?

K-means is a local search technique (remember hill climbing) for optimising the distortion of the data: the within-cluster scatter, i.e. how far the points are from their own centre.

📐 K-means cost (within-cluster sum of squares, WCSS)

\[ J = \sum_{k=1}^{K} \; \sum_{i:\, y_i = k} \lVert x_i - m_k \rVert^2 \]

The sum of squared distances from each point to the centre of its cluster. scikit-learn calls it inertia_.

💡 The slide writes the cost as $C = \sum_k N_k \sum_{y_i = k} \lVert x_i - m_k \rVert^2$, with an extra factor $N_k$. That version comes from The Elements of Statistical Learning, eq. (14.31). The book's authors have since listed it in their errata: without the $N_k$ "gives the correct objective for the K-means algorithm". The guarantees below hold for $J$.

How does the cost change with each iteration?

It never increases. Look at the cost curve in the example: it drops fast, then flattens. Each of the two steps can only lower $J$:

Assignment step: the centres are fixed. Moving a point to its nearest centre can only shorten its distance, so $J$ cannot go up.
Update step: the assignments are fixed. For one cluster, the point $c$ that minimises $\sum_i \lVert x_i - c \rVert^2$ is exactly the mean, because $\sum_{i} \lVert x_i - c \rVert^2 = \sum_{i} \lVert x_i - \bar{x} \rVert^2 + N \lVert c - \bar{x} \rVert^2$ and the second term is 0 only for $c = \bar{x}$. That is why the prototypes are called means.

Try it: the mean minimises the squared distances

Click (or drag) anywhere to move the candidate centre $c$ of this cluster. The dashed lines are the distances; the cost is the sum of their squares. The cross marks the mean.

When should we terminate? Will it always terminate?

Stop when no point changes its cluster: then the means do not move either, and nothing will ever change again.
K-means will converge. There are only finitely many ways to split $N$ points into $K$ groups, and $J$ never increases. So the algorithm cannot cycle forever (when it keeps the old centre on ties).
In practice you may still want to limit the number of iterations, or stop when $J$ improves by less than a small tolerance.

Pitfall

Does it always work?

Unfortunately, no. K-means finds a local minimum of $J$, and which one depends on where the centres start. It also assumes roughly round, similarly sized clusters.

Try it: local optima and random restarts

Run K-means from a random start (centres = random data points). Every run is added to the list with its final cost $J$. Some runs get stuck: one centre sits between two true clusters while two centres share one cluster. 10 restarts runs ten times and keeps the best. On the second dataset (the shapes from the slide) even the best run does not recover the true clusters.

What happened?

K-means can get stuck in local optima: effectively, the result depends on the starting condition.
How can we "fix" this? Use random restarts (remember local search?) and keep track of the best solution so far, the one with the lowest $J$. A smarter start is K-means++.
K-means will converge, but you may want to limit the iterations.
No restart helps when the clusters are not round: K-means cuts space into convex regions around the centres, so thin, long or very unequal clusters are split or merged wrongly.

Choosing K

How many clusters?

$J$ always goes down as $K$ grows. With $K = N$ every point is its own centre and $J = 0$. So we cannot just pick the $K$ with the lowest cost.

The elbow method

Plot the cost against $K$. The curve falls steeply while each new centre splits a real cluster, then flattens once the extra centres only split clusters that are already good. Choose the $K$ at the bend, the "elbow". It points to the true value of $K$ when the clusters are clear.

Silhouette analysis

For every point $i$, compare how close it is to its own cluster with how close it is to the nearest other cluster:

📐 Silhouette coefficient of point $i$

\[ s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}} \in [-1, 1] \]

$a(i)$ = mean distance from $i$ to the other points of its own cluster; $b(i)$ = mean distance from $i$ to the points of the nearest other cluster.

$s \approx 1$: well inside its cluster, far from the others. $s \approx 0$: on the border between two clusters. $s < 0$: probably in the wrong cluster.
The mean silhouette over all points scores the whole clustering. Choose the $K$ with the highest mean silhouette, and check the silhouette plot: every cluster should reach above the mean, with no negative values.

Try it: elbow and silhouette together

Three true clusters. For each $K$, K-means is run with 10 random restarts. Pick a $K$ to see the clustering and its silhouette plot: one horizontal bar per point, sorted, grouped by cluster; the dashed line is the mean.

cost J (left axis) mean silhouette (right axis)

🎬 More: silhouette analysis in scikit-learn · k-means Elbow Method and Silhouette Method · Find the number of clusters in KMeans. Silhouette score. Python code example

K-means summary

A practical algorithm, good to have in the toolbox.
Implementation: run with random restarts, keep track of the best solution found, provide (or estimate) $K$. It can be slow on big datasets: every iteration computes $N \cdot K$ distances.
You can use different distance metrics, as part of the algorithm design (see the variants below).
Speeding up K-means: faster nearest-neighbour algorithms and data structures (e.g. k-d trees).

Variants

K-means variants

The "centre" of a cluster is whatever point minimises the total distance to the cluster's points, so the right centre depends on the distance you use.

Variant	Use it when your distance is…	Centre of a cluster	Minimises
K-means	squared Euclidean	the arithmetic mean	within-cluster variance: squared deviations from the mean (not distances)
K-medians	taxicab (Manhattan, L1)	the coordinate-wise median	absolute deviations = Manhattan distances
K-medoids	any other distance	the medoid: the actual data point with the smallest total distance to the others	the sum of distances, for any distance
K-modes	dissimilarity for categorical data: the number of mismatching features	the mode (most frequent value) of each feature	total mismatches

Try it: mean, median and medoid

One cluster with an outlier. Drag the outlier (or click anywhere to move it) and watch the three centres. The mean is pulled strongly by the outlier; the median and the medoid barely move. That is why K-medians and K-medoids are more robust to outliers.

K-means++

Plain K-means picks the initial centroids at random from the data points, and this randomisation affects the final clusters. There are two ways to avoid the problem: repeat K-means (random restarts, keeping the clustering with small intra-cluster and large inter-cluster distance), or use K-means++, a smart centroid initialisation. The rest of the algorithm is the same as K-means.

📐 K-means++ initialisation

Pick the first centroid $C_1$ uniformly at random from the data points.
For every point, compute its squared distance to the nearest centroid chosen so far: \[ d_i = \min_{j = 1 \dots m} \lVert x_i - C_j \rVert^2 \] ($m$ = number of centroids already picked).
Pick the next centroid at random, choosing $x_i$ with probability $\dfrac{d_i}{\sum_j d_j}$: far-away points are likely, points next to an existing centroid are almost never chosen.
Repeat steps 2–3 until there are $K$ centroids.

❗ The slide writes $\max_j$ ("distance from the farthest centroid"). The original algorithm (Arthur & Vassilvitskii, k-means++: The Advantages of Careful Seeding, SODA 2007) uses the distance to the nearest chosen centroid, as above, and samples the next centroid with probability proportional to $d_i$ rather than taking the maximum. Always taking the farthest point is a different method (farthest-point initialisation), which is sensitive to outliers.

Try it: K-means++ seeding

Five clusters, $K = 5$. Pick the centroids one by one. The area of each point is proportional to its probability of being picked next, $d_i / \sum_j d_j$.

Soft K-means

K-means makes a hard assignment: on convergence every point belongs to exactly one cluster. It uses the L2 norm (squared Euclidean distance) between a point and its centroid.
Soft K-means / EM makes a soft assignment: every point belongs to every cluster with some probability (a responsibility). The full version, a Gaussian mixture model trained with the EM algorithm, is based on the expected probability of a point belonging to each cluster rather than on the L2 norm. It also learns each cluster's shape, so it is less limited to round clusters than K-means.

The simplest soft K-means keeps the K-means loop and replaces the hard assignment with responsibilities controlled by a stiffness $\beta$:

📐 Soft K-means

\[ r_{ik} = \frac{e^{-\beta \lVert x_i - m_k \rVert^2}}{\sum_{j} e^{-\beta \lVert x_i - m_j \rVert^2}} \qquad m_k = \frac{\sum_i r_{ik}\, x_i}{\sum_i r_{ik}} \]

Each point pulls on every centre with weight $r_{ik}$. As $\beta \to \infty$ the nearest centre gets $r = 1$ and we are back to hard K-means. As $\beta \to 0$, every point belongs equally to every cluster.

Try it: stiffness

Three overlapping clusters. The colour of each point mixes the cluster colours by its responsibilities. Lower the stiffness: the borders blur, and at very low $\beta$ all centres collapse into the overall mean. Click a point to see its responsibilities.

stiffness $\beta$1.00

🎬 Video: Soft k-Means Clustering (Bioinformatics Algorithms: An Active Learning Approach).

Hierarchical

Hierarchical methods

Recall K-means: input = $K$ and a measure of dissimilarity (distances); output = the cluster centres.
Hierarchical techniques avoid needing to specify $K$: input = a measure of dissimilarity (e.g. distances); output = a hierarchical model of data similarity.
The output is a tree, the dendrogram: the root holds all the data, each level splits it into finer clusters. Cutting the tree at some level gives a flat clustering.

Agglomerative (bottom up): start with every point in its own cluster, merge the closest groups.
Divisive (top down): start with all the data in one cluster, split it recursively.

Divisive methods: hierarchical K-means

Hierarchical K-means is a divisive method: start with all the data in 1 cluster, split it using "flat" K-means, then recursively split each cluster.
$K$ is usually small ($K = 2$: bisecting K-means).
You need to decide when to stop (a number of clusters, a maximum cost per cluster…).

Try it: split, split, split

The data from the slide. Each click splits one cluster in two with K-means ($K = 2$). Here we split the cluster with the largest cost $J$, which is a common rule. The tree on the right grows as the dendrogram of the splits; the lines join each parent centre to its two children.

Agglomerative techniques

Work in the reverse direction (bottom up).
Given $N$ data points and a dissimilarity measure: start with all the data in separate clusters, then repeat $N - 1$ times: find the closest two groups and merge them.
How do we measure the dissimilarity between groups? With a dissimilarity $d_{ij}$ between two data points, the distance between groups $G_1$ and $G_2$ is defined by a linkage:

📐 Linkages

\[ \text{Single linkage (SL):} \quad d_{SL}(G_1, G_2) = \min_{i \in G_1,\, j \in G_2} d_{ij} \] \[ \text{Complete linkage (CL):} \quad d_{CL}(G_1, G_2) = \max_{i \in G_1,\, j \in G_2} d_{ij} \] \[ \text{Group average (GA):} \quad d_{GA}(G_1, G_2) = \frac{1}{N_{G_1} N_{G_2}} \sum_{i \in G_1} \sum_{j \in G_2} d_{ij} \] \[ \text{Centroid linkage:} \quad d_{C}(G_1, G_2) = \lVert \bar{x}_{G_1} - \bar{x}_{G_2} \rVert \]

If the data is nicely clustered, the particular choice does not matter. If it is not, you will get different clusters.
Single link → less compact clusters: chaining. Two groups merge as soon as one pair of points is close, so a chain of points glues far-apart groups together.
Complete link → more compact clusters. Two groups merge only when all their points are close.
Group average lies in between.

Try it: single link vs complete link

The eight points $d_1 \dots d_8$ from the slide (Manning et al., Introduction to Information Retrieval, Fig. 17.2). Step through the merges and compare the two clusters that remain before the last merge: single link joins the two rows ($d_2$–$d_3$ is only 1.5 apart), complete link joins the two squares. The second dataset shows chaining. The dendrogram grows below: the height of each join is the linkage distance of that merge.

Merges

Dendrograms

The leaves are the data points; each join is a merge, drawn at the height of its linkage distance. Cutting the dendrogram with a horizontal line at height $h$ gives the clusters that exist at that height: choose $K$ after clustering, where there is a large gap between consecutive heights.
Single linkage tends to produce a "staircase" dendrogram: points are added one at a time to one big growing cluster (chaining).
Complete linkage and Ward's method (merge the two groups whose union increases the total within-cluster sum of squares $J$ the least, the agglomerative cousin of K-means) give more balanced trees with clearly separated groups.
Centroid linkage can produce inversions: a merge lower than the previous one. Try it on the chaining data.

Evaluation

Cluster evaluation metrics: assessing compactness and separation

A good clustering is compact (small distances inside a cluster, intra-cluster) and well separated (large distances between clusters, inter-cluster). Internal metrics measure this from the data alone. External metrics compare the clustering with ground-truth labels, when we happen to have them (e.g. to benchmark an algorithm).

Metric	Type	Needs true labels?	Explanation
Silhouette score	intra + inter	no	compactness within a cluster vs separation from the nearest other cluster; high = well separated, compact clusters (range −1 … 1)
Davies–Bouldin index	intra + inter	no	average similarity of each cluster to its most similar cluster (spread / distance between centres); lower is better
Dunn index	intra + inter	no	smallest distance between points in different clusters / largest within-cluster distance; higher is better
Within-cluster sum of squares (WCSS)	intra	no	the K-means cost $J$: squared distances of points to their centroids; lower is better, but always drops as $K$ grows
Gap statistic	intra + inter	no	compares the WCSS with that of a random (uniform, structureless) reference dataset
Adjusted Rand Index (ARI)	intra + inter	yes	similarity of two clusterings (true vs predicted), counting pairs of points put together or apart, corrected for chance; 1 = identical, ≈ 0 = random
Normalized Mutual Information (NMI)	intra + inter	yes	shared information between the ground truth and the clustering (the information gain idea), scaled to 0 … 1
Fowlkes–Mallows Index (FMI)	intra + inter	yes	geometric mean of pairwise precision and recall
Cluster purity	intra	yes	fraction of points that belong to the majority true class of their cluster; how homogeneous the clusters are
V-measure	intra + inter	yes	harmonic mean of homogeneity (each cluster contains only one class) and completeness (each class is in one cluster)

💡 Purity is easy to fool: with $K = N$ every cluster is pure (purity 1). ARI and NMI do not reward this.

Try it: score a clustering

The three-cluster data from the elbow widget, now with its true labels. Choose $K$ and a start (the best of 10 restarts, or a single random run, which may be stuck), and compare the metrics.

K-means in Python

K-means from scratch with NumPy, then the library versions.

1. K-means from scratch

kmeans.py Python

import numpy as np

def assign(X, centres):
    # squared distance from every point to every centre: shape (N, K)
    d2 = ((X[:, None, :] - centres[None, :, :]) ** 2).sum(axis=2)
    return d2.argmin(axis=1)                      # index of the nearest centre

def update(X, labels, centres):
    new = centres.copy()
    for k in range(len(centres)):
        members = X[labels == k]
        if len(members):                          # an empty cluster keeps its old centre
            new[k] = members.mean(axis=0)
    return new

def cost(X, labels, centres):
    return ((X - centres[labels]) ** 2).sum()     # J = within-cluster sum of squares

def kmeans(X, K, max_iter=100, rng=None):
    rng = np.random.default_rng(rng)
    centres = X[rng.choice(len(X), K, replace=False)]   # K random data points
    labels = assign(X, centres)
    for _ in range(max_iter):
        centres = update(X, labels, centres)
        new_labels = assign(X, centres)
        if np.array_equal(new_labels, labels):     # nothing changed: converged
            break
        labels = new_labels
    return labels, centres, cost(X, labels, centres)

def kmeans_restarts(X, K, restarts=10, seed=0):
    runs = [kmeans(X, K, rng=seed + r) for r in range(restarts)]
    return min(runs, key=lambda run: run[2])       # keep the lowest cost

rng = np.random.default_rng(42)
X = np.vstack([rng.normal(c, 0.8, size=(60, 2)) for c in [(2.5, 7.5), (2.5, 2.5), (8, 5)]])
labels, centres, J = kmeans_restarts(X, K=3)
print(np.round(centres[np.argsort(centres[:, 0])], 1))  # close to the true centres
# [[2.4 2.5]
#  [2.5 7.4]
#  [8.2 4.9]]
print(round(J, 1))                                 # 202.7

2. K-means++ initialisation

kmeans_pp.py Python

def kmeans_pp_init(X, K, rng=None):
    rng = np.random.default_rng(rng)
    centres = [X[rng.integers(len(X))]]            # 1. first centre: uniformly at random
    for _ in range(K - 1):
        C = np.array(centres)
        # 2. squared distance of every point to its NEAREST chosen centre
        d = ((X[:, None, :] - C[None, :, :]) ** 2).sum(axis=2).min(axis=1)
        # 3. sample the next centre with probability proportional to d
        centres.append(X[rng.choice(len(X), p=d / d.sum())])
    return np.array(centres)

3. scikit-learn: K-means, the elbow and the silhouette

sklearn_kmeans.py Python

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score, adjusted_rand_score

y_true = np.repeat([0, 1, 2], 60)                  # the generating cluster of each point in X

for K in range(2, 7):
    km = KMeans(n_clusters=K, init="k-means++", n_init=10, random_state=0).fit(X)
    print(K, round(km.inertia_, 1),                # inertia_ = J, for the elbow plot
          round(silhouette_score(X, km.labels_), 3))
# 2 926.9 0.583
# 3 202.7 0.744    <- the elbow and the largest silhouette
# 4 170.8 0.617
# 5 139.7 0.491
# 6 120.5 0.358

km = KMeans(n_clusters=3, n_init=10, random_state=0).fit(X)
print(adjusted_rand_score(y_true, km.labels_))     # 1.0: the clustering matches the truth

4. Hierarchical clustering and the dendrogram

hierarchical.py Python

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
from sklearn.cluster import AgglomerativeClustering

# the eight points d1..d8 from the single-link vs complete-link example
D = np.array([[1, 3], [2, 3], [3.5, 3], [4.5, 3],
              [1, 1], [2, 1], [3.5, 1], [4.5, 1]])

for method in ["single", "complete"]:
    Z = linkage(D, method=method)                  # the N-1 merges and their heights
    print(method, fcluster(Z, t=2, criterion="maxclust"))   # cut into 2 clusters
# single   [1 1 1 1 2 2 2 2]   -> the two rows
# complete [1 1 2 2 1 1 2 2]   -> the two squares

dendrogram(linkage(D, "complete"), labels=[f"d{i}" for i in range(1, 9)])
plt.show()

AgglomerativeClustering(n_clusters=2, linkage="ward").fit_predict(D)

Summary: key takeaways

Clustering is unsupervised: group unlabelled data so that points in a cluster are close and clusters are far apart.
K-means alternates two steps: assign each point to the nearest centre, update each centre to the mean of its points.
It is a local search on the cost $J = \sum_k \sum_{y_i = k} \lVert x_i - m_k \rVert^2$: $J$ never increases, and the algorithm always converges, but to a local optimum that depends on the start. Use random restarts (keep the best) or K-means++.
K-means assumes round, similar clusters. Choose $K$ with the elbow method or silhouette analysis.
Variants: K-medians (Manhattan), K-medoids (any distance), K-modes (categorical), soft K-means / EM (probabilistic assignments).
Hierarchical clustering builds a dendrogram without fixing $K$: divisive (e.g. bisecting K-means) or agglomerative with single (chaining), complete (compact), average or centroid linkage.
Evaluate with internal metrics (silhouette, Davies–Bouldin, WCSS) or, when labels exist, external ones (ARI, NMI, purity).

Test yourselfLab 10 quiz

24 auto-graded tasks, 100 points: assignment and update steps, the cost J, convergence and local optima, random restarts and K-means++, the elbow and the silhouette, outliers and variants, hierarchical clustering and evaluation.

Start the quiz →