\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{\cluster}{\mathcal{C}}
\newcommand{\clustercentroid}[1]{{\vw}^{(#1)}}
\newcommand{\clusteridx}{c}
\newcommand{\covmtx}[1]{\mathbf{C}^{(#1)}}
\newcommand{\datacluster}[1]{\mathcal{C}^{(#1)}}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\dob}[2]{u_{#1}^{(#2)}}
\newcommand{\edgeweight}{A}
\newcommand{\featuredim}{d}
\newcommand{\featurevec}{\vx}
\newcommand{\meanvec}[1]{{\bm \mu}^{(#1)}}
\newcommand{\mvnormal}[2]{\mathcal{N}\left(#1,#2\right)}
\newcommand{\nodes}{\mathcal{V}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrcluster}{k}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\simplex}[1]{\Delta^{#1}}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{cluster}

\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 is a subset of the data points of a
		dataset that are more similar to each other than to the
		data points outside the subset. The measure of
		similarity is a design choice, such as the Euclidean distance
		between feature vectors or the edge weights of a
		similarity graph. In a hard clustering every data point
		belongs to exactly one cluster; in a soft clustering it
		belongs to every cluster with a degree of belonging, and the degrees of belonging of
		one data point sum to one. A clustering method
		represents a cluster by an object that determines the membership
		of any data point. Three representations are in use: a
		cluster centroid, as in $k$-means; a probability distribution, as
		the multivariate normal distribution of one component of a Gaussian mixture model (GMM); or a densely
		connected subset of the nodes of a similarity graph, as in
		graph clustering. The
		number and the shape of the clusters depend on the method and
		its hyperparameters: $k$-means delivers convex
		clusters, a GMM ellipsoids, and density-based spatial clustering of applications with noise (DBSCAN) any shape that
		a chain of nearby data points can trace.

\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 day in January, with a
		morning minimum near $0$ and a maximum near $5$ degrees, resembles
		the other days of January more than any day of July, whose
		temperatures lie some $20$ degrees higher. A cluster is a subset
		of the data points of a dataset that are more similar
		to each other than to the data points outside the subset
		(Bishop, 2006, Sect.~9.1;
		Hastie et al., 2009, Sect.~14.3).
		Fig.~\ref{fig_cluster_dict}(a) shows the two clusters that
		$k$-means finds among the days of $2024$: $192$ cold days and
		$174$ warm days. Every day of January and February is a cold day,
		and every day of July and August is a warm day. Measured by the
		Euclidean distance between their feature vectors, two days of
		the same cluster are $8.0$ degrees apart on average, a cold and
		a warm day $20.2$ degrees, and for $364$ of the $366$ days the
		most similar other day belongs to the same cluster.
\par
		The measure of similarity between data points is a
		design choice (Hastie et al., 2009, Sect.~14.3).
		For data points with numeric feature vectors
		$\featurevec \in \reals^{\featuredim}$, two data points are
		similar if the Euclidean distance between their feature vectors
		is small. Data points without numeric feature vectors,
		such as the members of a social network or the papers of a
		citation network, are the nodes of a similarity graph whose
		edge weights measure their similarity directly.
\par
		Formally, consider a dataset $\dataset =
		\{\featurevec^{(1)}, \ldots, \featurevec^{(\samplesize)}\}$. A
		cluster is a subset $\datacluster{\clusteridx} \subseteq \{1,
		\ldots, \samplesize\}$ of the indices of the data points. A
		hard clustering into $\nrcluster$ clusters is a partition of
		the indices,
		\begin{equation}
			\label{equ_cluster_partition_dict}
			\datacluster{1} \cup \cdots \cup \datacluster{\nrcluster}
			= \{1, \ldots, \samplesize\} \quad \text{and} \quad
			\datacluster{\clusteridx} \cap \datacluster{\clusteridx'}
			= \emptyset \text{ for } \clusteridx \neq \clusteridx'
			\text{,}
		\end{equation}
		so every data point belongs to exactly one cluster, and the
		hard clustering is recorded by the index of that cluster in
		$\{1, \ldots, \nrcluster\}$ (Jain et al., 1999, Sect.~2).
		The two clusters of Fig.~\ref{fig_cluster_dict}(a) form a
		partition \eqref{equ_cluster_partition_dict} of the $366$ days.
		A soft clustering replaces the index by a degree of belonging
		$\dob{\clusteridx}{\sampleidx}$ of data point $\sampleidx$
		to every cluster $\clusteridx = 1, \ldots, \nrcluster$,
		\begin{equation}
			\label{equ_cluster_dob_dict}
			\dob{\clusteridx}{\sampleidx} \geq 0 \quad \text{and} \quad
			\sum_{\clusteridx=1}^{\nrcluster} \dob{\clusteridx}{\sampleidx}
			= 1 \quad \text{for } \sampleidx = 1, \ldots, \samplesize
			\text{,}
		\end{equation}
		so the degrees of belonging of one data point form a vector in
		the probability simplex $\simplex{\nrcluster-1}$. A cluster
		is then no longer a subset but the map $\sampleidx \mapsto
		\dob{\clusteridx}{\sampleidx}$ that grades the membership of
		every data point. A hard clustering is the special case
		where every degree of belonging is $0$ or $1$: the cluster
		$\datacluster{\clusteridx}$ then consists of the data points
		with $\dob{\clusteridx}{\sampleidx} = 1$, and these clusters form
		a partition \eqref{equ_cluster_partition_dict}.
\par
		A clustering method does not store a cluster as a list of
		indices. It represents the cluster by an object from which the
		membership of any data point follows, including a
		data point that does not belong to the dataset. This
		object is the hypothesis that the method learns, and
		generalization to new data points is what it is for.
		Three representations are in use (Fig.~\ref{fig_cluster_dict}).
\par
		First, a cluster centroid $\clustercentroid{\clusteridx} \in
		\reals^{\featuredim}$ is a single point of the feature space
		(Bishop, 2006, Sect.~9.1). It represents a cluster as the set
		of data points that are nearer to it than to any other
		cluster centroid,
		\begin{equation}
			\label{equ_cluster_centroid_dict}
			\datacluster{\clusteridx} = \big\{ \sampleidx :
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx}}{2} \leq
			\normgeneric{\featurevec^{(\sampleidx)} -
			\clustercentroid{\clusteridx'}}{2}
			\text{ for all } \clusteridx' \neq \clusteridx \big\}
			\text{.}
		\end{equation}
		This is the hard clustering delivered by $k$-means, whose
		cluster centroids minimize the clustering error, an
		instance of empirical risk minimization (ERM). The region of the feature space that
		satisfies the inequalities in the cluster
		\eqref{equ_cluster_centroid_dict} is an intersection of
		halfspaces, one for each other cluster centroid, and
		therefore convex. For the days at Krems and
		$\nrcluster = 2$, the two cluster centroids are
		$(1.5, 10.5)$ and $(13.4, 26.1)$, and the boundary between the
		two clusters is the straight line through their midpoint at a
		right angle to their connecting segment
		(Fig.~\ref{fig_cluster_dict}(a)).
\par
		Second, a probability distribution represents a cluster. A Gaussian mixture model (GMM)
		represents cluster $\clusteridx$ by a multivariate normal distribution with
		mean $\meanvec{\clusteridx}$ and covariance matrix
		$\covmtx{\clusteridx}$, drawn with probability
		$p_{\clusteridx}$. The degree of belonging of a data point to cluster
		$\clusteridx$ is the posterior distribution of its cluster index
		given its feature vector, evaluated at $\clusteridx$
		(Bishop, 2006, Sect.~9.2),
		\begin{equation}
			\label{equ_cluster_posterior_dict}
			\dob{\clusteridx}{\sampleidx} = \frac{p_{\clusteridx}\,
			\mvnormal{\meanvec{\clusteridx}}{\covmtx{\clusteridx}}
			\big(\featurevec^{(\sampleidx)}\big)}
			{\sum_{\clusteridx'=1}^{\nrcluster} p_{\clusteridx'}\,
			\mvnormal{\meanvec{\clusteridx'}}{\covmtx{\clusteridx'}}
			\big(\featurevec^{(\sampleidx)}\big)} \text{.}
		\end{equation}
		The degrees of belonging \eqref{equ_cluster_posterior_dict} satisfy the
		constraints \eqref{equ_cluster_dob_dict}, so the result is a
		soft clustering. The level sets of the probability density function (pdf) of a
		multivariate normal distribution are ellipsoids whose axes are the
		eigenvectors of the covariance matrix
		(Bishop, 2006, Sect.~2.3), so a cluster represented this way
		is an ellipsoid rather than an intersection of halfspaces.
		For the days at Krems, the covariance matrices learned by the expectation–maximization (EM)
		algorithm have a long axis $2.8$ and $2.0$ times the short
		one, tilted by $50$ and $46$ degrees, so each cluster is elongated
		along the direction in which both temperatures rise together
		(Fig.~\ref{fig_cluster_dict}(b)). The larger of the two
		degrees of belonging names the $k$-means cluster for $335$ of the $366$
		days, and $58$ days have a degree of belonging between $0.2$ and $0.8$ to
		both clusters. Fig.~\ref{fig_cluster_dict}(d) contrasts the two
		assignments over the year: the $k$-means index jumps between
		$0$ and $1$, while the degree of belonging to the warm cluster is $0$ on
		every day from November to February and passes through
		intermediate values on days from March to October.
\par
		Third, for data points that are the nodes $\nodes = \{1,
		\ldots, \samplesize\}$ of a similarity graph with edge weights
		$\edgeweight_{\sampleidx,\sampleidx'} \geq 0$, a cluster is a
		subset $\cluster \subseteq \nodes$ of nodes that are densely
		connected among themselves and sparsely connected to the rest.
		Graph clustering methods measure this by the sum of the
		edge weights of the edges leaving the subset, divided by
		its size,
		\begin{equation}
			\label{equ_cluster_cut_dict}
			\frac{1}{|\cluster|} \sum_{\sampleidx \in \cluster}
			\sum_{\sampleidx' \notin \cluster}
			\edgeweight_{\sampleidx,\sampleidx'} \text{,}
		\end{equation}
		and a hard clustering into $\nrcluster$ clusters is good if
		the sum of the ratios \eqref{equ_cluster_cut_dict} over its
		clusters, the ratio cut, is small
		(von Luxburg, 2007, Sect.~5, Eq.~(1)). Spectral clustering
		minimizes the ratio cut approximately. For the days at Krems,
		the $k$-nearest-neighbor graph ($k$-NN graph) that joins each day to its $10$ nearest
		neighbors, with unit edge weights, has $2209$ edges;
		$2174$ of them join two days of the same $k$-means cluster and
		$35$ join a cold with a warm day. The ratio cut of the two
		clusters is $0.38$, against $12.07$ for the split of the days into
		those with an odd and those with an even index
		(Fig.~\ref{fig_cluster_dict}(c)).
\par
		Which subsets of a dataset are clusters therefore depends
		on the method and its hyperparameters, not on the
		dataset alone. The number $\nrcluster$ of clusters is an
		input to $k$-means and to a GMM, while density-based spatial clustering of applications with noise (DBSCAN)
		determines it from a distance threshold and a minimum
		cluster size. The shape of a cluster follows from its
		representation: an intersection of halfspaces for
		$k$-means, an ellipsoid for a GMM, and any shape that a
		chain of nearby data points can trace for DBSCAN and
		for graph clustering. The same $366$ days are split by a
		straight line in Fig.~\ref{fig_cluster_dict}(a), while in
		Fig.~\ref{fig_cluster_dict}(b) each day receives a degree of belonging to
		each of two tilted ellipses. The choice of representation is a
		choice of hypothesis space, and the number of clusters is chosen
		like any other hyperparameter, since the
		clustering error alone cannot choose it.
\par
		Clusters serve as categories where no label provides them,
		the setting of unsupervised learning. An energy supplier can
		treat the cold days of Fig.~\ref{fig_cluster_dict}(a) as the
		heating season and classify a new day by the side of the boundary
		line on which its feature vector falls. In
		image segmentation, a cluster of pixels with similar colors
		is one region of the image (Bishop, 2006, Sect.~9.1.1), and
		in customer segmentation a cluster of customers with similar
		purchase records is one market segment (Wedel and Kamakura, 2000).
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 2, horizontal sep=1.7cm,
				vertical sep=2.0cm},
			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) a cluster centroid per cluster},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=60]
			\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]{cluster_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]{cluster_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addplot[only marks, mark=x, mark size=3pt, thick, black]
				table[col sep=comma, x=tmin, y=tmax]{cluster_centroids.csv};
			\addlegendentry{cluster centroids (crosses)}
			\addplot[black, dashed, thin]
				table[col sep=comma, x=tmin, y=tmax]{cluster_boundary.csv};
			\addlegendentry{boundary (dashed line)}
			\nextgroupplot[
				xlabel={morning minimum temperature\\(b) a multivariate normal distribution per cluster},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=60]
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{gcluster}+2*\thisrow{shared}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{cluster_points_plot.csv};
			\addlegendentry{cold days (circles)}
			\addplot[only marks, mark=square, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{gcluster}+2*\thisrow{shared}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{cluster_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addplot[only marks, mark=*, mark size=1.6pt, black, forget plot,
				restrict expr to domain={\thisrow{gcluster}+2*\thisrow{shared}}{2:2}]
				table[col sep=comma, x=tmin, y=tmax]{cluster_points_plot.csv};
			\addplot[only marks, mark=square*, mark size=1.5pt, black,
				restrict expr to domain={\thisrow{gcluster}+2*\thisrow{shared}}{3:3}]
				table[col sep=comma, x=tmin, y=tmax]{cluster_points_plot.csv};
			\addlegendentry{shared days (filled markers)}
			\addplot[black, thin, forget plot]
				table[col sep=comma, x=tmin, y=tmax]{cluster_ellipse_cold.csv};
			\addplot[black, dashed, thin, forget plot]
				table[col sep=comma, x=tmin, y=tmax]{cluster_ellipse_warm.csv};
			\nextgroupplot[
				xlabel={morning minimum temperature\\(c) a connected set of nodes per cluster},
				ylabel={maximum daytime temperature},
				xmin=-9, xmax=23, ymin=0, ymax=60]
			\addplot[gray!70, thin, forget plot, -,
				quiver={u=\thisrow{u}, v=\thisrow{v}}]
				table[col sep=comma, x=tmin, y=tmax]{cluster_edges_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]{cluster_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]{cluster_points_plot.csv};
			\addlegendentry{warm days (squares)}
			\addlegendimage{gray!70, thin}
			\addlegendentry{edges (thin lines)}
			\nextgroupplot[
				xlabel={day of the year\\(d) hard against soft assignment},
				ylabel={assignment to the warm cluster},
				xmin=0, xmax=370, ymin=-0.05, ymax=1.6,
				ytick={0,0.5,1}]
			\addplot[only marks, mark=o, mark size=1.6pt, black]
				table[col sep=comma, x=doy, y=cluster]{cluster_points_plot.csv};
			\addlegendentry{$k$-means index (circles)}
			\addplot[only marks, mark=x, mark size=3pt, thick, black]
				table[col sep=comma, x=doy, y=dobwarm]{cluster_points_plot.csv};
			\addlegendentry{GMM degree of belonging (crosses)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{Every $18$th of the $366$ days of $2024$ at Krems, $21$
			days, under the three representations of a cluster. (a) The
			days drawn as cold days (circles) or warm days (squares) by
			the nearer of the two cluster centroids of $k$-means
			(crosses); the boundary between the two clusters is a straight
			line (dashed line). (b) The two multivariate normal distributions of a
			GMM, the cold cluster (solid ellipse) and the warm
			cluster (dashed ellipse), each drawn as the level set of its
			pdf at twice the standard deviation along each axis; a
			day is drawn by the cluster with the larger degree of belonging, and
			filled where that degree of belonging is below $0.8$ (filled markers).
			(c) The $3$-nearest-neighbor graph of the $21$ drawn days,
			which joins each day to the three days most similar to it
			(thin lines); all $41$ edges join two days of the same
			cluster. (d) The same $21$ days by their day of the year:
			the $k$-means assignment, $0$ for a cold and $1$ for a
			warm day (circles), and the degree of belonging to the warm cluster
			under the GMM (crosses). Data generated by
			\texttt{pythondemos/cluster.py}
			\label{fig_cluster_dict}}
		\end{figure}

\subsection{Cross References}
clustering, cluster centroid, clustering error, hard clustering, soft clustering, degree of belonging, $k$-means, GMM, multivariate normal distribution, graph clustering, similarity graph, $k$-NN graph, edge weight, spectral clustering, DBSCAN, data point, feature vector, Euclidean distance, feature space, hyperparameter, convex, probability simplex, unsupervised learning

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Jain et al. (1999). Data clustering: a review. ACM Computing Surveys, 31(3), pp.~264--323.
  \item von Luxburg (2007). A tutorial on spectral clustering. Statist. Comput., 17(4), pp.~395--416.
  \item Wedel and Kamakura (2000). Market Segmentation: Conceptual and Methodological Foundations. 2nd ed., Kluwer Academic Publishers, Boston, MA.
  \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}
