\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{\dataset}{\mathcal{D}}
\newcommand{\defeq}{:=}
\newcommand{\feature}{x}
\newcommand{\featuredim}{d}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\lossfunc}[2]{L\left(#1,#2 \right)}
\newcommand{\mI}{\mathbf{I}}
\newcommand{\meanvec}[1]{{\bm \mu}^{(#1)}}
\newcommand{\mvnormal}[2]{\mathcal{N}\left(#1,#2\right)}
\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{clustering error}

\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}
The clustering error of a clustering is the average,
		over the data points of a dataset, of a loss that
		measures how poorly a data point is represented by the
		cluster it is assigned to. For hard clustering methods
		that represent a cluster by a cluster centroid, such as
		$k$-means, the loss is the squared Euclidean distance to the
		nearest cluster centroid. The Euclidean distance itself or the
		sum of absolute differences gives a variant whose best
		cluster centroids are medians instead of means and
		which is less sensitive to outliers. Soft clustering
		with a Gaussian mixture model (GMM) uses the negative logarithm of the probability density function (pdf) as
		the loss, so its clustering error is the negative
		log-likelihood function per data point. In every case the
		clustering error is the training error of a hypothesis, and
		minimizing it is empirical risk minimization (ERM). Lloyd's algorithm and the expectation–maximization (EM)
		algorithm never increase it but may stop at a local minimum.
		The clustering error is non-increasing in the number of
		clusters and vanishes when every data point is its own
		cluster, so it cannot choose that number.

\subsection{Definition}
Consider the $366$ days of one
		year 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.
		A clustering method decomposes these days into a few
		clusters, and clustering methods differ in how they
		represent a cluster. One representation is a
		cluster centroid, a vector $\clustercentroid{\clusteridx} \in
		\reals^{\featuredim}$ for each cluster $\clusteridx = 1,
		\ldots, \nrcluster$; each data point is assigned to the
		cluster with the nearest cluster centroid, which is the
		hard clustering delivered by $k$-means. A natural measure
		of how well the cluster centroids represent the dataset
		$\dataset = \{\featurevec^{(1)}, \ldots,
		\featurevec^{(\samplesize)}\}$ is the average, over the
		data points, of the minimum squared Euclidean distance to the
		cluster centroids (Bishop, 2006, Sect.~9.1, Eq.~(9.1)),
		\begin{equation}
			\label{equ_clusteringerror_kmeans_dict}
			\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize}
			\min_{\clusteridx = 1, \ldots, \nrcluster}
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx}}{2}^{2} \text{.}
		\end{equation}
		The clustering error of $k$-means is the average
		\eqref{equ_clusteringerror_kmeans_dict}. For two
		cluster centroids and the days at Krems, it is $42.0$;
		Fig.~\ref{fig_clusteringerror_dict}(a) draws the distances
		it averages for some of the days.
\par
		In the end, the clustering error
		\eqref{equ_clusteringerror_kmeans_dict} is the average of a
		loss, for a special choice of the loss function. The
		hypothesis learned by $k$-means is the map
		$\hypothesis(\featurevec) =
		\clustercentroid{\clusteridx^{\star}(\featurevec)}$ that sends a
		feature vector to its nearest cluster centroid, with
		$\clusteridx^{\star}(\featurevec) = \argmin_{\clusteridx = 1,
		\ldots, \nrcluster} \normgeneric{\featurevec -
		\clustercentroid{\clusteridx}}{2}$. The loss of a
		data point is (Shalev-Shwartz and Ben-David, 2014, Sect.~22.2)
		\begin{equation}
			\label{equ_clusteringerror_loss_dict}
			\lossfunc{\featurevec}{\hypothesis} \defeq
			\normgeneric{\featurevec - \hypothesis(\featurevec)}{2}^{2}
			= \min_{\clusteridx = 1, \ldots, \nrcluster}
			\normgeneric{\featurevec - \clustercentroid{\clusteridx}}{2}^{2}
			\text{.}
		\end{equation}
		A data point carries no label here: the loss
		\eqref{equ_clusteringerror_loss_dict} compares the feature vector
		with the cluster centroid that stands in for it. The
		clustering error is the average of the loss
		\eqref{equ_clusteringerror_loss_dict} over the dataset, so it
		is the training error of the hypothesis $\hypothesis$, and
		choosing cluster centroids that minimize it is empirical risk minimization (ERM) over
		the hypothesis space of all maps of this form.
\par
		The squared Euclidean distance in the loss
		\eqref{equ_clusteringerror_loss_dict} is one choice among several. Replacing the squared norm by
		the norm itself, $\lossfunc{\featurevec}{\hypothesis} =
		\normgeneric{\featurevec - \hypothesis(\featurevec)}{2}$, or by the
		$\ell_{1}$-norm $\normgeneric{\featurevec -
		\hypothesis(\featurevec)}{1}$, the sum of the absolute differences
		of the features, keeps the assignment of a data point
		to its nearest cluster centroid. It changes which
		cluster centroid is best for a given cluster. Under the
		squared Euclidean distance, it is the mean of the
		data points in the cluster, under the Euclidean distance
		their geometric median (GM), computed by Weiszfeld's
		fixed-point iteration (Weiszfeld, 1937), and under the
		$\ell_{1}$-norm the median of each feature separately.
		A single far-away data point, an outlier, moves the
		mean of its cluster in proportion to its distance but
		moves either median little, so the clustering errors built
		from an unsquared norm are less sensitive to outliers
		(Hastie et al., 2009, Sect.~14.3.10). For the days
		at Krems and two cluster centroids, the three choices assign
		more than $99$ percent of the days to the same cluster. Their
		clustering errors, $42.0$, $5.8$, and $7.6$, are not comparable,
		since the first is measured in squared degrees and the other two in
		degrees. The squared Euclidean distance can also be replaced by a
		Bregman divergence, for which the mean remains the best
		cluster centroid (Banerjee et al., 2005).
\par
		Another choice is used by soft clustering methods, which
		represent a cluster by a probability distribution rather than by a
		single vector and assign each data point to every
		cluster with a degree of belonging. A Gaussian mixture model (GMM) represents a
		clustering by its model parameters: the cluster
		$\clusteridx$ is a multivariate normal distribution with mean
		$\meanvec{\clusteridx}$ and covariance matrix $\covmtx{\clusteridx}$,
		chosen with probability $p_{\clusteridx}$. The clustering
		error of these model parameters is the negative
		log-likelihood function of the dataset per data point
		(Bishop, 2006, Sect.~9.2, Eq.~(9.14)),
		\begin{equation}
			\label{equ_clusteringerror_gmm_dict}
			- \frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize} \ln
			\sum_{\clusteridx=1}^{\nrcluster} p_{\clusteridx}
			\mvnormal{\meanvec{\clusteridx}}{\covmtx{\clusteridx}}
			\big(\featurevec^{(\sampleidx)}\big) \text{,}
		\end{equation}
		again the average of a loss, the negative logarithm of the
		probability density function (pdf) at the feature vector. Minimizing the clustering error
		\eqref{equ_clusteringerror_gmm_dict} is maximum likelihood
		estimation of the model parameters (Bishop, 2006, Sect.~9.2).
		The $k$-means clustering error is a limit of this choice: for
		equal probabilities $p_{\clusteridx} = 1/\nrcluster$ and
		covariance matrices $\covmtx{\clusteridx} = \sigma^{2} \mI$,
		the loss of a data point in the clustering error
		\eqref{equ_clusteringerror_gmm_dict} is, as $\sigma \to 0$ and up
		to the factor $1/(2\sigma^{2})$ and an additive constant, the
		loss \eqref{equ_clusteringerror_loss_dict}
		(Bishop, 2006, Sect.~9.3.2).
\par
		Each of these clustering errors is a non-convex
		function of the cluster centroids or
		model parameters: with a single data point at $\feature = 0$
		and two scalar cluster centroids $w^{(1)}, w^{(2)} \in
		\reals$, the clustering error
		\eqref{equ_clusteringerror_kmeans_dict} is $\min\{(w^{(1)})^{2},
		(w^{(2)})^{2}\}$, which vanishes at $(1, 0)$ and at $(0, 1)$ but
		not at their midpoint. Lloyd's algorithm for $k$-means
		(Lloyd, 1982) and the expectation–maximization (EM) algorithm for a GMM are
		fixed-point iterations that never increase the clustering error and
		stop at a fixed point, which can be a local minimum
		rather than a global one (Bishop, 2006, Sect.~9.1). They are
		therefore run from several initializations, keeping the run with
		the smallest clustering error
		(Hastie et al., 2009, Sect.~14.3.6). For the days at
		Krems, Lloyd's algorithm started from the means of the
		colder and of the warmer half of the days lowers the clustering
		error from $43.0$ to $42.0$ in two iterations. At the
		fixed point, $192$ cold days share the cluster centroid
		$(1.5, 10.5)$ and $174$ warm days the cluster centroid
		$(13.4, 26.1)$; every day of January and February is a cold day,
		and every day of July and August a warm day.
\par
		The clustering error cannot choose the number $\nrcluster$ of
		clusters. An additional cluster centroid placed on any
		data point cannot increase it, so the smallest clustering
		error attainable with $\nrcluster$ cluster centroids is
		non-increasing in $\nrcluster$, and it is zero at $\nrcluster =
		\samplesize$, where every data point is its own
		cluster centroid. This is the training error of model selection
		in another guise: a larger hypothesis space never has a larger
		training error. Fig.~\ref{fig_clusteringerror_dict}(b) shows the
		curve for the days at Krems. With one cluster centroid the
		clustering error is the sum of the variances of the two
		features, $138.9$; the second cluster centroid removes
		$96.8$ of it, more than the next six cluster centroids
		together ($32.9$). Such a kink in the curve is the usual informal
		guide to $\nrcluster$
		(Hastie et al., 2009, Sect.~14.3.11); otherwise
		$\nrcluster$ is a hyperparameter, chosen by a criterion that
		penalizes it or by the performance of a prediction task that
		uses the clusters.
		\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.03,0.97)}, anchor=north west},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) $21$ of the $366$ days and two cluster centroids},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=50]
			\addplot[gray!70, dashed, thin, forget plot, -,
				quiver={u=\thisrow{ctmin}-\thisrow{tmin}, v=\thisrow{ctmax}-\thisrow{tmax}}]
				table[col sep=comma, x=tmin, y=tmax]{clusteringerror_points_plot.csv};
			\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]{clusteringerror_points_plot.csv};
			\addlegendentry{cold days (circles)}
			\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]{clusteringerror_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addplot[only marks, mark=x, mark size=3pt, thick, black,
				restrict expr to domain={\thisrow{lossid}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{clusteringerror_centroids.csv};
			\addlegendentry{cluster centroids (crosses)}
			\nextgroupplot[
				xlabel={number of clusters $\nrcluster$\\(b) smallest clustering error found},
				ylabel={clustering error}, xtick={1,...,8}, ymin=0]
			\addplot[black, thick, mark=*, mark size=1.5pt]
				table[col sep=comma, x=k, y=error]{clusteringerror_curve.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 two cluster centroids (crosses); the
			clustering error \eqref{equ_clusteringerror_kmeans_dict}
			averages the squared lengths of the dashed segments over all
			$366$ days. (b) The smallest clustering error found with
			$\nrcluster = 1, \ldots, 8$ cluster centroids: it falls
			with $\nrcluster$ and would reach zero at $\nrcluster = 366$.
			Data generated by \texttt{pythondemos/clusteringerror.py}
			\label{fig_clusteringerror_dict}}
		\end{figure}

\subsection{Cross References}
clustering, cluster, cluster centroid, hard clustering, soft clustering, degree of belonging, $k$-means, Lloyd's algorithm, GMM, EM, maximum likelihood, loss, loss function, training error, ERM, Euclidean distance, norm, GM, median, Bregman divergence, outlier, hyperparameter, model selection

\subsection{References}
\begin{enumerate}
  \item Banerjee et al. (2005). Clustering with Bregman Divergences. J. Mach. Learn. Res., 6, pp.~1705--1749.
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Lloyd (1982). Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2), pp.~129--137.
  \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}
