
\section{Discrétisation}

\subsection{Comparaison des algorithmes}
\subsubsection{Introduction}
Le classifieur naïf bayesien est efficace en terme de temps d'exécution et de pourcentage de bonne classification. Néanmoins, celui-ci fonctionne sur des données symboliques, et les ensembles de données que nous avons rencontrés utilisent des attributs continus.

Nous allons donc recourir à des techniques de discretisation afin de pouvoir utiliser le classifier naïf bayesien sur des attributs continus.

Nous étudierons plus particulièrement deux techniques : Equal Width Discretization (EWD) et Equal Frequency Discretization (EWD).

\subsubsection{Protocole}

Nous avons comparé les algorithmes KNN (avec K = 5) avec le classifieur naïf bayesien.
Les ensemble des données sont les suivants :
\begin{itemize}
  \item[\textbullet] IRIS
  \item[\textbullet] Donut
  \item[\textbullet] Optical Recognition of Handwritten Digits
\end{itemize}
Les techniques de discretisation sont les suivantes :
\begin{itemize}
  \item[\textbullet] EFD (pour K ayant pour valeur 5, 10 et 15).
  \item[\textbullet] EWD (pour K ayant pour valeur 5, 10 et 15).
  \item[\textbullet] Aucune : on considère la valeur entière ou flottante comme un attribut symbolique.
\end{itemize}
Les graphiques nous permettrons de comparer deux points :
\begin{itemize}
  \item[\textbullet] Le pourcentage de bonne classification.
  \item[\textbullet] Le temps d'exécution.
\end{itemize}

\newpage
\subsubsection{Résultats}

\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/knn-vs-nb-iris}
		\includegraphics[width=8cm]{images/knn-vs-nb-donut}
		\includegraphics[width=11cm]{images/knn-vs-nb-digits}
	\end{center}
	\caption{Résultats sur l'ensemble de données Donut}
\end{figure}



\subsubsection{Analyse}

KNN domine le classifieur naïf bayesien sur les données continues. Néanmoins, son temps d'exécution est très largement supérieur et KNN n'est pas forcement utilisable du fait de sa lenteur sur de très grands ensembles de données.

Avec l'ensemble de données Digits, on constate que l'utilisation du classifieur naïf bayesien est meilleur sans technique de discrétisation. Nous utilisons les entiers compris entre 0 et 16 comme des valeurs symboliques, l'ensemble n'étant pas continu mais déjà discret.



\subsection{Impact de la valeur K de discrétisation}

\subsubsection{Protocole}
Les techniques de discrétisation EFD et EWD requièrent une taille K du nombre de valeurs discrètes différentes obtenues. Il ne semble pas y avoir de règle concernant le choix de cette valeur, et nous avons donc décidé d'étudier l'impact de cette valeur sur la classification.

Nous avons fait varier la valeur de K entre 2 et 48 sur les ensembles de données IRIS et Donut, et étudié le taux de bonne classification.

\subsubsection{Résultats}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics[width=8cm]{images/discretization/efd-ewd-iris}
		\includegraphics[width=8cm]{images/discretization/efd-ewd-donut}
	\end{center}
\end{figure}

\subsubsection{Analyse}

Nous observons une forme similaire pour les deux courbes :
\begin{itemize}
  \item[\textbullet] Une forte croissance pour $K \in [\![2, 7 ]\!]$.
  \item[\textbullet] Un maximum au point 7.
  \item[\textbullet] Une decroissance.
\end{itemize}
Dans le cas du donut, pour $K > 10$ la classification est assez stable autour de 70\%. Pour Iris, la chute est plus importante, mais peut-être également imputable au fait que K devient assez grand par rapport au nombre d'éléments de l'ensemble de données (150).

À partir de ces observations, on constate qu'une valeur faible de K, comprise entre 5 et 10, est la plus adaptée pour ces deux ensembles de données.

Enfin, on constate que les résultats d'EFD et EWD sont assez comparables. Les deux techniques offrent les même résultats sur le donut, mais EWD est plus efficace sur IRIS, en particulier il résiste plus à la chute pour $K > 20$.

Dans \emph{A comparative study of discretization methods for naive-bayes classifiers}, les études de Y.Yang et G.I Webb on d'ailleurs montré que les différentes techniques ont des résultats proches, EFD et EWD ayant l'avantage d'être les plus performantes. 
