K-means clustering · aiwiki.page

K-means clustering is a method of cluster analysis that divides numerical observations into $k$ groups, each represented by its arithmetic mean, or centroid. It is widely used in unsupervised learning because it identifies groupings without requiring predefined class labels. Its objective is to minimize the sum of squared distances between observations and their assigned centroids. The name also commonly refers to an iterative algorithm, usually Lloyd’s algorithm, that seeks an approximate solution to this optimization problem. (scikit-learn.org)

Mathematical formulation

Let $x_1,\ldots,x_n$ be observations in the real vector space $\mathbb{R}^d$ , where each coordinate represents a numerical feature. For a specified integer $k$ , the objective is to find nonempty clusters $C_1,\ldots,C_k$ and corresponding centroids $\mu_1,\ldots,\mu_k$ minimizing

J=\sum_{j=1}^{k}\sum_{x_i\in C_j} \lVert x_i-\mu_j\rVert_2^2, \qquad \mu_j=\frac{1}{|C_j|}\sum_{x_i\in C_j}x_i.

The norm denotes Euclidean distance. This loss function is called the within-cluster sum of squares, or inertia. For fixed assignments, the arithmetic mean minimizes the squared-distance contribution of each cluster; a centroid need not coincide with an observed point. (cs.columbia.edu)

The problem belongs to mathematical optimization. Although finding centroids for fixed assignments is straightforward, jointly choosing assignments and centroids is not a convex optimization problem. Computing a global optimum is NP-hard in general, so practical implementations typically use iterative heuristics rather than exact search. (cs.columbia.edu)

Lloyd’s algorithm

The standard procedure starts with $k$ initial centroids and alternates between two operations:

Assignment: assign each observation to its nearest centroid.
Update: replace each centroid with the mean of the observations assigned to it.

Iterations stop when assignments stabilize, centroid movement falls below a tolerance, or a maximum iteration count is reached. An empty cluster requires an implementation-specific response, such as relocating its centroid. Each ordinary assignment or update step cannot increase the objective. With consistent handling of distance ties and nonempty clusters, the exact procedure reaches a stable partition after finitely many changes. This does not establish that the partition is globally optimal. (cs.columbia.edu)

For fixed centroids, nearest-center assignments divide the surrounding space into a Voronoi diagram. Boundaries between pairs of distinct centers lie on hyperplanes, explaining why standard k-means produces convex decision regions rather than following arbitrary curved cluster shapes. Lloyd’s work arose in quantization research and was published in 1982. (cs.columbia.edu)

Initialization and computational cost

Different initial centroids can lead to different final partitions. A common strategy runs the algorithm repeatedly with different initializations and retains the result with the lowest inertia. Fixing the random seed makes a particular randomized computation reproducible, but does not ensure optimality. (scikit-learn.org)

K-means++, introduced by David Arthur and Sergei Vassilvitskii in 2007, improves initialization by spreading the initial centers across the data. After selecting the first center uniformly at random, it samples subsequent centers with probability proportional to their squared distance from the nearest previously selected center. For the original procedure, the expected value of the initial objective is at most $8(\ln k+2)$ times the optimum; subsequent Lloyd iterations cannot increase it. This is an approximation guarantee in expectation, not a guarantee that every run finds the best partition. (theory.stanford.edu)

A straightforward Lloyd iteration costs approximately $O(nkd)$ , giving $O(nkdT)$ for $T$ iterations. Although convergence is often rapid in applications, worst-case iteration counts can be superpolynomial. Mini-batch k-means processes small, randomly selected batches and updates centers incrementally, reducing computation at the possible expense of a higher final objective. (scikit-learn.org)

Choosing the number of clusters

The number $k$ is a hyperparameter supplied before fitting. The globally optimal inertia cannot increase as $k$ increases, so minimizing inertia alone does not determine a useful cluster count. An elbow plot compares inertia across candidate values and looks for diminishing improvements, although a distinct elbow need not exist. (cs.columbia.edu)

The silhouette coefficient compares each observation’s average distance to its own cluster with its average distance to the nearest alternative cluster. Values near $1$ indicate strong separation, values near $0$ indicate overlap, and negative values suggest a potentially inappropriate assignment. Silhouette analysis evaluates a particular notion of geometric separation; it does not independently prove that the selected groups represent meaningful categories. (scikit-learn.org)

Assumptions and limitations

K-means is most suited to compact, approximately isotropic groups with comparable dispersion. It can produce misleading partitions when clusters are elongated, nonconvex, unevenly dispersed, or very different in size. Squared distances also make the objective sensitive to unusually distant observations. Every observation receives an assignment: standard k-means has no separate noise category. (scikit-learn.org)

Feature scaling matters because coordinates with larger numerical ranges can dominate distances. Feature engineering therefore changes the geometry on which clustering operates. In high-dimensional data, distances may become less informative; dimensionality reduction, including principal component analysis, can reduce computation and mitigate some difficulties, while also changing the representation being clustered. (scikit-learn.org)

Applications and related methods

K-means is used for vector quantization, in which observations are represented by a finite codebook of centroids. In image color reduction, pixels are clustered by their color coordinates and each original color is replaced by its assigned centroid. The resulting centers form a smaller palette. (cs.columbia.edu)

Unlike k-means, a Gaussian mixture model can represent clusters with different covariance structures and assign probabilistic memberships. Its expectation–maximization algorithm uses soft assignments, whereas ordinary k-means assigns each observation to exactly one cluster. K-medoids instead represents clusters with actual observations and can accommodate more general dissimilarities, making it a distinct objective rather than merely another initialization of k-means. (cs.columbia.edu)