\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{\covmtx}[1]{\mathbf{C}^{(#1)}}
\newcommand{\defeq}{:=}
\newcommand{\dob}[2]{u_{#1}^{(#2)}}
\newcommand{\featuredim}{d}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\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{\prob}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\simplex}[1]{\Delta^{#1}}
\newcommand{\vu}[0]{{\bf u}}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{soft clustering}

\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{Synonyms}
fuzzy clustering

\subsection{Abstract}
Soft clustering assigns each data point to every
		cluster with a degree of belonging, a number between zero and one, so
		that the degrees of belonging of one data point form a vector in
		the probability simplex. Hard clustering is the special
		case in which this vector is a vertex of the simplex, with one
		entry equal to one and the others equal to zero. For numeric
		feature vectors, the principled choice of the degrees of belonging is the
		posterior distribution of the cluster index under a Gaussian mixture model (GMM)
		whose model parameters are learned by the expectation–maximization (EM)
		algorithm. With equal cluster probabilities and
		covariance matrices $\sigma^{2} \mI$, the degrees of belonging tend to the
		vertices as $\sigma^{2}$ shrinks, and the EM algorithm
		becomes Lloyd's algorithm for $k$-means. Fuzzy $c$-means
		delivers degrees of belonging without a probabilistic model by minimizing a
		weighted clustering error over the simplex, and it also reduces
		to $k$-means as its fuzzifier tends to one. Assigning each
		data point to the cluster with the largest degree of belonging
		turns a soft clustering into a hard clustering, and one minus
		that largest degree of belonging measures how far the assignment is from
		certain.

\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$ clusters assigns every day to the nearer of
		two cluster centroids, $(1.5, 10.5)$ for $192$ cold days and
		$(13.4, 26.1)$ for $174$ warm days. A day in April whose temperatures
		lie halfway between the two cluster centroids becomes a cold
		day or a warm day all the same, and nothing records that it was a
		borderline case. Soft clustering keeps that information: it assigns
		each data point to every cluster with a degree of belonging
		$\dob{\clusteridx}{\sampleidx}$, a number between $0$ and $1$ for
		data point $\sampleidx = 1, \ldots, \samplesize$ and
		cluster $\clusteridx = 1, \ldots, \nrcluster$
		(Bishop, 2006, Sect.~9.3.2;
		Murphy, 2012, Sect.~11.2.3). The degrees of belonging of one
		data point form the vector
		\begin{equation}
			\label{equ_softclustering_simplex_dict}
			\vu^{(\sampleidx)} \defeq \big(\dob{1}{\sampleidx}, \ldots,
			\dob{\nrcluster}{\sampleidx}\big)^{\top} \in
			\simplex{\nrcluster-1}, \quad \text{i.e., }
			\dob{\clusteridx}{\sampleidx} \geq 0 \text{ and }
			\sum_{\clusteridx=1}^{\nrcluster} \dob{\clusteridx}{\sampleidx}
			= 1 \text{,}
		\end{equation}
		a point of the probability simplex $\simplex{\nrcluster-1}$. A
		hard clustering is the special case in which every vector
		\eqref{equ_softclustering_simplex_dict} is a vertex of the simplex:
		one entry is $1$ and the other $\nrcluster-1$ entries are $0$.
		A soft clustering method learns a hypothesis
		$\hypothesis: \featurespace \rightarrow \simplex{\nrcluster-1}$ that
		maps a feature vector to a degree of belonging vector, so it can be
		evaluated for a day that did not belong to the dataset. A
		hard clustering method learns a map into the $\nrcluster$
		vertices only.
\par
		For data points with numeric feature vectors, the principled
		choice of the degrees of belonging is a probabilistic model, the Gaussian mixture model (GMM). It
		generates a data point by drawing a cluster index $I$ with
		probabilities $p_{1}, \ldots, p_{\nrcluster}$ and then the
		feature vector from the multivariate normal distribution of that cluster, with
		mean $\meanvec{\clusteridx}$ and covariance matrix
		$\covmtx{\clusteridx}$. The degree of belonging of data point
		$\featurevec^{(\sampleidx)}$ to cluster $\clusteridx$ is the
		posterior distribution of its cluster index,
		\begin{equation}
			\label{equ_softclustering_posterior_dict}
			\dob{\clusteridx}{\sampleidx} \defeq
			\prob{I = \clusteridx \mid \featurevec^{(\sampleidx)}} =
			\frac{p_{\clusteridx}\,
			\mvnormal{\meanvec{\clusteridx}}{\covmtx{\clusteridx}}
			(\featurevec^{(\sampleidx)})}
			{\sum_{\clusteridx'=1}^{\nrcluster} p_{\clusteridx'}\,
			\mvnormal{\meanvec{\clusteridx'}}{\covmtx{\clusteridx'}}
			(\featurevec^{(\sampleidx)})}
			\text{,}
		\end{equation}
		which Bishop (2006), Sect.~9.2 calls the responsibility of
		cluster $\clusteridx$ for the data point. The
		model parameters are learned by maximum likelihood with the
		expectation–maximization (EM) algorithm, whose E-step computes the degrees of belonging
		\eqref{equ_softclustering_posterior_dict} and whose M-step
		recomputes the model parameters as averages weighted by them
		(Bishop, 2006, Sect.~9.2.2). Maximum likelihood is empirical risk minimization (ERM)
		with the negative logarithm of the probability density function (pdf) as the loss, so
		the learned model parameters minimize a clustering error, and
		the EM algorithm is a fixed-point iteration that never
		increases it (Dempster et al., 1977, Thm.~1). On the days at
		Krems, the EM algorithm started from the $k$-means
		cluster centroids stops after $273$ iterations with
		cluster probabilities $0.63$ and $0.37$ and
		means $(3.1, 12.4)$ and $(14.2, 27.5)$. For $58$ of the
		$366$ days, no degree of belonging reaches $0.8$; $23$ of them are in May,
		and none is in January, February, November, or December.
\par
		A soft clustering is turned into a hard clustering by assigning
		each data point to the cluster with the largest
		degree of belonging, and $1 - \max_{\clusteridx = 1, \ldots, \nrcluster}
		\dob{\clusteridx}{\sampleidx}$ measures how far that assignment is
		from certain (Murphy, 2012, Sect.~11.2.3). For the days at
		Krems, this assignment agrees with $k$-means on $335$ of the
		$366$ days. Fig.~\ref{fig_softclustering_dict}(a) shows why the two
		disagree: the curve on which the two degrees of belonging
		\eqref{equ_softclustering_posterior_dict} are equal is not the
		decision boundary of $k$-means, the perpendicular bisector
		of the two cluster centroids. It bends around the warm
		cluster, because the warm days scatter less than the cold
		ones and the covariance matrix of the warm cluster is smaller.
\par
		Hard clustering is a limit of the GMM. Fix every
		cluster probability at $1/\nrcluster$ and every
		covariance matrix at $\sigma^{2} \mI$, a multiple of the identity
		matrix with one common $\sigma^{2}$; this shrinks the
		hypothesis space, which is model pruning, one of the three
		routes that regularization distinguishes. The degree of belonging
		\eqref{equ_softclustering_posterior_dict} then depends on the
		feature vector only through its squared Euclidean distances to the
		means,
		\begin{equation}
			\label{equ_softclustering_limit_dict}
			\dob{\clusteridx}{\sampleidx} =
			\frac{\exp\big(- \normgeneric{\featurevec^{(\sampleidx)} -
			\meanvec{\clusteridx}}{2}^{2} / (2\sigma^{2})\big)}
			{\sum_{\clusteridx'=1}^{\nrcluster}
			\exp\big(- \normgeneric{\featurevec^{(\sampleidx)} -
			\meanvec{\clusteridx'}}{2}^{2} / (2\sigma^{2})\big)} \text{,}
		\end{equation}
		the softmax function of the negative squared Euclidean distances divided
		by $2\sigma^{2}$. As $\sigma^{2}$ shrinks towards $0$, the
		degree of belonging \eqref{equ_softclustering_limit_dict} of the nearest
		mean tends to $1$ and all others to $0$, so the vector
		\eqref{equ_softclustering_simplex_dict} tends to the vertex of the
		nearest-cluster centroid assignment, and the EM
		algorithm becomes Lloyd's algorithm for $k$-means
		(Bishop, 2006, Sect.~9.3.2;
		Hastie et al., 2009, Sect.~14.3.7). With the
		means at the $k$-means cluster centroids of the
		days at Krems, $26$ days have a degree of belonging between $0.2$ and $0.8$
		for $\sigma^{2} = 25$, three days for $\sigma^{2} = 4$, and none for
		$\sigma^{2} = 1$, while for every $\sigma^{2}$ the largest
		degree of belonging names the nearest cluster centroid.
		Fig.~\ref{fig_softclustering_dict}(b) draws the degree of belonging to the
		cold cluster along the line through the two
		cluster centroids, parametrized by $s$ with $s = 0$ at the
		cold and $s = 1$ at the warm cluster centroid. Along this
		line, $k$-means jumps from $1$ to $0$ at $s = 1/2$, the
		GMM crosses $1/2$ later and gradually, and the constrained
		GMM with $\sigma^{2} = 4$ is close to the jump.
\par
		Fuzzy $c$-means delivers degrees of belonging without a probabilistic model
		(Bezdek, 1981). It minimizes a weighted clustering error,
		\begin{equation}
			\label{equ_softclustering_fcm_dict}
			\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize}
			\sum_{\clusteridx=1}^{\nrcluster}
			\big(\dob{\clusteridx}{\sampleidx}\big)^{\varphi}
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx}}{2}^{2} \text{,}
		\end{equation}
		jointly over the cluster centroids $\clustercentroid{1},
		\ldots, \clustercentroid{\nrcluster} \in \reals^{\featuredim}$ and
		the degrees of belonging, each vector
		\eqref{equ_softclustering_simplex_dict} constrained to the
		probability simplex, with a fuzzifier $\varphi > 1$. For fixed
		cluster centroids, the minimizing degrees of belonging are
		proportional to $\normgeneric{\featurevec^{(\sampleidx)} -
		\clustercentroid{\clusteridx}}{2}^{-2/(\varphi - 1)}$, normalized to
		sum to one; for fixed degrees of belonging, the minimizing
		cluster centroid $\clustercentroid{\clusteridx}$ is the average
		of the feature vectors weighted by
		$(\dob{\clusteridx}{\sampleidx})^{\varphi}$. Alternating the two
		updates is a fixed-point iteration: each update minimizes the
		objective \eqref{equ_softclustering_fcm_dict} exactly in one block
		of variables with the other fixed, so no iteration increases
		the objective, and a fixed point is a pair of
		cluster centroids and degrees of belonging at which neither update
		changes anything. As $\varphi$ tends to $1$, the degrees of belonging tend to
		the vertices of the simplex and the objective
		\eqref{equ_softclustering_fcm_dict} to the clustering error of
		$k$-means. With $\varphi = 1.05$ on the days at Krems, the
		cluster centroids lie within $0.05$ of those of $k$-means
		and the objective is $42.0$, the clustering error of
		$k$-means. For $358$ of the $366$ days, the largest degree of belonging
		exceeds $0.99$. With $\varphi = 2$, $66$ days have no degree of belonging of
		$0.8$ or more, and with $\varphi = 10$ every degree of belonging lies between
		$0.26$ and $0.74$.
\par
		The degrees of belonging of fuzzy $c$-means decay like the reciprocal of a
		squared Euclidean distance, so far away from every
		cluster centroid they approach $1/\nrcluster$. At the ends of
		the line in Fig.~\ref{fig_softclustering_dict}(b), the degree of belonging to
		the cold cluster is $0.91$ at $s = -1/2$ and $0.09$ at
		$s = 3/2$, where the GMM gives $1$ and $0$ to within $0.02$.
\par
		In image segmentation by clustering the patches of a
		photograph by their colors, a patch on the horizon between a
		mountain and the sky is partly both, and its degree of belonging vector
		records both shares while a hard clustering must choose one.
		A soft clustering of the days at Krems records the transitional
		days of spring and autumn, which a hard clustering into a cold
		and a warm regime hides.
		\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.46\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.5,-0.32)}, anchor=north, legend columns=1},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) $21$ of the $366$ days and two boundaries},
				ylabel={maximum daytime temperature},
				xmin=-8, xmax=23, ymin=0, ymax=40]
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{cluster}+2*\thisrow{confident}}{2:2}]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_points_plot.csv};
			\addlegendentry{cold days (circles)}
			\addplot[only marks, mark=square*, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{cluster}+2*\thisrow{confident}}{3:3}]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addplot[only marks, mark=o, mark size=1.6pt, black, forget plot,
				restrict expr to domain={\thisrow{cluster}+2*\thisrow{confident}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_points_plot.csv};
			\addplot[only marks, mark=square, mark size=1.5pt, black, forget plot,
				restrict expr to domain={\thisrow{cluster}+2*\thisrow{confident}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_points_plot.csv};
			\addplot[black, thick]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_contour.csv};
			\addlegendentry{equal degrees of belonging (solid curve)}
			\addplot[black, dashed]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_bisector.csv};
			\addlegendentry{$k$-means decision boundary (dashed line)}
			\addplot[gray, dotted, thin, forget plot]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_centroids.csv};
			\addplot[only marks, mark=x, mark size=3pt, thick, black]
				table[col sep=comma, x=tmin, y=tmax]{softclustering_centroids.csv};
			\addlegendentry{cluster centroids (crosses)}
			\nextgroupplot[
				xlabel={position $s$ on the line through the cluster centroids\\(b) soft and hard assignments along the line},
				ylabel={degree of belonging to the cold cluster},
				xmin=-0.5, xmax=1.5, ymin=-0.02, ymax=1.05]
			\addplot[black, dashed]
				table[col sep=comma, x=s, y=kmeans]{softclustering_segment.csv};
			\addlegendentry{$k$-means (dashed curve)}
			\addplot[black, thick]
				table[col sep=comma, x=s, y=gmm]{softclustering_segment.csv};
			\addlegendentry{GMM (solid curve)}
			\addplot[black, dashdotted]
				table[col sep=comma, x=s, y=sigma4]{softclustering_segment.csv};
			\addlegendentry{constrained GMM (dash-dotted curve)}
			\addplot[black, densely dotted, thick]
				table[col sep=comma, x=s, y=fcm]{softclustering_segment.csv};
			\addlegendentry{fuzzy $c$-means (dotted curve)}
		\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 larger of their two degrees of belonging
			\eqref{equ_softclustering_posterior_dict} under the GMM;
			the four open markers are days whose larger degree of belonging is below
			$0.8$. The solid curve is the set of feature vectors with
			equal degrees of belonging to both clusters, the dashed line the
			decision boundary of $k$-means, the crosses its two
			cluster centroids, and the thin dotted segment between
			them the line of panel (b). (b) The degree of belonging to the cold
			cluster along the line through the two
			cluster centroids: $k$-means (dashed curve) jumps at
			$s = 1/2$, the GMM (solid curve) and fuzzy $c$-means with
			$\varphi = 2$ (dotted curve) change gradually, and the
			constrained GMM \eqref{equ_softclustering_limit_dict} with
			$\sigma^{2} = 4$ (dash-dotted curve) is close to the jump. Data
			generated by \texttt{pythondemos/softclustering.py}
			\label{fig_softclustering_dict}}
		\end{figure}

\subsection{Cross References}
clustering, cluster, degree of belonging, hard clustering, probability simplex, GMM, posterior distribution, EM, maximum likelihood, clustering error, $k$-means, Lloyd's algorithm, cluster centroid, softmax function, fixed-point iteration, decision boundary, image segmentation, spectral clustering

\subsection{References}
\begin{enumerate}
  \item Bezdek (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York, NY, USA.
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Murphy (2012). Machine Learning: A Probabilistic Perspective. MIT Press, Cambridge, MA, USA.
  \item Dempster et al. (1977). Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc.: Ser. B (Methodological), 39(1), pp.~1--22.
  \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}
