\section{K-Means}\label{sec:kmeans}
K-Means is a standard clustering algorithm, exploiting a distance metric to cluster points in $K$ pre-defined clusters. Its ease of implementation makes it a standard choice for most of the clustering tasks, and the inference only requires to store the positions of the centroids, i.e. the clusters' centers as obtained after the training.\\
The iterative algorithm (\textit{Expectation-Maximization (EM)} algorithm) can be summarized as follows:

\begin{algorithm}[!htbp]
    \caption{K-Means}
    \begin{algorithmic}%[1]
        \State Initialize centroids $\mu_k, \ k=1,\dots, K$
        \Loop
            \NoDo
            \Loop{ over each point $x_n,\ n=1,\dots, N$}
                \State Evaluate cluster assignment as:\Comment{\textbf{E}-step}
                $$ z_{nk} = \underset{k}{\mathrm{argmin}\ } (x_n -\mu_k)^T(x_n - \mu_k)$$
            \State Recompute centroids:\Comment{\textbf{M}-step}
            $$ \mu_k = \frac{\sum_{n=1}^N z_{nk}x_n}{\sum_{n=1}^N z_{nk}}, \ k=1,\dots, K$$
            \EndLoop
        \EndLoop
        \State \textbf{until} convergence
    \end{algorithmic}
\end{algorithm}

As most of the clustering algorithms, initialization and convergence criteria are two critical factors in determining the overall performances. While the latter is typically bypassed by setting an appropriate number of iterations, the former requires several different runs of the algorithm, possibly converging to as many different solutions.\\
Some other limitations are then referred to:
\begin{itemize}
    \item the adoption of the Euclidean distance metric, treating all the dimensions of the feature space evenly. The relative representativeness and importance of a feature is completely lost
    \item non-linear separable clusters, even though clearly recognizable, are often wrongly recognized
\end{itemize}