\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\clustercentroid}[1]{{\vw}^{(#1)}}
\newcommand{\clusteridx}{c}
\newcommand{\covmtx}[1]{\mathbf{C}^{(#1)}}
\newcommand{\datacluster}[1]{\mathcal{C}^{(#1)}}
\newcommand{\defeq}{:=}
\newcommand{\dob}[2]{u_{#1}^{(#2)}}
\newcommand{\featuredim}{d}
\newcommand{\featurevec}{\vx}
\newcommand{\fixedpointop}{\mathcal{F}}
\newcommand{\hypothesis}{h}
\newcommand{\iteridx}{t}
\newcommand{\lossfunc}[2]{L\left(#1,#2 \right)}
\newcommand{\meanvec}[1]{{\bm \mu}^{(#1)}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrcluster}{k}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{cluster centroid}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{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 (GM), 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 GM and the
		coordinate-wise median move little. A soft clustering
		method, such as a Gaussian mixture model (GMM), 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 $\nrcluster$ vectors and one
		cluster index per data point.

\subsection{Definition}
Consider the $366$ days of
		$2024$ at Krems an der Donau, each a data point with a
		feature vector $\featurevec \in \reals^{2}$ that holds the
		morning minimum and the maximum daytime temperature of the day.
		$k$-means with $\nrcluster = 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 $\clusteridx = 1, \ldots,
		\nrcluster$ by a cluster centroid $\clustercentroid{\clusteridx}
		\in \reals^{\featuredim}$ 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.~\ref{fig_clustercentroid_dict}(a) shows for the days at
		Krems.
\par
		Which vector represents a cluster best is decided by
		a loss function $\lossfunc{\featurevec}{\vw}$ that measures how
		poorly a vector $\vw$ stands in for the feature vector
		$\featurevec$ of a data point. The cluster centroid of a
		cluster with index set $\datacluster{\clusteridx}
		\subseteq \{1, \ldots, \samplesize\}$ is a vector that
		minimizes the summed loss over its data points,
		\begin{equation}
			\label{equ_clustercentroid_def_dict}
			\clustercentroid{\clusteridx} \in \argmin_{\vw \in
			\reals^{\featuredim}} \sum_{\sampleidx \in
			\datacluster{\clusteridx}}
			\lossfunc{\featurevec^{(\sampleidx)}}{\vw} \text{.}
		\end{equation}
		For the squared Euclidean distance $\lossfunc{\featurevec}{\vw} =
		\normgeneric{\featurevec - \vw}{2}^{2}$, the summed loss
		is a strictly convex quadratic function of $\vw$,
		and its unique minimizer is the mean of the
		feature vectors,
		\begin{equation}
			\label{equ_clustercentroid_mean_dict}
			\clustercentroid{\clusteridx} =
			\frac{1}{\big|\datacluster{\clusteridx}\big|}
			\sum_{\sampleidx \in \datacluster{\clusteridx}}
			\featurevec^{(\sampleidx)} \text{,}
		\end{equation}
		since the gradient of the summed loss vanishes
		exactly where the deviations $\featurevec^{(\sampleidx)} - \vw$
		sum to zero (MacQueen, 1967). The two cluster centroids of
		the days at Krems are the means
		\eqref{equ_clustercentroid_mean_dict} of the cold and of the warm
		days. Under the Euclidean distance itself,
		$\lossfunc{\featurevec}{\vw} = \normgeneric{\featurevec -
		\vw}{2}$, the minimizer of the summed loss
		\eqref{equ_clustercentroid_def_dict} is the geometric median (GM)
		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}
			\label{equ_clustercentroid_weiszfeld_dict}
			\vw^{(\iteridx+1)} = \fixedpointop\big(\vw^{(\iteridx)}\big)
			\defeq \frac{\sum_{\sampleidx \in \datacluster{\clusteridx}}
			\featurevec^{(\sampleidx)} \big/
			\normgeneric{\featurevec^{(\sampleidx)} - \vw^{(\iteridx)}}{2}}
			{\sum_{\sampleidx \in \datacluster{\clusteridx}} 1 \big/
			\normgeneric{\featurevec^{(\sampleidx)} - \vw^{(\iteridx)}}{2}}
			\quad \text{for } \iteridx = 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
		\eqref{equ_clustercentroid_weiszfeld_dict} 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 GM, and the summed
		loss never increases from one iterate to the next
		(Weiszfeld, 1937). Under the sum of absolute differences,
		$\lossfunc{\featurevec}{\vw} = \normgeneric{\featurevec -
		\vw}{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.
\par
		For a fixed cluster, the minimization
		\eqref{equ_clustercentroid_def_dict} is empirical risk minimization (ERM) over the
		hypothesis space of constant maps $\hypothesis(\featurevec) =
		\vw$. 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 / |\datacluster{\clusteridx}|$. The $\nrcluster$ cluster
		centroids together are the model parameters of the
		hypothesis $\hypothesis(\featurevec) =
		\clustercentroid{\clusteridx^{\star}(\featurevec)}$ learned by
		$k$-means, which sends a feature vector to its nearest
		cluster centroid,
		\begin{equation}
			\label{equ_clustercentroid_assign_dict}
			\clusteridx^{\star}(\featurevec) \defeq
			\argmin_{\clusteridx = 1, \ldots, \nrcluster}
			\normgeneric{\featurevec - \clustercentroid{\clusteridx}}{2}
			\text{.}
		\end{equation}
		The average of the loss $\normgeneric{\featurevec -
		\hypothesis(\featurevec)}{2}^{2}$ over the dataset is the
		clustering error. The nearest-centroid rule
		\eqref{equ_clustercentroid_assign_dict} is a linear classifier. For
		two cluster centroids, a feature vector is nearer to
		$\clustercentroid{1}$ than to $\clustercentroid{2}$ if and only
		if
		\begin{equation}
			\label{equ_clustercentroid_bisector_dict}
			\big(\clustercentroid{2} - \clustercentroid{1}\big)^{\top}
			\featurevec \leq \frac{1}{2} \Big(
			\normgeneric{\clustercentroid{2}}{2}^{2} -
			\normgeneric{\clustercentroid{1}}{2}^{2} \Big) \text{,}
		\end{equation}
		which follows from expanding the two squared Euclidean distances.
		The decision boundary of the linear rule
		\eqref{equ_clustercentroid_bisector_dict} 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.~\ref{fig_clustercentroid_dict}(a). Each
		cluster is an intersection of halfspaces and so a
		convex region. The rule
		\eqref{equ_clustercentroid_assign_dict} 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).
\par
		Lloyd's algorithm for $k$-means alternates the assignment
		\eqref{equ_clustercentroid_assign_dict} of every data point
		with an averaging step that recomputes each cluster centroid as
		the mean \eqref{equ_clustercentroid_mean_dict} 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
		\eqref{equ_clustercentroid_def_dict} 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
		GM 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
		\eqref{equ_clustercentroid_mean_dict} remains the cluster
		centroid (Banerjee et al., 2005, Prop.~1).
\par
		The mean \eqref{equ_clustercentroid_mean_dict} moves with
		every data point of its cluster: adding a
		vector to one feature vector adds the same vector
		divided by $|\datacluster{\clusteridx}|$ 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.~\ref{fig_clustercentroid_dict}(b)). The
		GM 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).
\par
		A soft clustering method assigns each data point
		$\sampleidx$ to every cluster $\clusteridx$ with a
		degree of belonging $\dob{\clusteridx}{\sampleidx} \in [0, 1]$, with
		$\sum_{\clusteridx=1}^{\nrcluster} \dob{\clusteridx}{\sampleidx}
		= 1$. Its cluster centroid is the mean of all
		feature vectors weighted by their degrees of belonging,
		\begin{equation}
			\label{equ_clustercentroid_dob_dict}
			\meanvec{\clusteridx} =
			\frac{\sum_{\sampleidx=1}^{\samplesize}
			\dob{\clusteridx}{\sampleidx} \featurevec^{(\sampleidx)}}
			{\sum_{\sampleidx=1}^{\samplesize}
			\dob{\clusteridx}{\sampleidx}} \text{,}
		\end{equation}
		whose denominator is the effective number of data points
		in the cluster. For a Gaussian mixture model (GMM), which represents the
		cluster $\clusteridx$ by a multivariate normal distribution with mean
		$\meanvec{\clusteridx}$ and covariance matrix $\covmtx{\clusteridx}$,
		the degree of belonging is the posterior distribution of the cluster
		index, and the weighted mean
		\eqref{equ_clustercentroid_dob_dict} is the M-step of the
		expectation–maximization (EM) algorithm for $\meanvec{\clusteridx}$
		(Bishop, 2006, Sect.~9.2.2). Hard clustering is the case
		$\dob{\clusteridx}{\sampleidx} \in \{0, 1\}$, where the weighted
		mean \eqref{equ_clustercentroid_dob_dict} is the mean
		\eqref{equ_clustercentroid_mean_dict}. For the days at Krems, the
		EM 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.
\par
		Replacing every data point by its cluster centroid
		compresses a dataset to $\nrcluster$ 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 $\nrcluster$ 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).
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.7cm},
			width=0.5\linewidth, height=0.44\linewidth,
			axis lines=left,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.97,0.97)}, anchor=north east},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) $21$ of the $366$ days, two cluster centroids},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=50]
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{cluster}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_points_plot.csv};
			\addlegendentry{cold days}
			\addplot[only marks, mark=square, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{cluster}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_points_plot.csv};
			\addlegendentry{warm days}
			\addplot[only marks, mark=x, mark size=3pt, thick, black]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_kmeans.csv};
			\addlegendentry{cluster centroids}
			\addplot[black, dashed, thick]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_boundary.csv};
			\addlegendentry{decision boundary}
			\nextgroupplot[
				xlabel={morning minimum temperature\\(b) the cluster centroid of the warm days},
				ylabel={maximum daytime temperature},
				xmin=12, xmax=15.5, ymin=23.5, ymax=33]
			\addplot[only marks, mark=square, mark size=1.5pt, gray]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_warm_plot.csv};
			\addplot[gray, dashed, thick, quiver={u=\thisrow{dtmin}, v=\thisrow{dtmax}, every arrow/.append style={-stealth}}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_shift.csv};
			\addplot[only marks, mark=x, mark size=3pt, thick, gray,
				restrict expr to domain={\thisrow{kindid}+10*\thisrow{corrupted}}{10:10}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_centroids.csv};
			\addplot[only marks, mark=x, mark size=3pt, thick, black,
				restrict expr to domain={\thisrow{kindid}+10*\thisrow{corrupted}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_centroids.csv};
			\addplot[only marks, mark=triangle*, mark size=2.2pt, black,
				restrict expr to domain={\thisrow{kindid}+10*\thisrow{corrupted}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_centroids.csv};
			\addplot[only marks, mark=diamond*, mark size=2.4pt, black,
				restrict expr to domain={\thisrow{kindid}+10*\thisrow{corrupted}}{2:2}]
				table[col sep=comma, x=tmin, y=tmax]{clustercentroid_centroids.csv};
		\end{groupplot}
		\end{tikzpicture}
		\caption{(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 GM
			(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
			\texttt{pythondemos/clustercentroid.py}
			\label{fig_clustercentroid_dict}}
		\end{figure}

\subsection{Cross References}
clustering, cluster, clustering error, $k$-means, Lloyd's algorithm, $k$-means++, hard clustering, soft clustering, degree of belonging, GMM, EM, mean, median, GM, Euclidean distance, norm, outlier, linear classifier, decision boundary, hyperplane, fixed-point iteration, ERM, hypothesis, model parameter, Bregman divergence, feature vector

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Boyd and Vandenberghe (2004). Convex Optimization. Cambridge Univ. Press, Cambridge, U.K.
  \item Banerjee et al. (2005). Clustering with Bregman Divergences. J. Mach. Learn. Res., 6(58), pp.~1705--1749.
  \item Lloyd (1982). Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2), pp.~129--137.
  \item MacQueen (1967). Some methods for classification and analysis of multivariate observations. In: Proc. Fifth Berkeley Symp. Math. Statist. Probab., pp.~281--297. University of California Press.
  \item Park and Jun (2009). A simple and fast algorithm for K-medoids clustering. Expert Syst. Appl., 36(2, Part 2), pp.~3336--3341.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \item Weiszfeld (1937). Sur le point pour lequel la somme des distances de $n$ points donnés est minimum. T\^ohoku Math. J., 43, pp.~355--386.
  \item Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed., Springer Science+Business Media, New York, NY, USA.
\end{enumerate}

\end{document}
