\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{\clusteridx}{c}
\newcommand{\covmtx}[1]{\mathbf{C}^{(#1)}}
\newcommand{\defeq}{:=}
\newcommand{\dob}[2]{u_{#1}^{(#2)}}
\newcommand{\featuredim}{d}
\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{\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{\vx}[0]{{\bf x}}

\begin{document}

\section{degree of belonging}

\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}
membership degree, responsibility

\subsection{Abstract}
A degree of belonging is a number that indicates the extent
		to which a data point belongs to a cluster, one for
		each pair of a data point and a cluster of a
		clustering. In the most common formulation, the degrees of
		belonging of one data point are nonnegative and sum to one,
		so they form a vector of the probability simplex and
		a probability mass function (pmf) over the cluster indices. Hard clustering
		is the special case in which this vector has one entry
		equal to one and all others equal to zero, as delivered by
		$k$-means. A principled construction of degrees of belonging
		strictly between zero and one is the posterior distribution of the
		cluster index under a Gaussian mixture model (GMM), which the expectation–maximization (EM)
		algorithm computes in its E-step. The degrees of belonging
		in turn determine the clusters: the mean of a
		cluster is the average of the feature vectors weighted
		by them, and with degrees of belonging of zero or one this
		weighted average is the averaging step of Lloyd's algorithm.
		As the common variance of the clusters of a
		GMM shrinks to zero, the degrees of belonging turn into
		zero or one and soft clustering turns into
		hard clustering.

\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 cold
		cluster and a warm cluster. A day in January is a cold
		day and a day in July a warm day, but 28 May 2024, with a morning
		minimum of $11.1$ and a maximum of $21.3$ degrees, lies between
		the two. A degree of belonging $\dob{\clusteridx}{\sampleidx}$
		is a number that indicates the extent to which data point
		$\sampleidx$ belongs to cluster $\clusteridx$, for
		$\clusteridx = 1, \ldots, \nrcluster$ and $\sampleidx = 1,
		\ldots, \samplesize$. For 28 May 2024, the Gaussian mixture model (GMM) of
		Fig.~\ref{fig_dob_krems_dict} delivers the degrees of belonging
		$0.50$ to the cold and $0.50$ to the warm cluster, while a
		day in January obtains $1.00$ and $0.00$. In the most common
		formulation, the degrees of belonging of one data point are
		nonnegative and sum to one (Bezdek, 1981;
		Ruspini, 1969),
		\begin{equation}
			\label{equ_dob_simplex_dict}
			\dob{\clusteridx}{\sampleidx} \geq 0
			\quad \text{for } \clusteridx = 1, \ldots, \nrcluster
			\qquad \text{and} \qquad
			\sum_{\clusteridx=1}^{\nrcluster} \dob{\clusteridx}{\sampleidx}
			= 1 \text{.}
		\end{equation}
		The vector
		$\vu^{(\sampleidx)} \defeq \big(\dob{1}{\sampleidx}, \ldots,
		\dob{\nrcluster}{\sampleidx}\big)^{\top}$ then lies in the
		probability simplex $\simplex{\nrcluster-1}$. It is the
		probability mass function (pmf) of a random variable (RV) with values in $\{1, \ldots, \nrcluster\}$,
		the cluster index of the data point. Possibilistic
		clustering drops the sum constraint of the simplex
		condition \eqref{equ_dob_simplex_dict} and lets each degree of
		belonging vary in $[0, 1]$ on its own (Krishnapuram and Keller, 1993).
		Fig.~\ref{fig_dob_schematic_dict} sketches three
		data points and their degrees of belonging to two
		overlapping clusters.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}[>=Stealth, scale=1.0]
			\draw[thick] (-1.6, 0) ellipse (2.2 and 1.2);
			\node[font=\small] at (-1.6, -1.55) {cluster $1$ (solid)};
			\draw[thick, dashed] (1.6, 0) ellipse (2.2 and 1.2);
			\node[font=\small] at (1.6, -1.55) {cluster $2$ (dashed)};
			\fill[black] (-2.4, 0.3) circle (2.5pt);
			\node[above=3pt, font=\small] at (-2.4, 0.3)
				{$\featurevec^{(1)}$};
			\fill[black] (0.0, 0.0) circle (2.5pt);
			\node[above=3pt, font=\small] at (0.0, 0.0)
				{$\featurevec^{(2)}$};
			\fill[black] (2.4, -0.2) circle (2.5pt);
			\node[above=3pt, font=\small] at (2.4, -0.2)
				{$\featurevec^{(3)}$};
			\node[font=\scriptsize, align=center] at (-2.4, -2.2)
				{$\dob{1}{1}\!=\!0.95$\\[1pt]$\dob{2}{1}\!=\!0.05$};
			\node[font=\scriptsize, align=center] at (0.0, -2.2)
				{$\dob{1}{2}\!=\!0.5$\\[1pt]$\dob{2}{2}\!=\!0.5$};
			\node[font=\scriptsize, align=center] at (2.4, -2.2)
				{$\dob{1}{3}\!=\!0.1$\\[1pt]$\dob{2}{3}\!=\!0.9$};
		\end{tikzpicture}
		\caption{Three data points with different degrees of
			belonging to two overlapping clusters, cluster $1$
			(solid ellipse) and cluster $2$ (dashed ellipse). The
			feature vector $\featurevec^{(1)}$ lies deep inside
			cluster $1$ and $\featurevec^{(3)}$ deep inside
			cluster $2$, while
			$\featurevec^{(2)}$ lies in the overlap with equal degrees
			of belonging. In every case
			$\dob{1}{\sampleidx} + \dob{2}{\sampleidx} = 1$, the simplex
			condition \eqref{equ_dob_simplex_dict}
			\label{fig_dob_schematic_dict}}
		\end{figure}
		Hard clustering is the special case in which every
		data point belongs to exactly one cluster. With
		$\widehat{\clusteridx}^{(\sampleidx)}$ the index of the
		cluster that data point $\sampleidx$ is assigned to,
		its degrees of belonging are
		\begin{equation}
			\label{equ_dob_hard_dict}
			\dob{\clusteridx}{\sampleidx} =
			\begin{cases}
				1 & \text{for } \clusteridx = \widehat{\clusteridx}^{(\sampleidx)}
				\text{,} \\
				0 & \text{otherwise} \text{,}
			\end{cases}
		\end{equation}
		so the vector $\vu^{(\sampleidx)}$ is a vertex of the
		probability simplex $\simplex{\nrcluster-1}$
		(Bishop, 2006, Sect.~9.1). $k$-means delivers such a
		hard clustering: $\widehat{\clusteridx}^{(\sampleidx)}$ is
		the index of the cluster centroid nearest to
		$\featurevec^{(\sampleidx)}$ in Euclidean distance. For the days at
		Krems and two cluster centroids, $k$-means assigns $192$
		days to the cold cluster with cluster centroid
		$(1.5, 10.5)$ and $174$ days to the warm cluster with
		cluster centroid $(13.4, 26.1)$. The dashed curve in
		Fig.~\ref{fig_dob_krems_dict}(b) shows these hard assignments
		over the year: they jump between $0$ and $1$ from one spring day
		to the next.
\par
		Soft clustering methods assign a data point to several
		clusters with degrees of belonging strictly between $0$
		and $1$. A principled construction uses a probabilistic model for the
		data points, the GMM. Under it, the cluster
		index $I^{(\sampleidx)} \in \{1, \ldots, \nrcluster\}$ of
		data point $\sampleidx$ is an unobserved RV with
		$\prob{I^{(\sampleidx)} = \clusteridx} = p_{\clusteridx}$.
		Given $I^{(\sampleidx)} = \clusteridx$, the feature vector
		$\featurevec^{(\sampleidx)}$ is drawn from a multivariate normal distribution with
		mean $\meanvec{\clusteridx}$ and covariance matrix
		$\covmtx{\clusteridx}$. The degree of belonging is then the
		posterior distribution of the cluster index given the
		observed feature vector,
		\begin{equation}
			\label{equ_dob_gmm_dict}
			\dob{\clusteridx}{\sampleidx} \defeq
			\prob{I^{(\sampleidx)} = \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}
		the responsibility of cluster $\clusteridx$ for the
		data point (Bishop, 2006, Sect.~9.2;
		Murphy, 2012, Sect.~11.2.3). The posterior degrees of
		belonging \eqref{equ_dob_gmm_dict} are the probabilities of
		the $\nrcluster$ values of one RV, so they satisfy the
		simplex condition \eqref{equ_dob_simplex_dict} by construction.
		The model parameters $p_{\clusteridx}$, $\meanvec{\clusteridx}$,
		and $\covmtx{\clusteridx}$ of the GMM are learned by
		maximum likelihood. This is an instance of empirical risk minimization (ERM): the
		loss of a data point is the negative logarithm of the
		probability density function (pdf) of the GMM at its feature vector, and the
		clustering error is the average of this loss over the
		dataset. For the days at Krems, a two-component
		GMM learned by the expectation–maximization (EM) algorithm has the
		means $(3.1, 12.3)$ and $(14.2, 27.5)$ and the
		cluster probabilities $0.63$ and $0.37$. Under it,
		$58$ of the $366$ days have no degree of belonging above $0.8$,
		$23$ of them in May and none between November and February
		(Fig.~\ref{fig_dob_krems_dict}).
\par
		The degrees of belonging determine the clusters in turn.
		In the M-step of the EM algorithm, the mean of
		cluster $\clusteridx$ is the average of the
		feature vectors weighted by the degrees of belonging. The
		cluster probability is the average of the degrees of
		belonging themselves. In formulas,
		\begin{equation}
			\label{equ_dob_centroid_dict}
			\meanvec{\clusteridx} =
			\frac{\sum_{\sampleidx=1}^{\samplesize}
			\dob{\clusteridx}{\sampleidx}\, \featurevec^{(\sampleidx)}}
			{\sum_{\sampleidx=1}^{\samplesize} \dob{\clusteridx}{\sampleidx}}
			\qquad \text{and} \qquad
			p_{\clusteridx} = \frac{1}{\samplesize}
			\sum_{\sampleidx=1}^{\samplesize} \dob{\clusteridx}{\sampleidx}
			\quad \text{for } \clusteridx = 1, \ldots, \nrcluster\text{.}
		\end{equation}
		The covariance matrix $\covmtx{\clusteridx}$ is the covariance matrix of
		the feature vectors under the same weighting
		(Bishop, 2006, Sect.~9.2.2). A day with the degrees of
		belonging $0.50$ and $0.50$ counts half towards each mean.
		With the degrees of belonging \eqref{equ_dob_hard_dict} of a
		hard clustering, the weighted average
		\eqref{equ_dob_centroid_dict} is the mean of the
		data points assigned to cluster $\clusteridx$, which
		is the averaging step of Lloyd's algorithm for $k$-means,
		and $p_{\clusteridx}$ is the share of data points in that
		cluster. The EM algorithm alternates the
		posterior \eqref{equ_dob_gmm_dict} with the weighted averages
		\eqref{equ_dob_centroid_dict}, so the degrees of belonging are
		recomputed in every iteration: they are not
		model parameters but a function of the model parameters
		and of the feature vector. At the fixed point of the
		EM algorithm on the days at Krems, each mean
		equals the average of the days weighted by their degrees of
		belonging and differs from the $k$-means
		cluster centroid of the same cluster by at most
		$1.9$ degrees.
\par
		Hard clustering is also a limit of the posterior degrees of
		belonging \eqref{equ_dob_gmm_dict}. Fix every cluster
		probability at $1/\nrcluster$ and every covariance matrix at
		$\sigma^{2} \mI$, a multiple of the identity matrix $\mI$
		with one common variance $\sigma^{2}$. The posterior
		\eqref{equ_dob_gmm_dict} then depends on
		$\featurevec^{(\sampleidx)}$ only through its squared
		Euclidean distances to the means. As $\sigma^{2}$ shrinks
		towards $0$, it concentrates on the nearest mean: every
		degree of belonging tends to $0$ or $1$, and the EM
		algorithm reduces to Lloyd's algorithm
		(Bishop, 2006, Sect.~9.3.2;
		Hastie et al., 2009, Sect.~14.3.7). For the
		days at Krems, with the two $k$-means cluster centroids
		as means and $\sigma^{2} = 1$, no day has both degrees of
		belonging above $0.2$, and every degree of belonging is within
		$0.01$ of its $k$-means value \eqref{equ_dob_hard_dict}. With
		$\sigma^{2} = 50$, $16$ percent of the days have both degrees
		above $0.2$. With $\sigma^{2} = 1000$, every day has both above
		$0.2$ and no degree of belonging exceeds $0.63$.
\par
		The degrees of belonging of a data point are the value of a
		hypothesis at its feature vector. The posterior
		\eqref{equ_dob_gmm_dict} is a map
		$\hypothesis: \reals^{\featuredim} \rightarrow \simplex{\nrcluster-1}$
		determined by the model parameters of the GMM, and the
		assignment rule of $k$-means is a map from
		$\reals^{\featuredim}$ to the vertices of
		$\simplex{\nrcluster-1}$ determined by the
		cluster centroids. Either map applies to a day that did not
		belong to the dataset the clusters were learned
		from, which is how a clustering generalizes. A
		hard clustering is derived from degrees of belonging by
		assigning each data point to the cluster with the
		largest one, and $1 - \max_{\clusteridx = 1, \ldots, \nrcluster}
		\dob{\clusteridx}{\sampleidx}$ measures how uncertain that
		assignment is (Murphy, 2012, Sect.~11.2.3). For the days at
		Krems, the largest posterior degree of belonging names the
		$k$-means cluster on $91.5$ percent of the days. In
		medical image segmentation, the degrees of belonging of a
		pixel to the tissue types let a pixel at the boundary between
		two tissues belong partly to both, where a hard clustering
		must pick one (Pham et al., 2000).
		\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},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) $21$ of the $366$ days and the two means},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=52,
				legend style={at={(0.03,0.97)}, anchor=north west}]
			\addplot[black, thick, forget plot]
				table[col sep=comma, x=x1, y=x2]{dob_ellipse1.csv};
			\addplot[black, thick, dashed, forget plot]
				table[col sep=comma, x=x1, y=x2]{dob_ellipse2.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{class}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{dob_points_plot.csv};
			\addlegendentry{cold days (circles)}
			\addplot[only marks, mark=square, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{class}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{dob_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addplot[only marks, mark=triangle, mark size=2pt, black,
				restrict expr to domain={\thisrow{class}}{2:2}]
				table[col sep=comma, x=tmin, y=tmax]{dob_points_plot.csv};
			\addlegendentry{in-between days (triangles)}
			\addplot[only marks, mark=x, mark size=3pt, thick, black,
				restrict expr to domain={\thisrow{kindid}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{dob_means.csv};
			\addlegendentry{means (crosses)}
			\nextgroupplot[
				xlabel={day of the year 2024\\(b) degree of belonging to the warm cluster},
				ylabel={degree of belonging},
				xmin=0, xmax=366, ymin=-0.05, ymax=1.05,
				legend style={at={(0.5,-0.42)}, anchor=north,
					legend columns=2, column sep=6pt}]
			\addplot[black, thick]
				table[col sep=comma, x=day, y=uwarm]{dob_year.csv};
			\addlegendentry{GMM (solid curve)}
			\addplot[black, dashed, const plot]
				table[col sep=comma, x=day, y=hard]{dob_year.csv};
			\addlegendentry{$k$-means (dashed curve)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Every $18$th of the $366$ days of $2024$ at Krems,
			$21$ days, drawn by their posterior degrees of belonging
			\eqref{equ_dob_gmm_dict} under the two-component GMM:
			cold days (circles) and warm days (squares) have a degree of
			belonging above $0.8$ to one cluster, in-between days
			(triangles) have both below $0.8$. The crosses are the two
			means, and the ellipses are the level sets of the two
			multivariate normal distributions at one standard deviation: the cold one
			(solid ellipse) and the warm one (dashed ellipse). (b) The
			degree of
			belonging to the warm cluster of every day of the
			year: the posterior under the GMM (solid curve) and the
			$0$ or $1$ of $k$-means (dashed curve). Data generated by
			\texttt{pythondemos/dob.py}
			\label{fig_dob_krems_dict}}
		\end{figure}

\subsection{Cross References}
cluster, clustering, soft clustering, hard clustering, cluster centroid, GMM, EM, $k$-means, Lloyd's algorithm, posterior distribution, probability simplex, pmf, clustering error

\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 Krishnapuram and Keller (1993). A possibilistic approach to clustering. IEEE Transactions on Fuzzy Systems, 1(2), pp.~98--110.
  \item Murphy (2012). Machine Learning: A Probabilistic Perspective. MIT Press, Cambridge, MA, USA.
  \item Pham et al. (2000). Current methods in medical image segmentation. Annual Review of Biomedical Engineering, 2, pp.~315--337.
  \item Ruspini (1969). A new approach to clustering. Information and Control, 15(1), pp.~22--32.
  \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}
