

\section{ID3}

\subsection{Arbres induits par ID3}

Nous avons implementé l'algorithme ID3\cite{Quinlan1986}, et obtenu les arbres suivants :

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=13cm]{images/tree-play-tennis}
	\end{center}
	\caption{Arbre induit pour l'ensemble de données \emph{Play Tennis}}
\end{figure}

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=13cm]{images/tree-mush}
	\end{center}
	\caption{Arbre induit pour l'ensemble de données \emph{Mushroom}}
\end{figure}


\newpage
Nous remarquons que ces arbres sont petits par rapport au nombre d'attributs de chaque ensemble de données et leurs valeurs possible. Ils permettent néanmoins 100\% de bonne classification.\\
À partir de ces images, nous pouvons identifier très facilement un système à base de règle permettant de réaliser les classifications sans erreurs.

\subsection{Amélioration d'ID3}

\subsubsection{Gain Ratio}

Nous avons implementé la technique \emph{Gain Ratio}\cite{Quinlan1986} et comparé les arbres induits. Dans le cas de l'ensembles de données \emph{Play Tennis} les deux arbres sont exactement les même.\\
Dans l'ensemble de données \emph{mushroom}, l'arbre devient un peigne droit. Les première modifications apparaissent au 3e noeud : \emph{habitat} est remplacé par \emph{veil-color}.\\\\

Le but de cette technique est de ne pas sélectionner comme attribut pour un noeud une donnée trop discriminante et créerait des sous-arbres à partir de parties de l'ensemble de données trop petites. Nous démontrons l'utilité de cette méthode à partir des données suivantes :

\begin{center}
\begin{tabular}{|c||c|c|}
\hline
Label (sexe) & Mois naissance & Longueur des cheveux\\
\hline
fille & mai & long\\
\hline
fille & avril & long\\
\hline
fille & février & long\\
\hline
garçon & décembre & court\\
\hline
garçon & juin & court\\
\hline
\end{tabular}
\end{center}
Ces données nous indiquent le sexe d'un individu à partir de son mois de naissance et la longueur de ses cheveux.\\
Nous voyons ci-dessous les arbres induits par ID3 avec le calcul du gain classique, puis avec le gain-ratio.

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[height=3.5cm]{images/id3-gain}
		\includegraphics[height=3.5cm]{images/id3-gain-ratio}
	\end{center}
\end{figure}
% Ajouter les valeurs du tableau des gains
Nous observons que l'arbre de gauche est valide par rapport aux données que nous lui avons fourni, mais on se doute que pour de nouveaux individus les résultats seront assez aléatoires : il n'y a pas de relation entre le sexe d'une personne et son mois de naissance.\\
Le gain-ratio nous a permis d'obtenir l'arbre de droit. Il détermine qu'un individu est une fille si ses cheveux sont longs, et un garçon si ceux-ci sont courts. Ces règles semblent nettement plus efficace : pour un ensemble de nouveaux individus, le pourcentage de bonne classification sera plus important.

\subsubsection{Impureté de Gini}

Nous avons ajouté dans notre classifieur la possibilité d'utiliser l'impureté de Gini\cite{brei84a} en lieu et place des calculs d'entropie. Cette modification a entrainé un changement des entropies et des gains dans l'arbre, mais la structure de celui-ci est restée inchangée.

\subsubsection{Gestion des attributs continus}

Nous avons étudié les résultats d'une 10-Cross validation sur l'ensemble de données \emph{Iris}. Nous avons fait varier le paramètre $K$ des méthodes EFD et EWD afin d'en mesurer les impacts sur la classification. Nous comparons cette valeur au résultat d'un 5NN.

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=13cm]{images/efd-ewd-ID3-iris}
	\end{center}
\end{figure}
Nous constatons que le pourcentage de bonne classification varie avec une amplitude de généralement 10\%, avec plusieurs maximums locaux. EWD semble plus efficace que EFD. Il est important de noter que pour la valeur $K=6$, ID3 avec EWD est aussi efficace que KNN, mais avec un temps d'exécution beaucoup plus faible.

\subsubsection{Élagage}

Nous avons réalisé la technique d'élagage \emph{Reduced Error Pruning}\cite{Elomaa01ananalysis}. Celle-ci ne modifie pas l'arbre des ensembles de données \emph{Mushroom} ou \emph{PlayTennis}. Nous avons cependant constaté aux cours de nos tests des améliorations de certains résultats.

\subsection{Évaluation des paramètres d'ID3}

ID3 a la particularité de pouvoir être configuré de différentes manières :
\begin{itemize}
  \item[\textbullet] Utilisation de l'entropie ou de l'impureté de Gini.
  \item[\textbullet] Utilisation du Gain Ratio.
  \item[\textbullet] Utilisation d'une technique d'élagage.
\end{itemize}
Nous avons évalué sur deux ensembles de données l'impact des évolutions de ces valeurs, et obtenu les résultats suivants :

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/iris-id3}
		\includegraphics[width=8cm]{images/adult-id3}
	\end{center}
\end{figure}
Dans ces graphiques, le gain ratio est la technique qui améliore le plus le résultat, mais cette constatation peut ne pas être vraie sur d'autres ensembles de données. Il est donc recommandé d'effectuer ces tests pour paramètrer son classifieur ID3 lors de l'utilisation d'un nouvel ensemble de données.\\
On constate que selon l'ensemble de données, combiner plusieurs options (Gini, Gain Ratio, élagage) peut améliorer ou affaiblir le classifieur.\\
L'utilisation du Gain-Ratio est préjudiciable aux performances : il est nécessaire d'effectuer beaucoup plus de calculs à la construction de l'arbre.
