Dictionary of Applied Machine Learning

$k$-means

Updated on 2026-09-07

Typeset PDF version — the authoritative form of this entry

Python demo — a script that recomputes what this entry states and prints one line per check

The $k$-means method is a hard clustering method for data points with numeric feature vectors. It partitions a dataset into $\nrcluster$ clusters. Each cluster is represented in the feature space by a cluster centroid. The quality of a clustering is measured by the clustering error: the average squared Euclidean distance between a data point and the nearest cluster centroid. Minimizing the clustering error is a non-convex and NP-hard optimization problem. Practical $k$-means methods use an approximate iterative optimization method known as Lloyd's algorithm: a fixed-point iteration that alternates between assigning each data point to its nearest cluster centroid and re-averaging. No iteration increases the clustering error, and the iterates reach a fixed point after finitely many iterations.

Definition

B-fetchConsider the task of grouping the days of a year by their weather at some location, say the town Krems in Austria. Each day yields a data point whose feature vector is obtained by stacking temperature measurements recorded during that day, e.g., the minimum and the maximum air temperature. Days in the same group should have similar feature vectors. $k$-means produces such a grouping: with $\nrcluster = 2$, it partitions the days into a cold-season and a warm-season cluster.

$k$-means is an optimization-based hard clustering method for data points with a numeric feature vector (Jung, 2022, Sect. 8.1). It partitions a dataset $\dataset = \{\featurevec^{(1)}, \ldots, \featurevec^{(\samplesize)}\}$ with $\featurevec^{(\sampleidx)} \in \reals^{\featuredim}$ into $\nrcluster$ disjoint clusters indexed by $\clusteridx = 1, \ldots, \nrcluster$. Each cluster is represented by a cluster centroid $\clustercentroid{\clusteridx} \in \reals^{\featuredim}$, obtained by averaging the feature vectors of the data points assigned to that cluster (see Fig. 1 for an example with $\nrcluster = 2$ cluster centroids). The quality of a given choice of cluster centroids is measured by the clustering error: the average squared Euclidean distance between the feature vector of a data point and the nearest cluster centroid. The $k$-means principle is to choose cluster centroids that minimize the clustering error, \[ \min_{\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster}} \;\frac{1}{\samplesize}\sum_{\sampleidx=1}^{\samplesize} \min_{\clusteridx = 1, \ldots, \nrcluster} \normgeneric{\featurevec^{(\sampleidx)} - \clustercentroid{\clusteridx}}{2}^{2}\text{.} \] The inner minimization assigns each data point to its nearest cluster centroid. The outer minimization chooses the cluster centroids so that the average squared Euclidean distance (between each data point and its nearest cluster centroid) is small.

Figure 1 of the entry kmeans
Figure 1: Scatterplot of data points with feature vectors $\featurevec^{(\sampleidx)} \in \reals^{2}$ for $\sampleidx = 1, \ldots, \samplesize$. The crosses mark the two cluster centroids $\clustercentroid{1}, \clustercentroid{2}$ produced by $k$-means with $\nrcluster = 2$
Solving the $k$-means optimization problem exactly is NP-hard (Mahajan et al., 2009). The difficulty of the optimization problem is also reflected by the fact that the objective function is non-convex in the cluster centroids. With a single data point at $x = 0$ and two scalar cluster centroids $w^{(1)}, w^{(2)} \in \reals$, the objective is $f(w^{(1)}, w^{(2)}) = \min\big((w^{(1)})^{2}, (w^{(2)})^{2}\big)$. Both $(w^{(1)}, w^{(2)}) = (1, 0)$ and $(0, 1)$ are global optima with value $0$, meaning at least one centroid perfectly coincides with the data point $x$, yet their midpoint $(0.5, 0.5)$ gives $f = 0.25 > 0$. A convex combination of optima is therefore worse than either optimum, which violates the defining property of a convex function.

B-lloydPractical implementations use iterative alternating-minimization methods that converge to a local optimum. A widely used choice is Lloyd's algorithm, which alternates between assigning each data point to its closest cluster centroid and recomputing each cluster centroid as the mean of the currently assigned data points. One iteration of Lloyd's algorithm is the application of an operator $\fixedpointop$ to the stacked cluster centroids $\weights \defeq \big(\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster}\big)$, so the method is the fixed-point iteration $\weights^{(\iteridx+1)} = \fixedpointop\big(\weights^{(\iteridx)}\big)$. Its fixed points are cluster centroids that each coincide with the mean of the data points assigned to them. Applying $\fixedpointop$ never increases the clustering error, and since a finite dataset admits only finitely many partitions, the iterates reach a fixed point after finitely many iterations (Selim and Ismail, 1984).

The $k$-means principle is a special case of the empirical risk minimization (ERM) principle. Indeed, $k$-means uses a hypothesis space $\hypospace_{\nrcluster}$ that consists of all maps $\hypothesis: \featurespace \rightarrow \featurespace$ of the piecewise-constant form \[ \hypothesis(\featurevec) = \clustercentroid{\,\clusteridx^{\star}(\featurevec)}, \qquad \clusteridx^{\star}(\featurevec) = \argmin_{\clusteridx = 1, \ldots, \nrcluster} \normgeneric{\featurevec - \clustercentroid{\clusteridx}}{2}\text{,} \] parameterized by the $\nrcluster$ cluster centroids $\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster} \in \featurespace$. Each such hypothesis maps every feature vector to its nearest cluster centroid. The loss function is the squared Euclidean distance between the feature vector of each data point and its nearest cluster centroid, $\lossfunc{\featurevec}{\hypothesis} = \normgeneric{\featurevec - \hypothesis(\featurevec)}{2}^{2}$. With these choices, ERM on $\hypospace_{\nrcluster}$ recovers the $k$-means optimization problem above (Jung, 2022, Sect. 8.1).

B-imageApplications of $k$-means include customer segmentation (grouping the customers of a retailer by feature vectors such as monthly spending and number of purchases), outlier detection, compression, and image segmentation. Fig. 2 illustrates the latter two on a subsampled photo of the Ötscher massif: $k$-means on the pixel colors with $\nrcluster = 4$ replaces each pixel's color by the nearest of $\nrcluster$ palette colors, compressing $24$ bits per pixel to $2$ bits per pixel plus a small palette; with $\nrcluster = 2$, the cluster assignments form a segmentation mask that separates the sky and the summit from the vegetation.

Figure 2 of the entry kmeans
Figure 2: Image compression and image segmentation via $k$-means on pixel colors. (a) A photo of the Ötscher massif, subsampled to $97 \times 129$ pixels. (b) Each pixel's color replaced by the nearest of $\nrcluster = 4$ palette colors, compressing $24$ bits per pixel to $2$ bits per pixel plus the palette — a compression factor of approximately $12$. (c) Segmentation mask from $\nrcluster = 2$: sky and summit (white) versus vegetation (black). Data generated by pythondemos/kmeans.py
Synonyms: $k$-means clustering.

See also: hard clustering, cluster, cluster centroid, clustering error, Lloyd's algorithm, $k$-means++, Euclidean distance, optimization problem, empirical risk minimization, hypothesis space, loss function.

References

  1. Jung (2022). Machine Learning: The Basics. Springer Nature. doi.org/10.1007/978-981-16-8193-6
  2. Mahajan et al. (2009). The Planar k-Means Problem is NP-Hard. WALCOM: Algorithms and Computation.
  3. Selim and Ismail (1984). K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality. IEEE Trans. Pattern Anal. Mach. Intell.. doi.org/10.1109/TPAMI.1984.4767478

Cite this entry

@misc{dictml_kmeans,
  author = {Jung, Alexander and Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {$k$-means},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-09-11},
  url = {https://dictionaryofml.org/terms/kmeans.html}
}