Clustering

k-means is the default partitioning method. Given k, it minimises the within-cluster sum of squared distances to the cluster centroids by Lloyd's algorithm: assign each point to its nearest centroid, recompute each centroid as the mean of its points, and repeat until assignments stop changing. Each iteration costs O(n·k·d). Finding the global optimum is NP-hard even for two clusters, so the result depends on initialisation; k-means++ (Arthur and Vassilvitskii, 2007) picks spread-out starting centroids with probability proportional to squared distance and is O(log k)-competitive with the optimal clustering in expectation, and implementations run several restarts and keep the best. k-means assumes roughly spherical clusters of similar size in Euclidean space and is sensitive to outliers and to feature scaling.

Other families make different assumptions. Hierarchical agglomerative clustering starts with every point alone and repeatedly merges the closest pair of clusters, with the linkage criterion (single, complete, average or Ward's minimum variance) defining "closest"; the result is a dendrogram that can be cut at any level. Density-based DBSCAN (Ester et al., 1996) takes a radius eps and a minimum neighbourhood size minPts, grows clusters from core points in dense regions, finds arbitrarily shaped clusters and labels sparse points as noise; HDBSCAN removes the need for a single global eps. Gaussian mixture models fitted with the EM algorithm give soft, probabilistic assignments and elliptical clusters. Spectral clustering works on the eigenvectors of a similarity graph.

Choosing the number of clusters is a judgement call. The elbow method looks for a bend in the within-cluster error curve; the silhouette coefficient (Rousseeuw, 1987) compares each point's mean distance to its own cluster with that to the nearest other cluster, from -1 to 1; information criteria such as BIC apply to mixture models. These indices measure geometric separation, not usefulness. Kleinberg (2002) proved that no clustering function can satisfy three natural axioms (scale invariance, richness and consistency) at once, which formalises why different algorithms legitimately disagree.

In practice results depend more on representation than on algorithm. Features must be scaled or standardised, categorical data needs suitable distances, and high-dimensional data suffers from distance concentration, so text and images are usually embedded first and compared with cosine similarity, often after dimensionality reduction. Cluster labels are also unstable: rerunning with a different seed or a slightly different sample can reshuffle membership, so stability should be checked before clusters feed decisions.

Clustering is sometimes confused with classification because both produce groups, but classification assigns inputs to predefined, labelled classes learned from examples, while clustering discovers groups whose meaning must be interpreted afterwards. When clusters are used to segment or profile customers or citizens, the resulting segments can amount to profiling under GDPR Article 4(4).