🎯 K-Means Clustering — Lloyd's Algorithm

Initialise k centroids (randomly or via k-means++). Assign each data point to the nearest centroid by Euclidean distance. Recompute each centroid as the mean position of all assigned points. Repeat assignment and update until no point changes cluster between iterations (convergence). Run multiple times with different initialisations and keep the result with the lowest WCSS.

The elbow method plots WCSS against values of k; the optimal k is at the bend (elbow) where adding more clusters provides diminishing improvement. The silhouette score measures how well each point fits its cluster relative to neighbouring clusters (ranges -1 to +1; higher is better). Domain knowledge often provides the best guide — for example, a retailer segmenting customers might know they want 5 customer personas.

K-means assumes spherical clusters of similar size and density, and struggles with elongated, irregular, or nested clusters. It is sensitive to outliers (which can pull centroids away from the bulk of data) and to the choice of k. It uses Euclidean distance, making it unsuitable for categorical data without preprocessing. Algorithms like DBSCAN, Gaussian mixture models, or hierarchical clustering address some of these limitations.

K-means++ improves initial centroid selection to avoid poor starting configurations. The first centroid is chosen randomly. Each subsequent centroid is chosen with probability proportional to the squared distance from the nearest existing centroid, ensuring centroids start well-separated and spread across the data. This typically yields better final cluster quality and faster convergence than purely random initialisation.

K-means applied to image compression treats each pixel's RGB colour as a 3D data point and clusters all pixels into k colour groups. Each pixel is then replaced by its cluster's centroid colour, reducing the image to a k-colour palette. With k=16, a 24-bit colour image is approximated using only 4 bits per pixel plus a 16-colour lookup table — a significant compression with moderate quality loss.