K-means clustering

Cluster analysis partitions observations into groups whose members are similar under a specified measure. Within this field, k-means clustering denotes an optimization problem in which a finite set of observations is represented by (k) centroids, with each observation assigned to the centroid having the smallest squared Euclidean distance. The same name also refers to a family of iterative algorithms that seek a locally optimal partition for this objective.

For observations (x_1,\ldots,x_n\in\mathbb{R}^d), k-means seeks a partition (S={S_1,\ldots,S_k}) minimizing the within-cluster sum of squares

[ \Phi(S)=\sum_{i=1}^{k}\sum_{x\in S_i}\lVert x-\mu_i\rVert^2, ]

where

[ \mu_i=\frac{1}{|S_i|}\sum_{x\in S_i}x ]

is the arithmetic mean of cluster (S_i). The mean is the least-squares representative of a finite set under squared Euclidean distance, so the use of centroids follows directly from the objective rather than from an independent modeling assumption.

The standard iterative method alternates between assigning observations to their nearest centroids and replacing each centroid with the mean of its assigned observations. Every completed assignment or centroid update leaves the objective unchanged or decreases it. Because a finite data set has only finitely many possible assignments, deterministic handling of ties yields termination at a fixed point after finitely many assignment changes. The resulting fixed point is generally a local optimum, not necessarily the global optimum.

Historical development

The mathematical basis of k-means emerged from several lines of work on quantization, least-squares approximation, and classification. Hugo Steinhaus formulated a related problem of dividing a heterogeneous population into internally homogeneous groups in 1956. His formulation identified representative points with the centers of their corresponding classes and expressed the partition through proximity to those centers.

In 1958, You Watanabe gave a finite-partition analysis of the alternating assignment and recomputation scheme. Watanabe’s treatment distinguished changes caused by strict decreases in squared error from changes caused only by equal-distance ties, establishing finite termination when a fixed ordering resolved those ties. The analysis also noted that an empty class does not possess an arithmetic mean, separating that condition from ordinary convergence of nonempty classes.

Stuart Lloyd developed the same central iteration for pulse-code modulation at Bell Laboratories in 1957, although his paper appeared in 1982. Lloyd’s formulation treated centroids as reconstruction values and cluster boundaries as nearest-neighbor decision regions, thereby connecting the method to vector quantization.

Edward W. Forgy described an iterative clustering procedure in 1965 that used randomly selected observations as initial representatives. In 1967, James MacQueen introduced the term “k-means” and presented an online form in which cluster means were updated as observations were assigned. These developments produced several related algorithms that share an objective but differ in initialization, update order, and treatment of intermediate assignments.

Later analysis concentrated on computational complexity and initialization. David Arthur and Sergei Vassilvitskii introduced k-means++ in 2007, using distance-weighted sampling to choose initial centroids. Their result bounded the expected objective produced by the initialization relative to the optimum, while leaving the subsequent Lloyd iterations unchanged.

Objective and geometric structure

For fixed centroids (c_1,\ldots,c_k), the objective

[ \sum_{j=1}^{n}\min_{1\leq i\leq k}\lVert x_j-c_i\rVert^2 ]

is minimized over assignments by placing each observation in a cluster associated with one of its nearest centroids. This assignment divides the ambient space into Voronoi cells. Each cell contains the points at least as close to its centroid as to every competing centroid, with boundary conventions determining the assignment of equidistant observations.

For a fixed nonempty cluster (S_i), its contribution to the objective is minimized at the arithmetic mean. The identity

[ \sum_{x\in S_i}\lVert x-c\rVert^2

\sum_{x\in S_i}\lVert x-\mu_i\rVert^2 + |S_i|\lVert c-\mu_i\rVert^2 ]

shows that any displacement of (c) from (\mu_i) adds a nonnegative term. Consequently, the assignment step and the centroid step each solve one part of the optimization problem exactly while holding the other part fixed. K-means is therefore an instance of alternating optimization, also interpretable as block coordinate descent over discrete assignments and continuous centroid coordinates.

The partition produced by k-means consists of intersections between the data set and convex Voronoi regions. This geometry does not imply that the observed points in a cluster form a visibly convex cloud, because a finite sample can occupy only disconnected portions of its cell. It does mean that a single cluster cannot represent two separated regions when another centroid lies between them under the same Euclidean metric.

The objective also admits a variance decomposition. If (\bar{x}) is the overall mean, then

[ \sum_{j=1}^{n}\lVert x_j-\bar{x}\rVert^2

\sum_{i=1}^{k}\sum_{x\in S_i}\lVert x-\mu_i\rVert^2 + \sum_{i=1}^{k}|S_i|\lVert\mu_i-\bar{x}\rVert^2. ]

Minimizing within-cluster variation is thus equivalent to maximizing the corresponding between-cluster variation for a fixed data set. This identity concerns the numerical objective and does not by itself establish that the clusters correspond to externally meaningful categories.

Lloyd iteration

A Lloyd iteration begins from a set of (k) centroids. The assignment phase associates every observation with a nearest centroid, after which the update phase replaces each centroid by the mean of its assigned observations. The process reaches a fixed point when neither phase changes the represented solution under the adopted tie convention.

Initialization affects the attained fixed point because the objective is nonconvex in the combined space of partitions and centroid locations. Uniformly sampling initial centroids from the observations can place several centroids in one dense region while leaving another region initially unrepresented. Distance-weighted seeding reduces this concentration by assigning greater selection probability to observations far from the centroids already chosen.

An empty cluster can arise when no observation selects a centroid during an assignment phase. The arithmetic mean is then undefined, so implementations employ an additional convention. Common conventions retain the previous centroid or replace it with an observation taken from a cluster contributing substantial squared error. These conventions define different algorithmic trajectories even though the underlying nonempty-cluster objective remains the same.

Equal-distance ties create another form of nonuniqueness. A point on a Voronoi boundary can be assigned to more than one cluster without changing the assignment-phase objective at that moment. If tie resolution varies between iterations, assignments can change while the objective remains constant. A fixed deterministic rule removes this ambiguity and supports the standard finite-termination argument.

Statistical interpretation

K-means has a close relationship to a Gaussian mixture model whose components have equal spherical covariance matrices and, in the simplest correspondence, equal prior weights. Under those restrictions, assigning an observation to the component with greatest posterior density becomes equivalent to selecting the nearest component mean. The centroid update then matches the maximum-likelihood update for the means after assignments have become deterministic.

This relationship is a limiting form of expectation–maximization, often called hard assignment. A general Gaussian mixture model retains fractional membership probabilities and can estimate unequal covariances or mixing proportions. K-means instead represents each observation by one cluster label and optimizes squared Euclidean distortion, so its clusters do not constitute probability distributions unless an additional probabilistic model is imposed.

The squared-distance objective gives observations with large residual distances disproportionate influence because their contribution grows quadratically. The centroid is correspondingly sensitive to outliers. Methods based on medians, medoids, or trimmed objectives alter this behavior by changing either the representative assigned to each cluster or the loss function applied to residual distances.

Feature scaling also changes the geometry. Multiplying one coordinate by a constant multiplies that coordinate’s contribution to squared distance by the square of the same constant. Consequently, k-means applied to differently scaled representations of the same measurements solves different optimization problems rather than merely producing different numerical expressions of one problem.

Computational properties

For (n) observations in (d) dimensions and (k) clusters, one direct Lloyd iteration requires approximately (O(nkd)) arithmetic operations, dominated by distance calculations between observations and centroids. The total running time additionally depends on the number of iterations, which varies with initialization and data geometry.

Finding a globally optimal k-means partition is computationally difficult. The optimization problem is NP-hard for general dimension and remains NP-hard under several restricted settings. Lloyd’s algorithm does not resolve this global problem; it identifies a partition stable under its two alternating update operations.

The distinction between finite termination and efficient termination is material. A deterministic Lloyd process on finite data eventually repeats no changing assignment, but worst-case constructions can force exponentially many iterations relative to the input description. Empirical implementations commonly finish in fewer iterations, although that observation does not change the worst-case bound.

The parameter (k) is part of the problem specification rather than an output of the basic objective. Increasing (k) cannot increase the minimum achievable within-cluster sum of squares, since an existing partition can be preserved while an additional centroid duplicates or subdivides a cluster. The objective alone therefore does not select a finite preferred value of (k); model-selection criteria introduce an additional penalty, stability condition, or external validation measure.

Scope

K-means represents observations through Euclidean centroids and is defined by the minimization of squared reconstruction error. Its mathematical structure is therefore most directly aligned with continuous vector data for which arithmetic averaging and Euclidean displacement have the intended interpretation. Data represented only by pairwise dissimilarities do not necessarily admit valid centroids in the original observation space.

The method differs from k-medoids, which restricts representatives to observed data points and can operate with a broader class of dissimilarities. It also differs from hierarchical clustering, which constructs nested relationships between groups rather than optimizing one flat partition for a fixed value of (k). Density-based clustering uses connected regions of sufficiently high sample density and therefore encodes a geometric criterion distinct from centroidal variance minimization.