\input{/home/kaiyou/Modèles/.preambles/article}

\usepackage{fullpage}
\usepackage{graphicx}

\author{Pierre Jaury}
\title{Apprentissage supervisé}
\date{10/02/2011}

\begin{document}

\maketitle
\tableofcontents

\section{Introduction}

On propose dans cette première approche du logiciel Weka d'apprentissage machine, d'expérimenter la classification automatique en assemblant des modules d'évaluation et de classification de données. On se concentre sur la séparation de valeurs dans l'espace en utilisant un module de SVM sur des données linéairement et non linéairement séparables ainsi que sur la génération d'arbres de décision en comparant différentes techniques.


\section{Apprentissage d'un SVM}

\subsection{Données linéairement séparables}

On débute avec des données séparables dans le plan : les points possèdent trois attributs dont deux coordonnées dans le plan et un attribut symbolique à deux valeurs $neg$ et $pos$. On charge un jeu de $40$ points grâce à un module \texttt{Arff Loader}, connecté à un \texttt{Data Visualizer} pour la visualisation -- voir figure \ref{arffloader}. Les données sont linéairement séparables : on peut les séparer sur leur troisième attribut selon leur position par rapport à une droite du plan, comme l'illustre la figure \ref{linsep}.



\begin{figure}
	\center
	\includegraphics[width=7cm]{arffloader}
	\caption{Chargement des données \textit{via} le module \texttt{Arff Loader}}\label{arffloader}
\end{figure}

\begin{figure}
	\center
	\includegraphics[width=9cm]{linsep}
	\caption{Données linéairement séparables, $pos$ en bleu, $neg$ en rouge, dans le plan $(x,y)$}\label{linsep}
\end{figure}

On utilise le jeu de données complet pour exercer et valider une classification par le module \texttt{SMO} -- voir figure \ref{smo}. On configure le module de sorte que le séparateur soit linéaire -- noyau polynomial de degré $1$ -- et on infère une droite de séparation d'équation : $1,452\cdot x - 0,823\cdot y - 0,734 = 0$. Le risque empirique fourni par l'évaluateur de qualité de la classification est nul ; en effet, le jeu de validation est le même que le jeu d'apprentissage.

\begin{figure}
	\center
	\includegraphics[width=12cm]{smo}
	\caption{Classification par le module \texttt{SMO}}\label{smo}
\end{figure}

Pour améliorer la classification, on sépare le jeu de données en deux : la première partie sert à l'apprentissage du classifieur, la seconde partie sert à valider la classification évaluée. Weka propose deux outils pour séparer ainsi les données : \texttt{TrainTestSplitMaker} et \texttt{CrossValidationFoldMaker}. \texttt{TrainTestSplitMaker} tire aléatoirement une part du jeu de données passée en paramètre et l'affecte à l'apprentissage, le reste servant à la validation. On l'exécute avec deux tiers de données pour l'apprentissage du classifieur -- voir figure \ref{split} -- qui infère une droite d'équation $1,453\cdot x - 0,818\cdot y - 0,727 = 0$ avec un risque empirique de $7\%$. Le risque empirique est élevé : l'entraînement du classifieur sur un jeu de données indépendant du jeu de validation est peu efficace.

\begin{figure}
	\center
	\includegraphics[width=9cm]{split}
	\caption{Séparation des données en un jeu d'apprentissage et un jeu de validation}\label{split}
\end{figure}

Finalement, \texttt{CrossValidationFoldMaker} propose le comportement le plus satisfaisant : il génère un certain nombre de couples jeu d'apprentissage-jeu de validation à partir du jeu de données initial, pour effectuer de la validation croisée. On exécute la classification à partir de la série de jeux générés -- voir figure \ref{cross}; le classifieur infère une droite d'équation $1,453\cdot x - 0,817\cdot y - 0,726 = 0$ avec un risque empirique nul.

\begin{figure}
	\center
	\includegraphics[width=9cm]{cross}
	\caption{Utilisation de la validation croisée}\label{cross}
\end{figure}

\subsection{Données non linéairement séparables}

On charge ensuite un jeu de données de taille et attributs similaires, qui n'est toutefois pas linéairement séparable, comme l'illustre la figure \ref{nonlinsep}. Une intuition laisse supposer que les données sont séparables sur leur troisième attributs par une parabole du plan. On configure le \texttt{SMO} pour classifier les données de part et d'autre d'un polynôme de degré $2$. Le classifieur infère une courbe à $6$ vecteurs de support (approximation de la parabole par autant de segments de droites). Le risque empirique obtenu après une validation croisée est nul : l'ensemble des valeurs est correctement classifié.

\begin{figure}
	\center
	\includegraphics[width=9cm]{nonlinsep}
	\caption{Données non linéairement séparables, $pos$ en bleu, $neg$ en rouge, dans le plan $(x,y)$}\label{nonlinsep}
\end{figure}


\section{Apprentissage d'un arbre de décision}

En plus de la séparation de valeurs, Weka peut évaluer des classifieurs tels que les arbres de décision. On exploite un jeu de $624$ données bancaires à $16$ attributs nommés de $A_1$ à $A_{16}$. Les attributs $A_2, A_3, A_{11}, A_{14}$ et $A_{15}$ prennent leurs valeurs dans les réels. Les autres attributs sont symboliques ; $A_1, A_9, A_{10}$ et $A_{16}$ sont bivalués ; $A_5$ et $A_{13}$ sont trivalués ; $A_4$, $A_6$ et $A_7$ ont respectivement des domaines à $4, 16$ et $9$ valeurs. La classe à prédire correspond à l'attribut $A_{16}$ qui prend ses valeurs dans $\{pos,neg\}$.

En utilisant deux tiers des données pour l'apprentissage et un tiers pour la validation, on exécute le classifieur nommé \texttt{J48} -- voir figure \ref{j48}. L'arbre résultat est représenté figure \ref{arbrej48}. $84\%$ des données de test sont correctement évaluées, dont la plus grande partie correspond à de bonnes évaluations pour la classe $neg$. On note que les seuls attributs $A_9, A_{15}, A_{10}, A_4 et A_3$ suffisent ici à la classification.

\begin{figure}
	\center
	\includegraphics[width=11cm]{j48}
	\caption{Classification \textit{via} le module \texttt{J48}}\label{j48}
\end{figure}

\begin{figure}
	\center
	\includegraphics[width=12cm]{arbrej48}
	\caption{Arbre inféré par le classifieur \texttt{J48}}\label{arbrej48}
\end{figure}

Etant donnée la taille du jeu de données, faire varier la proportion de données utilisée pour l'apprentissage influe peu sur le risque empirique en sortie du classifieur. On obtient toutefois des résultats légèrement meilleurs en augmentant la taille du jeu de données d'apprentissage, la taille du jeu de validation demeurant raisonnable compte tenu de celle du jeu de départ. On pourrait également améliorer la stratégie d'évaluation en augmentant la profondeur de l'arbre et en testant plus d'attributs.


\section{Comparaison des classifieurs}

On compare l'apprentissage par arbre \texttt{J48} avec un \textit{fast decision tree} implémenté dans le module \texttt{REP}. On conserve la configuration par défaut du module et on augmente la taille du jeu d'apprentissage à $90\%$ des valeurs disponibles. On n'effectue aucune adaptation sur les données puisque le classifieur \texttt{REP} est en mesure de travailler directement sur les attributs numériques et symboliques.

Après avoir exécuté le classifieur -- voir figure \ref{rep} --, on observe sur l'arbre qu'une décision -- voir figure \ref{arbrerep} -- simple sur l'attribut $A_9$ suffit à classer avec succès plus de $92\%$ des données de test, comme on pouvait en avoir l'intuition à partir de la figure \ref{arbrej48}. Le classifieur \texttt{REP} est plus rapide à l'exécution que le classifieur \texttt{J48} et fournit un arbre élagué plus pertinent dès la première exécution.

\begin{figure}
	\center
	\includegraphics[width=11cm]{rep}
	\caption{Classification \textit{via} le module \texttt{REP}}\label{rep}
\end{figure}

\begin{figure}
	\center
	\includegraphics[width=6cm]{arbrerep}
	\caption{Arbre inféré par le classifieur \texttt{REP}}\label{arbrerep}
\end{figure}


\section{Validation}

On ajoute un classifieur de type \texttt{J48} non élagué pour le comparer aux deux classifieurs précédents -- voir figure \ref{unpruned}. Toujours avec $90\%$ de données utilisées pour l'apprentissage, ce classifieur obtient de moins bonnes performances : moins de $80\%$ des données sont correctement classées dans le jeu de validation. On explique ce comportement en observant la structure complexe de l'arbre sur la figure \ref{arbreunpruned} : l'apprentissage sans élagage revient à un apprentissage par c\oe{}ur sur le jeu de données d'entraînement, qui est finalement moins pertinent sur le jeu de données de test.

On constate ainsi en augmentant le nombre minimal de valeurs par feuille de l'arbre -- ce qui revient à éviter le cas de l'apprentissage par c\oe{}ur où une feuille est associée à une valeur -- à une valeur de $3$ par exemple, qu'on simplifie la structure de l'arbre et qu'on améliore la performance du classifieur à environ $85\%$ de valeurs correctement classées.

\begin{figure}
	\center
	\includegraphics[width=11cm]{unpruned}
	\caption{Classification \textit{via} le module \texttt{J48} non élagué}\label{unpruned}
\end{figure}

\begin{figure}
	\center
	\includegraphics[width=11cm]{arbreunpruned}
	\caption{Arbre inféré par le classifieur \texttt{J48} non élagué}\label{arbreunpruned}
\end{figure}


\section{Fusion des classifieurs}

On termine l'approche du logiciel Weka par l'utilisation des techniques de \textit{boosting} avec le module de fusion de classifieurs \texttt{adaBoost}. Toujours sur le jeu de données bancaires à $16$ attributs, on compare les performances d'un module d'arbre de décision réduit \texttt{Decision Stump} avec celles d'un module \texttt{adaBoost} fusionnant trois itérations de \texttt{Decision Stump} avec les mêmes paramètres -- voir figure \ref{adaboost}.

En ne fusionnant que trois itérations du même module, les performances du classifieur sont comparables à celle du module initial -- $81\%$ de réussite sur le jeu de validation. On améliore toutefois largement les performances en augmentant le nombre d'itération : $90\%$ de réussite à partir d'une dizaine d'itération. La complexité de l'arbre inféré augmente toutefois avec le nombre d'itérations.

\begin{figure}
	\center
	\includegraphics[width=11cm]{adaboost}
	\caption{Classification \textit{via} le module \texttt{adaBoost}}\label{adaboost}
\end{figure}


\section{Conclusion}

La vue \textit{knowledge flow} du logiciel Weka offre la possibilité d'évaluer rapidement le fonctionnement et les performances de quelques classifieurs automatiques. L'exercice a mis en évidence la nécessité de connaître le jeu de données dans son ensemble pour la configuration des classifieurs de type SVM ainsi que la grande variété de techniques -- et de performances associées -- de générations d'arbres de décision.


\end{document}