\label{problem_definition}
Clustering is the task of gathering items in a way that elements belonging
to the same group (the \emph{cluster}) are more similar to each other other than the ones
assigned to the others.\\
More formally, given a input:
\begin{itemize}
    \item $X = \{x_0, \dots ,x_n\}$, the initial set of elements.
    \item $d: X \times X \to \mathbb{R}$, a \emph{metric} measuring the similarity.
\end{itemize}
The final goal is to find the cluster configuration
\begin{equation*}
    C = \left\{ c_0, \dots , c_m \right\} \mid \bigcup_{C} = X
\end{equation*}
partitioning $X$ into $m$ clusters, maximizing the intra-cluster distance
(dual problem of minimizing inter-cluter distance):

\begin{equation}
    \underset{C}{\mathrm{argmax}}
    \sum_{c \in C}
        \sum_{i,j}^{|c|}
            d(c_i,c_j)
\end{equation}


\subsection*{Challenges}
The concept of clustering is simple and powerful; moreover, its versatility
and generality are its greatness and at the same time source of many difficulties.
%% Metrics identification
Given the only strict requirement to be the definition of a metric over the
domain of $X$, clustering is applied to a wide variety of problems.
Clearly, each domain offers different optimization opportunities and
particular challenges.
In particular, the choice of the metric heavily influences the final outcome quality.
As a result even the medical~\cite{siless2013comparison}, the mechanical
engineering~\cite{wilding2011clustering} and the mobile networks~\cite{cheng2009stability}
literatures features different studies that address this particular challenge
suggesting highly specialized distance functions.

%% Inter/Intra cluster distance measure
Once the proper metric is identified, the following huge influencing factors
are the mathematical definitions of ``intra-cluster'' and ``inter-cluster''
distances. They vary a lot in the different implementation leading to
completely different clustering configurations.
For example, three methods are widely used when performing agglomerative
clustering to define the distance between two clusters:
the average, the minimum, and the maximum distance.
The average approach uses the barycenters, while the minimum (maximum)
relies upon the minimal (maximal) distance between any two points
belonging to a different clusters.


\subsection*{Choosing the $k$ parameter}
The first main issue of the k-means described in Section \ref{related} is the choice
of the number of clusters the dataset has to be divided into.

The original k-means does not address this problem at all. Thus, some heuristic has to
be applied. One possibility is to have a deep knowledge of the structure underlying the
dataset, having an idea of the target number of groups. On the other hand, especially
in exploratory data analysis, this value cannot be known in advance.
Hence, the most common solution is to run the algorithm with increasing values of $k$ and
finally keeping the parameter that produces the best-quality clusters.

Choosing the right value for this parameter is crucial, since a wrong one may
instruct the algorithm to collapse entities that are actually very far from each other
(or vice versa).


\subsection*{Positioning the initial centroids}
Given that an optimal value for $k$ is found, the other big problem is how to position the $k$
initial centroids.

Given enough time, the k-means algorithm will always converge. However it may be to a local
minimum. This is highly dependent on the initialization of the centroids. The boostrapping
phase can be addressed in various ways. For example, the
\emph{scikit-learn}\footnote{http://scikit-learn.org} Python library
uses an approach that positions the initial centroids to be (generally) distant
from each other by default. This procedure provides provably better results than using a random
one~\cite{arthur2007k}.

Using a proper and efficient boostrapping heuristic is very important, since misplacing
the initial centroids does not allow the algorithm to find the real clusters underlying
the data.
