k-Means Clustering

machine-learning clustering statistics

Definition

k-Means Clustering

k-means clustering is an unsupervised partitioning algorithm that seeks to divide a set of $d$-dimensional observations $\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$ into $k\le n$ disjoint sets $S=\{S_1,\dots ,S_k\}$ to minimise the within-cluster sum of squares (WCSS). Formally, the algorithm identifies the partition $S$ that satisfies:

$\arg {\min }_S{\sum }_{i=1}^k{\sum }_{\mathbf{x}\in S_i}\Vert \mathbf{x}-{\mu }_i{\Vert }^2$

where ${\mu }_i$ is the centroid (arithmetic mean) of the points in cluster $S_i$.

Lloyd’s Algorithm

The optimisation problem is NP-hard; however, it is typically solved using the iterative Lloyd’s algorithm, which alternates between two steps:

Assignment Step: Each observation ${\mathbf{x}}_j$ is assigned to the cluster whose centroid ${\mu }_i$ is closest in terms of Euclidean distance:

$$S_i^{(t)}=\{{\mathbf{x}}_p:\Vert {\mathbf{x}}_p-{\mu }_i^{(t)}{\Vert }^2\le \Vert {\mathbf{x}}_p-{\mu }_j^{(t)}{\Vert }^2\forall j,1\le j\le k\}$$

Update Step: The centroids are recalculated based on the new cluster assignments:
${\mu }_i^{(t+1)}=\frac{1}{|S_i^{(t)}|}{\sum }_{{\mathbf{x}}_j\in S_i^{(t)}}{\mathbf{x}}_j$

Limitations and Variants

Geometric Assumptions: k-means is biased toward finding spherical, equally-sized clusters. It fails to correctly identify non-convex structures, such as the two-moon dataset, where spectral clustering is preferred.

Initialisation Sensitivity: The algorithm is sensitive to the initial placement of centroids and may converge to a local minimum. Techniques such as k-means++ are utilised to ensure better initial seeding.

Medoids vs Centroids: While k-means uses the arithmetic mean as the cluster centre, k-medoids restricted the centre to be one of the actual data points from the set, providing robustness to outliers.