Clustering — k-Means, k-Medoids and Hierarchical Clustering

The clustering problem

Clustering groups unlabelled points so that points in the same cluster are similar and points in different clusters are dissimilar. It is unsupervised: there are no labels to check against, so the result depends on the choice of distance, algorithm and number of clusters. Applications: customer segmentation, document grouping, image segmentation, anomaly detection, vector quantisation.

Distances: Euclidean (most common), Manhattan, cosine (text), Hamming (categorical). Scale features first, exactly as for k-NN.

k-means

Partition $n$ points into $k$ clusters minimising the within-cluster sum of squares:

Lloyd's algorithm:

1. Initialise $k$ centroids.
2. Assign each point to its nearest centroid.
3. Update each centroid to the mean of its assigned points.
4. Repeat 2–3 until assignments stop changing.

import numpy as np

def kmeans(X, k, iters=100, seed=0):
    rng = np.random.default_rng(seed)
    C = X[rng.choice(len(X), k, replace=False)]           # random initial centroids
    for _ in range(iters):
        labels = np.argmin(((X[:, None] - C[None]) ** 2).sum(-1), axis=1)
        newC = np.array([X[labels == j].mean(0) if np.any(labels == j) else C[j] for j in range(k)])
        if np.allclose(newC, C):
            break
        C = newC
    return labels, C

Properties

• Each step cannot increase $J$, so the algorithm converges — to a local minimum that depends on initialisation. Run several random restarts and keep the lowest $J$.
• k-means++ initialisation: choose the first centroid at random, then each next one with probability proportional to its squared distance from the nearest chosen centroid — spreads the seeds and gives a provable $O(\log k)$ approximation.
• Cost per iteration $O(nkd)$.
• Assumes roughly spherical, similarly sized, convex clusters; sensitive to outliers (means are pulled) and to feature scale; needs $k$ in advance.

Choosing $k$

• Elbow: plot $J$ against $k$ and look for the bend.
• Silhouette: for point $i$ with mean intra-cluster distance $a(i)$ and mean distance to the nearest other cluster $b(i)$, $s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \in [-1, 1]$; choose the $k$ with the highest average.
• Domain knowledge or downstream usefulness.

k-medoids (PAM)

Like k-means, but each cluster centre must be an actual data point (the medoid), chosen to minimise the sum of (any) distances to the cluster's members:

PAM (Partitioning Around Medoids) repeatedly tries swapping a medoid with a non-medoid and keeps swaps that lower the total cost.

Hierarchical clustering

Builds a nested sequence of clusterings displayed as a dendrogram; cutting it at a height gives a flat clustering — no need to fix $k$ beforehand.

Bottom-up (agglomerative)

1. Start with each point as its own cluster.
2. Repeatedly merge the two closest clusters.
3. Stop when one cluster remains ($n - 1$ merges).

The linkage defines the distance between clusters:

Agglomerative clustering needs the $O(n^2)$ distance matrix and $O(n^2\log n)$–$O(n^3)$ time, so it suits small and medium data sets.

Top-down (divisive)

Start with all points in one cluster and recursively split — e.g. bisecting k-means (repeatedly split the worst cluster with 2-means) or DIANA (split off the most dissimilar points). Useful when only the top few levels are needed.

Beyond these methods

DBSCAN (density-based, finds arbitrary shapes and noise points), Gaussian mixture models (soft, probabilistic k-means fitted by EM) and spectral clustering are common alternatives.

Quick revision