# cluster centroid

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-19. [HTML](https://dictionaryofml.org/terms/clustercentroid.html) · [typeset PDF](https://dictionaryofml.org/terms/clustercentroid.pdf) · [LaTeX](https://dictionaryofml.org/terms/clustercentroid.tex) · [Python demo](https://dictionaryofml.org/terms/clustercentroid.py) · [notebook](https://dictionaryofml.org/terms/clustercentroid.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

A cluster centroid is a vector that represents a cluster of data points: among all vectors, it minimizes the summed loss over the data points of the cluster, where the loss measures how poorly a vector stands in for a data point. Under the squared Euclidean distance the cluster centroid is the mean of the feature vectors in the cluster, under the Euclidean distance their geometric median, and under the sum of absolute differences the median of each feature. k-means assigns a data point to its nearest cluster centroid, a rule that is a linear classifier whose decision boundary between two cluster centroids is the hyperplane through their midpoint and perpendicular to their difference. The averaging step of Lloyd's algorithm recomputes each cluster centroid as the mean of its cluster, and at a fixed point every cluster centroid is the mean of the data points nearest to it. The mean moves with every data point, so one outlier shifts it by the displacement divided by the size of the cluster, while the geometric median and the coordinate-wise median move little. A soft clustering method, such as a Gaussian mixture model, uses the mean weighted by the degrees of belonging as its cluster centroid. Replacing every data point by its cluster centroid compresses a dataset to $k$ vectors and one cluster index per data point.

## Definition

Consider the $366$ days of $2024$ at Krems an der Donau, each a data point with a feature vector ${\mathbf x} \in \mathbb{R}^{2}$ that holds the morning minimum and the maximum daytime temperature of the day. k-means with $k = 2$ decomposes these days into $192$ cold days and $174$ warm days, and it describes each cluster by a single vector: a typical cold day, $(1.5, 10.5)$, and a typical warm day, $(13.4, 26.1)$. Such a vector is a cluster centroid. A hard clustering method that represents each cluster $c = 1, \ldots,
k$ by a cluster centroid ${{\mathbf w}}^{(c)}
\in \mathbb{R}^{d}$ assigns a data point to the cluster whose cluster centroid is nearest (Bishop, 2006, Sect. 9.1; Hastie et al., 2009, Sect. 14.3.6), as Fig. 1(a) shows for the days at Krems.

Which vector represents a cluster best is decided by a loss function $L\left({\mathbf x},{\mathbf w} \right)$ that measures how poorly a vector ${\mathbf w}$ stands in for the feature vector ${\mathbf x}$ of a data point. The cluster centroid of a cluster with index set $\mathcal{C}^{(c)}
\subseteq \{1, \ldots, m\}$ is a vector that minimizes the summed loss over its data points,

\begin{equation}
\tag{1}
{{\mathbf w}}^{(c)} \in \mathop{\mathrm{arg\,min}}_{{\mathbf w} \in
\mathbb{R}^{d}} \sum_{r \in
\mathcal{C}^{(c)}}
L\left({\mathbf x}^{(r)},{\mathbf w} \right) \text{.}
\end{equation}

For the squared Euclidean distance $L\left({\mathbf x},{\mathbf w} \right) =
\left\lVert {\mathbf x} - {\mathbf w} \right\rVert_{2}^{2}$, the summed loss is a strictly convex quadratic function of ${\mathbf w}$, and its unique minimizer is the mean of the feature vectors,

\begin{equation}
\tag{2}
{{\mathbf w}}^{(c)} =
\frac{1}{\big|\mathcal{C}^{(c)}\big|}
\sum_{r \in \mathcal{C}^{(c)}}
{\mathbf x}^{(r)} \text{,}
\end{equation}

since the gradient of the summed loss vanishes exactly where the deviations ${\mathbf x}^{(r)} - {\mathbf w}$ sum to zero (MacQueen, 1967). The two cluster centroids of the days at Krems are the means Eq. (2) of the cold and of the warm days. Under the Euclidean distance itself, $L\left({\mathbf x},{\mathbf w} \right) = \left\lVert {\mathbf x} -
{\mathbf w} \right\rVert_{2}$, the minimizer of the summed loss Eq. (1) is the geometric median of the feature vectors (Boyd and Vandenberghe, 2004, Sect. 8.7.1). It has no closed form and is computed by Weiszfeld's fixed-point iteration (Weiszfeld, 1937),

\begin{equation}
\tag{3}
{\mathbf w}^{(t+1)} = \mathcal{F}\big({\mathbf w}^{(t)}\big)
:= \frac{\sum_{r \in \mathcal{C}^{(c)}}
{\mathbf x}^{(r)} \big/
\left\lVert {\mathbf x}^{(r)} - {\mathbf w}^{(t)} \right\rVert_{2}}
{\sum_{r \in \mathcal{C}^{(c)}} 1 \big/
\left\lVert {\mathbf x}^{(r)} - {\mathbf w}^{(t)} \right\rVert_{2}}
\quad \text{for } t = 0, 1, \ldots \text{,}
\end{equation}

a mean of the feature vectors weighted by the reciprocal of their distance to the current iterate. A fixed point of the iteration Eq. (3) that coincides with no feature vector is a point where the unit vectors towards the feature vectors sum to zero, which is the optimality condition of the geometric median, and the summed loss never increases from one iterate to the next (Weiszfeld, 1937). Under the sum of absolute differences, $L\left({\mathbf x},{\mathbf w} \right) = \left\lVert {\mathbf x} -
{\mathbf w} \right\rVert_{1}$, the summed loss separates into one problem per feature, so the cluster centroid holds the median of each feature over the cluster. For the warm days at Krems, the three choices give $(13.4, 26.1)$, $(13.5, 26.0)$, and $(13.7, 26.1)$, within $0.3$ degrees of each other; Weiszfeld's iteration started from the mean stops after $60$ iterations.

For a fixed cluster, the minimization Eq. (1) is empirical risk minimization over the hypothesis space of constant maps $h({\mathbf x}) =
{\mathbf w}$. The cluster centroid is the hypothesis that predicts one vector for every data point of the cluster, and the summed loss is its training error up to the factor $1 / |\mathcal{C}^{(c)}|$. The $k$ cluster centroids together are the model parameters of the hypothesis $h({\mathbf x}) =
{{\mathbf w}}^{(c^{\star}({\mathbf x}))}$ learned by k-means, which sends a feature vector to its nearest cluster centroid,

\begin{equation}
\tag{4}
c^{\star}({\mathbf x}) :=
\mathop{\mathrm{arg\,min}}_{c = 1, \ldots, k}
\left\lVert {\mathbf x} - {{\mathbf w}}^{(c)} \right\rVert_{2}
\text{.}
\end{equation}

The average of the loss $\left\lVert {\mathbf x} -
h({\mathbf x}) \right\rVert_{2}^{2}$ over the dataset is the clustering error. The nearest-centroid rule Eq. (4) is a linear classifier. For two cluster centroids, a feature vector is nearer to ${{\mathbf w}}^{(1)}$ than to ${{\mathbf w}}^{(2)}$ if and only if

\begin{equation}
\tag{5}
\big({{\mathbf w}}^{(2)} - {{\mathbf w}}^{(1)}\big)^{\top}
{\mathbf x} \leq \frac{1}{2} \Big(
\left\lVert {{\mathbf w}}^{(2)} \right\rVert_{2}^{2} -
\left\lVert {{\mathbf w}}^{(1)} \right\rVert_{2}^{2} \Big) \text{,}
\end{equation}

which follows from expanding the two squared Euclidean distances. The decision boundary of the linear rule Eq. (5) is the hyperplane through the midpoint of the two cluster centroids and perpendicular to their difference (Bishop, 2006, Sect. 9.1), the dashed line of Fig. 1(a). Each cluster is an intersection of halfspaces and so a convex region. The rule Eq. (4) also assigns a data point outside the dataset. A day with morning minimum $5$ and maximum $18$ degrees lies at distances $8.3$ and $11.7$ from the two cluster centroids of the days at Krems, so it is a cold day. The same rule serves classification when each class of a labeled dataset is represented by one or several cluster centroids and a new data point receives the label of the nearest one (Hastie et al., 2009, Sect. 13.2.1).

Lloyd's algorithm for k-means alternates the assignment Eq. (4) of every data point with an averaging step that recomputes each cluster centroid as the mean Eq. (2) of the data points assigned to it (Lloyd, 1982). At a fixed point, each cluster centroid is the mean of the data points nearest to it. Two conditions then hold at the same time: each cluster centroid minimizes the summed loss Eq. (1) over its cluster, and each cluster consists of the data points nearest to its cluster centroid (Hastie et al., 2009, Sect. 14.3.6). For the days at Krems, started from the means of the colder and of the warmer half of the days, Lloyd's algorithm reaches this fixed point after $2$ iterations. Changing the loss function changes only the averaging step: the geometric median gives $k$-medians, and restricting the cluster centroid to be one of the data points of its cluster gives $k$-medoids, which needs only the pairwise distances between data points (Hastie et al., 2009, Sect. 14.3.10; Park and Jun, 2009; Shalev-Shwartz and Ben-David, 2014, Sect. 22.2). For a Bregman divergence as loss function, the mean Eq. (2) remains the cluster centroid (Banerjee et al., 2005, Prop. 1).

The mean Eq. (2) moves with every data point of its cluster: adding a vector to one feature vector adds the same vector divided by $|\mathcal{C}^{(c)}|$ to the mean, whatever the other data points are. If the maximum temperature of the hottest warm day at Krems were recorded as $999.9$, a value some archives use to mark a missing record, the mean of the $174$ warm days would move by $965.6 / 174 =
5.5$ degrees (Fig. 1(b)). The geometric median would move by $0.03$ degrees and the coordinate-wise median not at all. The squared Euclidean distance gives the largest distances the largest weight, which is why cluster centroids built from an unsquared norm are less sensitive to outliers (Hastie et al., 2009, Sect. 14.3.10).

A soft clustering method assigns each data point $r$ to every cluster $c$ with a degree of belonging $u_{c}^{(r)} \in [0, 1]$, with $\sum_{c=1}^{k} u_{c}^{(r)}
= 1$. Its cluster centroid is the mean of all feature vectors weighted by their degrees of belonging,

\begin{equation}
\tag{6}
{\boldsymbol \mu}^{(c)} =
\frac{\sum_{r=1}^{m}
u_{c}^{(r)} {\mathbf x}^{(r)}}
{\sum_{r=1}^{m}
u_{c}^{(r)}} \text{,}
\end{equation}

whose denominator is the effective number of data points in the cluster. For a Gaussian mixture model, which represents the cluster $c$ by a multivariate normal distribution with mean ${\boldsymbol \mu}^{(c)}$ and covariance matrix $\mathbf{C}^{(c)}$, the degree of belonging is the posterior distribution of the cluster index, and the weighted mean Eq. (6) is the M-step of the expectation–maximization algorithm for ${\boldsymbol \mu}^{(c)}$ (Bishop, 2006, Sect. 9.2.2). Hard clustering is the case $u_{c}^{(r)} \in \{0, 1\}$, where the weighted mean Eq. (6) is the mean Eq. (2). For the days at Krems, the expectation–maximization algorithm started from the two k-means cluster centroids stops at the means $(3.1, 12.4)$ and $(14.2, 27.5)$, which lie $2.5$ and $1.5$ degrees from them. Of the $366$ days, $58$ have no degree of belonging above $0.8$, and each of them is counted in part by both cluster centroids.

Replacing every data point by its cluster centroid compresses a dataset to $k$ vectors and one cluster index per data point, which is vector quantization. The $366$ days at Krems become two typical days and one bit per day, and a photograph whose pixels are clustered by color becomes a palette of $k$ colors and one palette index per pixel (Bishop, 2006, Sect. 9.1.1; Shalev-Shwartz and Ben-David, 2014, Sect. 22.2). The clustering error is the average distortion of this compression, and minimizing it over the cluster centroids is the task from which Lloyd's algorithm arose (Lloyd, 1982).

![Figure 1 of the entry clustercentroid](https://dictionaryofml.org/terms/fig/clustercentroid-fig1.svg)

*Figure 1: (a) Every $18$th of the $366$ days of $2024$ at Krems, $21$ days, drawn as cold days (circles) or warm days (squares) by the nearer of the two cluster centroids (crosses), the means of the cold and of the warm days; the dashed line is the decision boundary of the nearest-centroid rule, the hyperplane through the midpoint of the two cluster centroids and perpendicular to their difference. (b) The $18$ of the $174$ warm days that fall inside the window (gray squares) and the cluster centroid of all $174$ warm days under three losses: their mean (black cross) under the squared Euclidean distance, their geometric median (filled triangle) under the Euclidean distance, and their coordinate-wise median (filled diamond) under the sum of absolute differences; the dashed arrow leads from the mean to the mean after the maximum temperature of one warm day is replaced by $999.9$ (gray cross), a move of $5.5$ degrees, while the two medians move by $0.03$ degrees and not at all. Data generated by pythondemos/clustercentroid.py*

**See also:** [clustering](https://dictionaryofml.org/terms/clustering.html), [cluster](https://dictionaryofml.org/terms/cluster.html), [clustering error](https://dictionaryofml.org/terms/clusteringerror.html), [$k$-means](https://dictionaryofml.org/terms/kmeans.html), Lloyd's algorithm, [$k$-means++](https://dictionaryofml.org/terms/kmeanspp.html), [hard clustering](https://dictionaryofml.org/terms/hardclustering.html), [soft clustering](https://dictionaryofml.org/terms/softclustering.html), [degree of belonging](https://dictionaryofml.org/terms/dob.html), [Gaussian mixture model](https://dictionaryofml.org/terms/gmm.html), [expectation–maximization](https://dictionaryofml.org/terms/em.html), [mean](https://dictionaryofml.org/terms/mean.html), median, geometric median, Euclidean distance, [norm](https://dictionaryofml.org/terms/norm.html), [outlier](https://dictionaryofml.org/terms/outlier.html), [linear classifier](https://dictionaryofml.org/terms/linclass.html), [decision boundary](https://dictionaryofml.org/terms/decisionboundary.html), hyperplane, fixed-point iteration, [empirical risk minimization](https://dictionaryofml.org/terms/erm.html), [hypothesis](https://dictionaryofml.org/terms/hypothesis.html), model parameter, Bregman divergence, [feature vector](https://dictionaryofml.org/terms/featurevec.html).

## References

- Bishop (2006). Pattern Recognition and Machine Learning. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-45528-0>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- MacQueen (1967). Some methods for classification and analysis of multivariate observations. *Proc. Fifth Berkeley Symp. Math. Statist. Probab.*.
- Boyd and Vandenberghe (2004). Convex Optimization. *Cambridge Univ. Press*. <https://doi.org/10.1017/CBO9780511804441>
- Weiszfeld (1937). Sur le point pour lequel la somme des distances de $n$ points donnés est minimum. *Tôhoku Math. J.*.
- Lloyd (1982). Least squares quantization in PCM. *IEEE Trans. Inf. Theory*. <https://doi.org/10.1109/TIT.1982.1056489>
- Park and Jun (2009). A simple and fast algorithm for K-medoids clustering. *Expert Syst. Appl.*. <https://doi.org/10.1016/j.eswa.2008.01.039>
- Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. *Cambridge Univ. Press*. <https://doi.org/10.1017/cbo9781107298019>
- Banerjee et al. (2005). Clustering with Bregman Divergences. *J. Mach. Learn. Res.*. <https://jmlr.org/papers/v6/banerjee05b.html>

## Cite this entry

```bibtex
@misc{dictml_clustercentroid,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {cluster centroid},
  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/clustercentroid.html}
}
```
