\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).
\newcommand{\clustercentroid}[1]{{\vw}^{(#1)}}
\newcommand{\clusteridx}{c}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\expect}{\mathbb{E} }
\newcommand{\feature}{x}
\newcommand{\featurevec}{\vx}
\newcommand{\fixedpointop}{\mathcal{F}}
\newcommand{\iteridx}{t}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrcluster}{k}
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\weights}{\vw}

\begin{document}

\section{$k$-means++}

\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}
$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 \nrcluster + 2)$ times
		the smallest clustering error attainable with $\nrcluster$
		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.

\subsection{Definition}
Lloyd's algorithm for
		$k$-means needs $\nrcluster$ 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 $\featurevec \in \reals^{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 $\nrcluster = 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.
\par
		The 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 $\nrcluster$ 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~\ref{alg_kmeanspp_dict}). The first seed
		$\clustercentroid{1}$ is a data point drawn uniformly at
		random from the dataset $\dataset = \{\featurevec^{(1)},
		\ldots, \featurevec^{(\samplesize)}\}$. For $\clusteridx = 2,
		\ldots, \nrcluster$, the seed $\clustercentroid{\clusteridx}$ is
		a data point drawn with probability proportional to its
		squared Euclidean distance to the nearest seed already chosen: it
		equals the data point $\featurevec^{(\sampleidx)}$, for
		$\sampleidx = 1, \ldots, \samplesize$, with probability
		\begin{equation}
			\label{equ_kmeanspp_seeding_dict}
			\prob{\clustercentroid{\clusteridx} = \featurevec^{(\sampleidx)}}
			= \frac{\min_{\clusteridx' = 1, \ldots, \clusteridx - 1}
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx'}}{2}^{2}}
			{\sum_{\sampleidx' = 1}^{\samplesize}
			\min_{\clusteridx' = 1, \ldots, \clusteridx - 1}
			\normgeneric{\featurevec^{(\sampleidx')} -
			\clustercentroid{\clusteridx'}}{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.~\ref{fig_kmeanspp_dict}(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.
		\begin{algorithm}[H]
		\caption{$k$-means++ seeding (Arthur and Vassilvitskii, 2007, Sect.~2.2)
			\label{alg_kmeanspp_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} feature vectors $\featurevec^{(1)},
				\ldots, \featurevec^{(\samplesize)}$, cluster count
				$\nrcluster$
			\State draw $\clustercentroid{1}$ uniformly at random from
				$\{\featurevec^{(1)}, \ldots, \featurevec^{(\samplesize)}\}$
			\For{$\clusteridx = 2, \ldots, \nrcluster$}
				\State draw $\clustercentroid{\clusteridx}$ from
					$\{\featurevec^{(1)}, \ldots,
					\featurevec^{(\samplesize)}\}$ with the
					probabilities \eqref{equ_kmeanspp_seeding_dict}
			\EndFor
			\Statex \textbf{Output:} initial cluster centroids
				$\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster}$
				for Lloyd's algorithm
		\end{algorithmic}
		\end{algorithm}
		Fig.~\ref{fig_kmeanspp_toy_dict} shows the effect of the seeds on
		four data points with feature vectors $(-5, 1)^{\top}$,
		$(-5, -1)^{\top}$, $(5, 1)^{\top}$, and $(5, -1)^{\top}$ and
		$\nrcluster = 2$. Two seeds on opposite sides lead
		Lloyd's algorithm to the left/right split with
		cluster centroids $(\pm 5, 0)^{\top}$ and
		clustering error $1$, the smallest possible. Two seeds on
		the same side assign each right-hand data point to the seed
		at the same height, so the first averaging step delivers the
		cluster centroids $(0, \pm 1)^{\top}$. These are a
		fixed point of Lloyd's algorithm, and the top/bottom
		split they define has clustering error $25$. Uniform
		seeding draws two seeds on the same side with probability
		$1/3$, two of the six pairs. Under $k$-means++, the second seed
		is the other data point on the side of the first with
		probability $4/(4 + 100 + 104) = 1/52$ by the seeding rule
		\eqref{equ_kmeanspp_seeding_dict}. The expected
		clustering error after Lloyd's algorithm is therefore
		$9$ under uniform seeding and $1.46$ under $k$-means++.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}[x=0.35cm, y=0.35cm,
				dot/.style={circle, draw=black, fill=black,
					inner sep=0pt, minimum size=4pt},
				sq/.style={rectangle, draw=black, fill=black,
					inner sep=0pt, minimum size=4pt},
				seed/.style={circle, draw=black, thick, fill=none,
					inner sep=0pt, minimum size=8pt}]
				% --- (a) seeds on opposite sides: left/right split ---
				\begin{scope}
					\draw[->, gray!60] (-7,0) -- (7,0) node[right,
						black, font=\scriptsize] {$\feature_{1}$};
					\draw[->, gray!60] (0,-2.2) -- (0,2.4)
						node[above, black, font=\scriptsize]
						{$\feature_{2}$};
					\node[dot] at (-5,1) {};
					\node[dot] at (-5,-1) {};
					\node[sq] at (5,1) {};
					\node[sq] at (5,-1) {};
					\node[seed] at (-5,1) {};
					\node[seed] at (5,1) {};
					\draw[thick] (-5.4,-0.4) -- (-4.6,0.4) (-5.4,0.4) -- (-4.6,-0.4);
					\draw[thick] (4.6,-0.4) -- (5.4,0.4) (4.6,0.4) -- (5.4,-0.4);
					\node[font=\scriptsize, anchor=north] at (0,-2.4)
						{(a) seeds on opposite sides: left/right split};
				\end{scope}
				% --- (b) seeds on the same side: top/bottom split ---
				\begin{scope}[xshift=5.6cm]
					\draw[->, gray!60] (-7,0) -- (7,0) node[right,
						black, font=\scriptsize] {$\feature_{1}$};
					\draw[->, gray!60] (0,-2.2) -- (0,2.4)
						node[above, black, font=\scriptsize]
						{$\feature_{2}$};
					\node[dot] at (-5,1) {};
					\node[sq] at (-5,-1) {};
					\node[dot] at (5,1) {};
					\node[sq] at (5,-1) {};
					\node[seed] at (-5,1) {};
					\node[seed] at (-5,-1) {};
					\draw[thick] (-0.4,0.6) -- (0.4,1.4) (-0.4,1.4) -- (0.4,0.6);
					\draw[thick] (-0.4,-1.4) -- (0.4,-0.6) (-0.4,-0.6) -- (0.4,-1.4);
					\node[font=\scriptsize, anchor=north] at (0,-2.4)
						{(b) seeds on the same side: top/bottom split};
				\end{scope}
			\end{tikzpicture}
		\caption{Four data points and two seeds (rings) for
			Lloyd's algorithm with $\nrcluster = 2$; the crosses are the
			cluster centroids at the fixed point reached, and a
			data point is drawn as a filled circle or a filled square
			by the cluster it ends up in. (a) Seeds on opposite
			sides, drawn by $k$-means++ with probability $51/52$,
			lead to the left/right split with clustering error $1$.
			(b) Seeds on the same side, drawn by uniform seeding with
			probability $1/3$, lead to the cluster centroids
			$(0, \pm 1)^{\top}$, a fixed point of Lloyd's algorithm
			whose top/bottom split has clustering error $25$
			\label{fig_kmeanspp_toy_dict}}
		\end{figure}
		The seeds alone come with a guarantee. Let $E^{\star}$ denote the
		smallest clustering error that any $\nrcluster$
		cluster centroids achieve on the dataset. The seeds
		$\clustercentroid{1}, \ldots, \clustercentroid{\nrcluster}$ of
		Algorithm~\ref{alg_kmeanspp_dict} are random variables (RVs), and their
		expected clustering error satisfies, for every dataset
		and before a single iteration of Lloyd's algorithm
		(Arthur and Vassilvitskii, 2007, Thm.~1.1),
		\begin{equation}
			\label{equ_kmeanspp_bound_dict}
			\expect \Bigg\{ \frac{1}{\samplesize}
			\sum_{\sampleidx=1}^{\samplesize}
			\min_{\clusteridx = 1, \ldots, \nrcluster}
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx}}{2}^{2} \Bigg\}
			\leq 8 \, (\ln \nrcluster + 2) \, E^{\star} \text{.}
		\end{equation}
		Since
		Lloyd's algorithm never increases the clustering error,
		its output started from the seeds satisfies the bound
		\eqref{equ_kmeanspp_bound_dict} as well. The logarithm cannot be
		removed: there are datasets on which the expected
		clustering error of the seeds is at least a constant
		multiple of $\ln \nrcluster$ times $E^{\star}$
		(Arthur and Vassilvitskii, 2007, Sect.~4). Uniform seeding has no bound of
		this kind: on the four data points of
		Fig.~\ref{fig_kmeanspp_toy_dict}, the expected
		clustering error of two uniform seeds is $18$, against
		$2.92$ for $k$-means++ and the bound $8 \, (\ln 2 + 2) \cdot 1 =
		21.55$ of the guarantee \eqref{equ_kmeanspp_bound_dict}. Moving
		the two pairs apart, to $(\pm 50, \pm 1)^{\top}$, keeps $E^{\star}
		= 1$ but raises the uniform value to $1668$, while the
		$k$-means++ value is $3.00$. On the patches, the mean
		clustering error of
		$1000$ seed sets is $0.038$ for $k$-means++ and $0.086$ for
		uniform seeding, $2.1$ and $4.8$ times the best value found;
		the worst $k$-means++ seed set has clustering error
		$0.149$, the worst uniform seed set $0.551$.
\par
		The seeding changes nothing about Lloyd's algorithm itself.
		With the cluster centroids collected in one vector
		$\weights = (\clustercentroid{1}, \ldots,
		\clustercentroid{\nrcluster})$, Lloyd's algorithm is the
		fixed-point iteration $\weights^{(\iteridx+1)} =
		\fixedpointop(\weights^{(\iteridx)})$ for $\iteridx = 0, 1,
		\ldots$. The operator $\fixedpointop$ 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 $\weights^{(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 $\nrcluster$
		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.~\ref{fig_kmeanspp_dict}(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.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.9cm},
			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={greenness of the patch\\(a) $20$ of the $972$ patches and the first seed},
				ylabel={blueness of the patch},
				xmin=0, xmax=0.8, ymin=0, ymax=1.05]
			\addplot[scatter, only marks, mark=*, point meta=\thisrow{ms},
				visualization depends on={\thisrow{ms} \as \perpointmarksize},
				scatter/@pre marker code/.append style={/tikz/mark size=\perpointmarksize},
				scatter/use mapped color={draw=black, fill=gray!60}]
				table[col sep=comma, x=green, y=blue]{kmeanspp_patches_plot.csv};
			\addplot[only marks, mark=square*, mark size=2.6pt, black]
				table[col sep=comma, x=green, y=blue]{kmeanspp_first_seed.csv};
			\nextgroupplot[
				xlabel={fraction of the $1000$ runs\\(b) clustering error after Lloyd's algorithm, sorted},
				ylabel={clustering error},
				xmin=0, xmax=1, ymin=0.012, ymax=0.027,
				scaled y ticks=false,
				yticklabel style={/pgf/number format/fixed, /pgf/number format/precision=3},
				legend style={at={(0.03,0.03)}, anchor=south west}]
			\addplot[black, thick]
				table[col sep=comma, x=frac, y=final_pp]{kmeanspp_runs.csv};
			\addlegendentry{$k$-means++ seeds (solid curve)}
			\addplot[black, thick, dashed]
				table[col sep=comma, x=frac, y=final_uniform]{kmeanspp_runs.csv};
			\addlegendentry{uniform seeds (dashed curve)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Every $49$th of the $972$ patches, $20$ patches,
			drawn as circles whose area is proportional to the
			probability \eqref{equ_kmeanspp_seeding_dict} of being
			the second seed when the first seed is the vegetation patch
			marked by the filled square; the three largest circles are sky
			patches. (b) The clustering error after
			Lloyd's algorithm in $1000$ runs from $k$-means++ seeds
			(solid curve) and $1000$ runs from uniform seeds (dashed
			curve), each sorted in increasing order against the fraction
			of the runs; the step from $0.018$ to $0.025$ sits at $64\%$
			of the $k$-means++ runs and at $48\%$ of the uniform runs.
			Data generated by \texttt{pythondemos/kmeanspp.py}
			\label{fig_kmeanspp_dict}}
		\end{figure}
		Painting each patch of the photograph in the average color of
		its cluster is image segmentation, and the two
		fixed points give two different segmentations. The better
		one separates sky, mountain, and vegetation; the worse one paints
		the $204$ sky patches and $91$ mountain patches in one color and
		cuts the vegetation in two. $k$-means++ is the default
		initialization of $k$-means in scikit-learn
		(Pedregosa et al., 2011).

\subsection{Cross References}
$k$-means, Lloyd's algorithm, cluster centroid, clustering error, clustering, cluster, hard clustering, fixed point, fixed-point iteration, Euclidean distance, minimum, convex, ERM, image segmentation

\subsection{References}
\begin{enumerate}
  \item Arthur and Vassilvitskii (2007). k-means++: the advantages of careful seeding. In: Proc. of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp.~1027--1035. Society for Industrial and Applied Mathematics Philadelphia.
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Pedregosa et al. (2011). Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12(85), pp.~2825--2830.
  \item Ostrovsky et al. (2006). The effectiveness of Lloyd-type methods for the k-means problem. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.~165--176.
  \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}
