Dictionary of Applied Machine Learning: 147 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-11-19
Readiness 88/100
See also $k$-means cluster centroid clustering error clustering cluster hard clustering convex empirical risk minimization
$k$-means++ is a randomized rule for the initial cluster centroids of Lloyd's algorithm: the first is a data point drawn uniformly at random, each further one a data point drawn with probability proportional to its squared Euclidean distance to the nearest cluster centroid already chosen. The initial cluster centroids are thereby spread across the dataset, so that Lloyd's algorithm rarely starts with several of them in the same cluster. The expected clustering error of the initial cluster centroids is at most $8 (\ln k + 2)$ times the smallest clustering error attainable with $k$ cluster centroids, for every dataset and before a single iteration of Lloyd's algorithm; uniform seeding has no such guarantee. Since Lloyd's algorithm never increases the clustering error, the bound also holds for its output. The seeding changes neither the fixed-point iteration of Lloyd's algorithm nor its fixed points; it selects the starting point and thereby which fixed point is reached. On the patches of a photograph with three clusters, Lloyd's algorithm reaches the best clustering found from $64\%$ of the $k$-means++ seeds and from $48\%$ of the uniform seeds, and it needs fewer iterations.

kmeanspp.py, which recomputes what the entry states: the script block by block · open in ColabB-patchesLloyd's algorithm for $k$-means needs $k$ initial cluster centroids before its first iteration, and the clustering it delivers depends on them. Consider a photograph of the Oetscher massif cut into $972$ square patches, each a data point with a feature vector ${\mathbf x} \in \mathbb{R}^{2}$ that holds its average greenness and blueness. Vegetation, mountain and haze, and sky form three clusters of patches, and the best cluster centroids found for $k = 3$ have the clustering error $0.018$. Started from three patches drawn uniformly at random, Lloyd's algorithm ends in $516$ of $1000$ runs at a different fixed point with clustering error $0.025$: two cluster centroids share the vegetation, and the mountain patches are divided between the sky cluster centroid and one of the vegetation cluster centroids. $k$-means++ is a randomized rule for the initial cluster centroids that spreads them across the dataset (Arthur and Vassilvitskii, 2007). Started from its seeds, Lloyd's algorithm ends at the worse fixed point in $359$ of $1000$ runs.
B-toyThe clustering error is not a convex function of
the cluster centroids. Lloyd's algorithm never increases
it and stops at a fixed point, which can be a local
minimum rather than a global one; which fixed point is
reached depends on the initial cluster centroids
(Bishop, 2006, Sect. 9.1;
Hastie et al., 2009, Sect. 14.3.6). The usual
remedy is to run Lloyd's algorithm from several initial
choices and keep the run with the smallest clustering error
(Hastie et al., 2009, Sect. 14.3.6), the simplest
initial choice being $k$ data points drawn
uniformly at random (Bishop, 2006, Sect. 9.1). Uniform
seeding tends to place several initial cluster centroids
in the largest cluster: $566$ of the $972$ patches are
vegetation, so all three uniform seeds are vegetation patches
with probability $0.20$. $k$-means++ draws the seeds one
after the other and lets the data points far from the
seeds chosen so far be the likely next ones
(Algorithm 1). The first seed
${{\mathbf w}}^{(1)}$ is a data point drawn uniformly at
random from the dataset $\mathcal{D} = \{{\mathbf x}^{(1)},
\ldots, {\mathbf x}^{(m)}\}$. For $c = 2,
\ldots, k$, the seed ${{\mathbf w}}^{(c)}$ is
a data point drawn with probability proportional to its
squared Euclidean distance to the nearest seed already chosen: it
equals the data point ${\mathbf x}^{(r)}$, for
$r = 1, \ldots, m$, with probability
\begin{equation}
\label{equ_kmeanspp_seeding_dict}
\mathbb{P}\left({{\mathbf w}}^{(c)} = {\mathbf x}^{(r)}\right)
= \frac{\min_{c' = 1, \ldots, c - 1}
\left\lVert {\mathbf x}^{(r)} -
{{\mathbf w}}^{(c')} \right\rVert_{2}^{2}}
{\sum_{r' = 1}^{m}
\min_{c' = 1, \ldots, c - 1}
\left\lVert {\mathbf x}^{(r')} -
{{\mathbf w}}^{(c')} \right\rVert_{2}^{2}} \text{.}
\end{equation}
A data point that is already a seed has probability
$0$ under the seeding rule \(\eqref{equ_kmeanspp_seeding_dict}\), and
a data point twice as far from the seeds as another is twice
as likely to be drawn. Given a vegetation patch as the first
seed, the second seed is a sky patch with probability
$0.74$ under the seeding rule \(\eqref{equ_kmeanspp_seeding_dict}\)
and $0.21$ under uniform seeding, the share of sky patches
(Fig. 2(a)). It is another vegetation
patch with probability $0.06$ against $0.58$. The seeds
are the input of Lloyd's algorithm, and the combination of
the seeding with Lloyd's algorithm is what Arthur and Vassilvitskii (2007)
named $k$-means++. Ostrovsky et al. (2006) proposed the same
seeding independently.
B-plotThe seeding changes nothing about Lloyd's algorithm itself.
With the cluster centroids collected in one vector
${\mathbf w} = ({{\mathbf w}}^{(1)}, \ldots,
{{\mathbf w}}^{(k)})$, Lloyd's algorithm is the
fixed-point iteration ${\mathbf w}^{(t+1)} =
\mathcal{F}({\mathbf w}^{(t)})$ for $t = 0, 1,
\ldots$. The operator $\mathcal{F}$ applies one
assignment step and one averaging step. Its fixed points
are cluster centroids that each equal the mean of the
data points assigned to them, and its convergence
follows from the monotone decrease of the clustering error.
$k$-means++ only chooses the starting point ${\mathbf w}^{(0)}$,
and with it the fixed point that is reached and the number
of iterations to reach it: on the patches,
Lloyd's algorithm needs $10.0$ iterations on average
from $k$-means++ seeds and $12.7$ from uniform seeds. The
seeding itself is not an iterative method but $k$
draws, so no fixed-point view applies to it; its output is an
RV, and the guarantee \(\eqref{equ_kmeanspp_bound_dict}\) is a
statement about its expectation. Nor does the seeding
exclude the worse fixed point; it makes it rarer
(Fig. 2(b)). On the patches, $35.9\%$ of
the runs from $k$-means++ seeds and $51.6\%$ of the runs from
uniform seeds end at the clustering error $0.025$, so with
five restarts, keeping the run with the smallest
clustering error, all five miss the best clustering
with probability $0.6\%$ against $3.7\%$. In terms of
empirical risk minimization (ERM), $k$-means minimizes the training error of a
hypothesis that maps a feature vector to its nearest
cluster centroid; the seeding changes neither the
hypothesis space nor the loss function, only the
optimization method and thereby the local minimum of the
training error that it finds.
pythondemos/kmeanspp.py
See also: $k$-means, Lloyd's algorithm, cluster centroid, clustering error, clustering, cluster, hard clustering, fixed point, fixed-point iteration, Euclidean distance, minimum, convex, empirical risk minimization, image segmentation.
@misc{dictml_kmeanspp,
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-11-20},
url = {https://dictionaryofml.org/terms/kmeanspp.html}
}