Clustering

Clustering is unsupervised learning: there are no labels, only data points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^d$. The goal is to partition them into groups (clusters) so that points in one group are similar and points in different groups are dissimilar. What "similar" means is decided entirely by the distance you choose.

Convention used in these notes. Vectors are bold ($\mathbf{x}$); samples are the rows of the data matrix; the distance is Euclidean unless stated; no logarithms appear in this topic. $C_k$ denotes cluster $k$, $|C_k|$ its number of points, ${\mathbf{\mu }}_k$ its centroid, and $K$ the number of clusters. $d(\cdot ,\cdot )$ is a general dissimilarity when Euclidean distance is not required.

k-means partitions the points into exactly $K$ clusters, each represented by its centroid (the mean of its points). It searches for the partition that minimises the within-cluster sum of squares (WCSS), also called the inertia or distortion.

Convergence. Each assignment step cannot increase $J$ (every point moves to a centroid at least as close), and each update step cannot increase $J$ (the mean is the minimiser). $J$ is therefore non-increasing. With the tie rule above, $J$ strictly decreases whenever the partition changes, so no partition repeats; there are only finitely many partitions, so the algorithm stops after finitely many iterations. It stops at a fixed point of the two steps, usually called a local minimum of $J$: neither step can improve it, but it need not be the global minimum.

Sensitivity to initialisation. The final partition and its $J$ depend on the starting centroids; different starts can end at different fixed points, and k-means is not guaranteed to find the global minimum of $J$. In practice it is run from several starts and the lowest $J$ is kept. k-means++ seeding picks the first centroid uniformly at random from the data and each further centroid from the data with probability proportional to $D(\mathbf{x}{)}^2$, the squared distance from $\mathbf{x}$ to the nearest centroid already chosen, which spreads the starting centroids out.

Each iteration costs $O(nKd)$. A cluster can end up empty; its mean is then undefined, and implementations either keep its old centroid or re-seed it (for example at a point far from its current centroid). The clusters produced are separated by straight boundaries (hyperplanes), because each is the set of points nearest one centroid, so k-means suits compact, roughly round clusters of similar size.

Choosing $K$. The minimum achievable WCSS never increases as $K$ grows, and it is $0$ at $K=n$ when the points are distinct (each point its own cluster). So you cannot choose $K$ by simply minimising $J$. (The $J$ that Lloyd's algorithm actually returns from a particular start can even rise with $K$, because it may stop at a poor local minimum.) The elbow method plots the best $J$ found against $K$ and looks for the point after which the drop becomes small. The silhouette score below, or validation on a downstream task, is also used. Whatever the method, $K$ is chosen by the user, not learned by the basic algorithm.

k-medoids keeps the same idea (a partition into $K$ clusters, each with a representative) but the representative, called the medoid, must be one of the data points. It works from a dissimilarity $d(\mathbf{x},\mathbf{y})$ that need not be Euclidean, so it can be used when only a pairwise distance matrix is available.

Hierarchical clustering does not need $K$ in advance. It produces a tree of nested clusters, a dendrogram, and you choose the number of clusters afterwards by cutting the tree.

Agglomerative (bottom-up). Start with $n$ singleton clusters and repeatedly merge the two closest clusters until one cluster remains. This takes exactly $n-1$ merges. Divisive (top-down). Start with all points in one cluster and repeatedly split a cluster. The number of ways to split $n$ points into two non-empty groups is $2^{n-1}-1$, so exact divisive search is impractical and a heuristic split rule (for example running 2-means on the cluster) is used.

Agglomerative methods differ only in how the distance between two clusters $A$ and $B$ is defined. The syllabus names single linkage and "multiple-linkage"; the standard linkage criteria are below. Single, complete and average linkage need only the point distances $d(a,b)$.

Single linkage and the minimum spanning tree. Treat the points as a complete graph whose edge weights are the distances. The single-linkage merge heights are exactly the edge weights of a minimum spanning tree (MST), taken in increasing order (this is Kruskal's algorithm). Removing the $K-1$ largest MST edges leaves the $K$ single-linkage clusters.

For single, complete, average and Ward's linkage the merge heights never decrease as you go up the tree, so the dendrogram has no inversions. Centroid linkage can invert: for three points at mutual distance 1, the first merge is at height 1, and the third point is then $\sqrt{3}/2\approx 0.866$ from the pair's midpoint. The naive algorithm stores the $n\times n$ distance matrix ($O(n^2)$ memory) and takes $O(n^3)$ time. Given the data and the linkage, the result has no random element, unlike k-means, which depends on its start. Ties between equal distances still have to be broken by a rule, and the choice can change the tree.