
\section{Clustering}

\subsection{Tiny Toy Problem}

Nous utilisons K-Means avec un ensemble de données en une dimensions constitué des points : $\left\{1, 2, 7, 8, 9, 10\right\}$, et nous cherchons deux clusters ($K = 2$).\\
Nous obtenons les résultats suivants :

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=12cm]{images/kmean/kmean-1D-final}
	\end{center}
\end{figure}

Les résultats sont bien ceux attendus : nous identifions clairement deux clusters $\left\{1, 2\right\}$ et $\left\{7, 8, 9, 10\right\}$ et les deux centroids ont pour position 1,5 et 8,5, ce qui constitue bien la moyenne des coordonnées de chaque cluster.

\subsection{Teddy Toy Problem}

\subsubsection{K-Means}

Nous avons testé K-Means sur un ensemble de données composé de 16 clusters de 100 points.
Chacune de ses exécutions donne des résultats relativement différents, mais l'on observe un certain nombre de phénomène commun à chacune d'entre elles.
\newpage
Voici un exemple d'initalisation, puis le résultat final obtenu.

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/kmean/kmean-3-0}
		\includegraphics[width=8cm]{images/kmean/kmean-3-final}
	\end{center}
\end{figure}


La première conclusion que l'on tire des exécutions de K-Means est que le résultat obtenu n'est pas celui espéré. Il apparaît clairement à l'oeil humain 16 clusters bien distincts, mais l'algorithme détermine des clusters différents.\\
La solution trouvée respecte bien la condition d'arrêt, à savoir que nous ne pouvons plus changer les coordonnées des centroïds.\\

Nous identifions deux principaux phénomènes au niveau des résultats de cet algorithme.\\
Le premier est que certains clusters, au sens attendu par l'humain, possèdent deux centroïds : c'est notamment le cas en haut à droite de l'image finale.\\
Dans le sens inverse, certains centroïds sont au centre de plusieurs groupes de points, ce qui est le cas pour les points rose saumon et violets en bas de l'image.\\

En comparant les deux images, on constate que les clusters identifiés par l'algorithme sont assez proches de ceux calculés initialement. Nous pouvons donc déterminer deux formes d'amélioration :
\begin{itemize}
  \item[\textbullet] Amélioration de la phase d'initialisation.
  \item[\textbullet] Amélioration des itérations, c'est-à-dire améliorer les déplacements des centroïds.
\end{itemize}


\subsubsection{K-Means++}

K-Means++ vise à corriger certains problèmes de K-Means en améliorant la position initiale des centroïds. Il ne s'agit désormais plus d'un simple tirage aléatoire, mais d'une prise en compte des centroïds déjà calculés afin d'éviter d'avoir des positions initiales trop rapprochées.\\
L'initialisation conserve néanmoins son caractère aléatoire, comme le prouve ces deux exemples de positions initiales.
\newpage
\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/kmean/kmeanpp-init-rox}
		\includegraphics[width=8cm]{images/kmean/kmean++-1-0}
	\end{center}
\end{figure}
Nous constatons que les deux initalisations sont très différentes :
\begin{itemize}
  \item[\textbullet] Dans le premier cas, celle-ci est excellente : une seule itération suffira à obtenir les clusters que nous attendions.
  \item[\textbullet] Dans le second, les points sont assez comparables à K-Means, avec des zones vides et d'autres ayant plusieurs points. Les résultats finaux obtenus dans ce second cas sont assez décevants : 
\end{itemize}

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/kmean/kmean++-1-final}
	\end{center}
	\caption{Résultats de K-Means++ avec la seconde initialisation}
\end{figure}

% end
L'exécution de multiples K-Means++ sur un même dataset nous a montré des résultats très variables. On observe ainsi que l'initialisation a un rôle très important dans les résultats de K-Means et K-Means++. Des recherches sur le sujet on été publiées, notamment \emph{A systematic evaluation of different methods for initializing the K-means clustering algorithm} \footnote{\url{http://www.public.iastate.edu/~apghosh/files/IEEEclust2.pdf}} qui propose onze strategies pour déterminer les points initiaux.\\

Dans le dataset que nous avons utilisé ici, il est facilement observable qu'une initialisation en forme de maillage sélectionnerait un point par cluster attendu, mais cette technique pourrait être très peu efficaces sur d'autres formes d'ensemble de données.

\subsubsection{K-Means vs K-Means++}
Le graphique suivant compare les distances moyennes et le nombre d'itérations entre K-Means et K-Means++.


\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/kmean/kmean-vs-plusPlus}
	\end{center}
	\caption{Comparaison de K-Means et K-Means++}
\end{figure}
Nous pouvons tirer plusieurs enseignements :
\begin{itemize}
  \item[\textbullet] En terme de distance, K-Means++ améliore légèrement les résultats de K-Means.
  \item[\textbullet] Le nombre d'itérations de K-Means++ est nettement meilleur, grâce au fait que les points initiaux sont plus espacés.
  \item[\textbullet] Le nombre d'itérations moyenne des deux algorithmes est très variable : l'équart type est très élevé.
\end{itemize}

