Dictionary of Applied Machine Learning: 107 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

$k$-means

Updated on 2026-10-22

Readiness 100/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Cite this entry

See also clustering empirical risk minimization hypothesis space Gaussian mixture model expectation–maximization

$k$-means is a hard clustering method for data points with numeric feature vectors. Each data point is assigned to exactly one of $\nrcluster$ clusters, each represented by a cluster centroid, namely the cluster whose cluster centroid is nearest in Euclidean distance. The cluster centroids are chosen to minimize the clustering error, the average squared Euclidean distance between a data point and its nearest cluster centroid. The resulting $k$-means optimization problem is an instance of empirical risk minimization (ERM) using a specific choice for the loss function. This optimization problem is non-convex and NP-hard, and typically solved using Lloyd's algorithm. This algorithm consists of a fixed-point iteration that never increases the clustering error and reaches a fixed point after finitely many iterations. Replacing the squared Euclidean distance by the Euclidean distance itself gives $k$-medians, whose averaging step computes a geometric median (GM) and which is less sensitive to outliers.

Figure produced by the Python demo of the entry k-means
Figure written by the entry's Python demo kmeans.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

B-patchesFig. 1 shows a photograph of a mountain that is cut into small square patches, and each patch is described by two numbers: how green and how blue it is on average. Vegetation, mountain and haze, and bright sky form three clusters of such patches, which are data points characterized by a feature vector $\featurevec \in \reals^{\featuredim}$. $k$-means is a hard clustering method for such data points (Hastie et al., 2009, Sect. 14.3.6; MacQueen, 1967).

B-lloydThe idea of $k$-means is to assign each data point of a dataset $\dataset = \{\featurevec^{(1)}, \ldots, \featurevec^{(\samplesize)}\}$ to exactly one of $\nrcluster$ clusters indexed by $\clusteridx = 1, \ldots, \nrcluster$. Each cluster is represented by a cluster centroid $\clustercentroid{\clusteridx} \in \reals^{\featuredim}$, and a data point is assigned to the cluster whose cluster centroid is nearest in Euclidean distance. The quality of a given choice of cluster centroids, and of the resulting hard clustering, is measured by the clustering error: the average squared Euclidean distance between a data point and its nearest cluster centroid, \[ \frac{1}{\samplesize}\sum_{\sampleidx=1}^{\samplesize} \min_{\clusteridx = 1, \ldots, \nrcluster} \normgeneric{\featurevec^{(\sampleidx)} - \clustercentroid{\clusteridx}}{2}^{2}\text{.} \] 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, and the outer minimization moves the cluster centroids (Fig. 1).

Figure 1 of the entry kmeans
Figure 1: Top: the photograph of the Oetscher massif with the patch grid drawn on it; each patch is one data point. Bottom: the $972$ patches, each described by its average greenness and its average blueness, both on a scale from $0$ to $1$. The three crosses are the cluster centroids found by $k$-means with $\nrcluster = 3$, labeled at their height, and the dashed lines are the boundaries between the clusters: each patch is assigned to the cluster whose cluster centroid is nearest. The thin lines connect two cluster centroids; each boundary crosses such a line at its midpoint at a right angle, marked by the small square. Data generated by pythondemos/kmeans.py
The clustering model of $k$-means is parameterized by the cluster centroids $\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster} \in \reals^{\featuredim}$. These model parameters are learned from a dataset by minimizing the clustering error. The resulting optimization problem has no closed-form solution, and the standard method for solving it approximately is Lloyd's algorithm (Lloyd, 1982), which alternates between two steps. The assignment step assigns every data point to its nearest cluster centroid, \begin{equation} \label{equ_kmeans_assign_dict} \widehat{\clusteridx}^{(\sampleidx)} \defeq \argmin_{\clusteridx = 1, \ldots, \nrcluster} \normgeneric{\featurevec^{(\sampleidx)} - \clustercentroid{\clusteridx}}{2} \quad \text{for } \sampleidx = 1, \ldots, \samplesize\text{,} \end{equation} and the averaging step moves each cluster centroid to the mean of the data points assigned to it, \begin{equation} \label{equ_kmeans_average_dict} \clustercentroid{\clusteridx} \defeq \frac{1}{\big|\{\sampleidx : \widehat{\clusteridx}^{(\sampleidx)} = \clusteridx\}\big|} \sum_{\sampleidx : \widehat{\clusteridx}^{(\sampleidx)} = \clusteridx} \featurevec^{(\sampleidx)} \quad \text{for } \clusteridx = 1, \ldots, \nrcluster\text{.} \end{equation} The two steps are repeated until the assignment \(\eqref{equ_kmeans_assign_dict}\) stops changing. Algorithm 1 states the method in full.
Algorithm 1 of the entry kmeans
Algorithm 1: $k$-means, Lloyd's algorithm
Run on the $972$ patches of Fig. 1 with $\nrcluster = 3$, $k$-means separates vegetation, mountain and haze, and bright sky. Every patch it assigns to the bluest cluster centroid lies in the upper half of the photograph. The learned cluster centroids define a hard clustering: every data point belongs to exactly one cluster, the one with the nearest cluster centroid. In contrast, soft clustering methods assign the same data point to several clusters, with varying degrees of belonging. Fig. 2 shows this assignment on the photograph itself.
Figure 2 of the entry kmeans
Figure 2: (a) The photograph from Fig. 1 at patch resolution, each patch one data point. The same photograph three times, each keeping only the patches assigned to one cluster: vegetation (b), mountain and haze (c), and bright sky (d). Every patch is bright in exactly one copy and black in the other two, so the three copies add back up to (a). Data generated by pythondemos/kmeans.py
The $k$-means principle is an instance of empirical risk minimization (ERM) with a particular choice for the hypothesis space and the loss function. The hypothesis space $\hypospace_{\nrcluster}$ consists of all maps $\hypothesis: \reals^{\featuredim} \rightarrow \reals^{\featuredim}$ 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 \reals^{\featuredim}$. Each such hypothesis maps every feature vector to its nearest cluster centroid. The region of feature space mapped to one cluster centroid is bounded by hyperplanes, one for each other cluster centroid (the dashed lines of Fig. 1). Thus, every cluster found by $k$-means is a convex region. The loss incurred by a feature vector $\featurevec$ is the squared Euclidean distance to its nearest cluster centroid, $\lossfunc{\featurevec}{\hypothesis} = \normgeneric{\featurevec - \hypothesis(\featurevec)}{2}^{2}$. The clustering error is then obtained as the average loss, i.e., the empirical risk, over the entire dataset. Minimizing the clustering error is therefore ERM over $\hypospace_{\nrcluster}$.

The clustering error is a non-convex function of the cluster centroids: with a single data point at $x = 0$ and two scalar cluster centroids $w^{(1)}, w^{(2)} \in \reals$, it is $\min\big((w^{(1)})^{2}, (w^{(2)})^{2}\big)$, so both $(1, 0)$ and $(0, 1)$ are global optima with value $0$, but their midpoint $(0.5, 0.5)$ gives $0.25$. Solving the optimization problem exactly is NP-hard (Mahajan et al., 2009). Lloyd's algorithm is an approximate method for the $k$-means optimization problem: it never increases the clustering error. Since Lloyd's algorithm might converge to a local minimum of the clustering error, it is typically run several times with different initializations, keeping the run with the smallest clustering error (Hastie et al., 2009, Sect. 14.3.6). A variant of $k$-means referred to as $k$-means++ uses a specific construction of the initial cluster centroids.

Like the expectation–maximization (EM) algorithm for a Gaussian mixture model (GMM), Lloyd's algorithm is a fixed-point iteration. Collect the cluster centroids in one vector $\weights \defeq \big(\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster}\big)$. One iteration, the assignment step \(\eqref{equ_kmeans_assign_dict}\) followed by the averaging step \(\eqref{equ_kmeans_average_dict}\), applies an operator $\fixedpointop$ to the current cluster centroids, so the method is the fixed-point iteration $\weights^{(\iteridx+1)} = \fixedpointop\big(\weights^{(\iteridx)}\big)$. The fixed points of $\fixedpointop$ are cluster centroids that each coincide with the mean of the data points assigned to them. Convergence follows from monotone descent rather than from a contractive operator property: each of the two steps minimizes the clustering error over one set of variables with the other held fixed, so applying $\fixedpointop$ never increases the clustering error. A finite dataset admits only finitely many partitions, so the iterates reach a fixed point after finitely many iterations (Selim and Ismail, 1984). On the patches of Fig. 1, Lloyd's algorithm reached a fixed point after $12$ iterations, and the clustering error never increased along the way.

B-gmmLloyd's algorithm for $k$-means is the limit of the EM algorithm for a GMM under additional constraints. Fix every cluster probability of the GMM at $1/\nrcluster$ and every covariance matrix at $\sigma^{2} \mI$, a multiple of the identity matrix with one common $\sigma^{2}$. The posterior distribution of the cluster index then depends on $\featurevec$ only through its Euclidean distances to the means, and as $\sigma^{2}$ shrinks towards $0$ it concentrates on the closest one. In the limit ($\sigma^{2} \to 0$), the E-step of EM becomes the assignment step \(\eqref{equ_kmeans_assign_dict}\) and the M-step becomes the averaging step \(\eqref{equ_kmeans_average_dict}\) of Lloyd's algorithm. On the patches of Fig. 1 with $\sigma^{2} = 10^{-4}$, the EM algorithm assigns $99.4\%$ of the patches like $k$-means. Leaving the covariance matrices and the cluster probabilities free is what lets a GMM provide a degree of belonging where $k$-means assigns each data point to one cluster.

B-mediansThe loss function is what separates $k$-means from its generalizations, and it decides what the averaging step of Lloyd's algorithm computes. Replacing the squared Euclidean distance by the Euclidean distance itself, $\lossfunc{\featurevec}{\hypothesis} = \normgeneric{\featurevec - \hypothesis(\featurevec)}{2}$, gives the $k$-medians optimization problem. The assignment step \(\eqref{equ_kmeans_assign_dict}\) is unchanged, since the nearest cluster centroid is the same under both losses, but the averaging step \(\eqref{equ_kmeans_average_dict}\) becomes the geometric median (GM) of the data points assigned to a cluster, which has no closed form and is computed by Weiszfeld's fixed-point iteration (Weiszfeld, 1937). The gain is robustness to outliers: adding $10$ far-away patches to the $566$ patches of the vegetation cluster of Fig. 1 moves their mean by $0.044$ but their GM by $0.004$, while $k$-medians assigns $98.5\%$ of the patches like $k$-means.

The averaging step is not tied to the squared Euclidean distance alone: for any Bregman divergence $\lossfunc{\featurevec}{\hypothesis} = \bregmandiv{\featurevec}{\hypothesis(\featurevec)}{\phi}$ as loss, the mean of the assigned data points still minimizes their summed loss, so only the assignment step changes (Banerjee et al., 2005). The Euclidean distance is not a Bregman divergence, which is why it changes the averaging step. Restricting each cluster centroid to be one of the data points assigned to it gives $k$-medoids, which uses only the pairwise distances between data points and therefore applies to data points without numeric feature vectors (Kaufman and Rousseeuw, 1990).

Fig. 3 shows the effect of the number $\nrcluster$ of clusters on the patches of Fig. 1. Each patch is painted with the average color of its cluster, which is image segmentation. With $\nrcluster = 2$, the sky and the mountain are separated from the vegetation. With $\nrcluster = 3$, the mountain and haze form their own cluster. With $\nrcluster = 4$, the vegetation splits into the sunlit meadow and the dark foliage. The clustering error decreases with $\nrcluster$, from $0.034$ for $\nrcluster = 2$ to $0.018$ for $\nrcluster = 3$ and $0.011$ for $\nrcluster = 4$, and it reaches $0$ when every data point is its own cluster centroid.

Figure 3 of the entry kmeans
Figure 3: The photograph at patch resolution, each patch painted with the average color of its cluster under $k$-means with (a) $\nrcluster = 2$, (b) $\nrcluster = 3$, and (c) $\nrcluster = 4$. In a grayscale print the clusters are told apart by brightness: the sky is brightest, mountain and haze are in between, and the vegetation is darkest; in (c) the sunlit meadow and the mountain are close in brightness. Data generated by pythondemos/kmeans.py

Synonyms: $k$-means clustering.

See also: hard clustering, clustering, cluster, cluster centroid, clustering error, Lloyd's algorithm, fixed-point iteration, $k$-means++, Euclidean distance, empirical risk minimization, hypothesis space, loss function, Gaussian mixture model, expectation–maximization, soft clustering, degree of belonging, geometric median, Bregman divergence.

References

  1. Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science+Business Media. doi.org/10.1007/978-0-387-84858-7
  2. MacQueen (1967). Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Symp. Math. Statist. Probab..
  3. Lloyd (1982). Least squares quantization in PCM. IEEE Trans. Inf. Theory. doi.org/10.1109/TIT.1982.1056489
  4. Mahajan et al. (2009). The Planar k-Means Problem is NP-Hard. WALCOM: Algorithms and Computation.
  5. 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
  6. Weiszfeld (1937). Sur le point pour lequel la somme des distances de $n$ points donnés est minimum. Tôhoku Math. J..
  7. Banerjee et al. (2005). Clustering with Bregman Divergences. J. Mach. Learn. Res.. jmlr.org/papers/v6/banerjee05b.html
  8. Kaufman and Rousseeuw (1990). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.

Cite this entry

@misc{dictml_kmeans,
  author = {Jung, Alexander},
  editor = {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-10-27},
  url = {https://dictionaryofml.org/terms/kmeans.html}
}