
\section{Mushroom}

\subsection{Classifier bayesien naïf}
L'ensemble de données mushroom permet de savoir à partir de différentes caractéristiques d'un champignon (odeur, forme\ldots{}) si celui-ci est consommable ou non.

 L'intégralité de ses attributs sont symboliques, et par conséquent cet ensemble de données est parfaitement adaptée au classifieur bayesien naïf. Ce dernier calcul la probabilité pour un champignon à classifier d'appartenir à chacune des catégories (consommable ou non).
 
 Après l'avoir réalisé, nous l'avons testé avec une 10-Cross Validation sur l'ensemble de données Mushroom. Nous avons obtenu un taux de bonne classification de \underline{99.7\%}.
 
 
 \subsection{Continuousification}

\subsubsection{Introduction}
Le classifieur naïf bayésien est efficace en terme de temps d'éxecution mais il fait une forte hypothèse sur les données d'entrée: les dimensions doivent être indépendantes.

La continuousification est un procédé qui transforme les attributs symboliques en continus afin de pouvoir utiliser KNN.

Nous allons étudier quatre techniques de continuousification que sont NBF (N Binary Features), VDM (Value Difference Metric Mapping), MVD et la continousification naïve.

\subsubsection{Protocole}

Nous avons comparé le classifieur naïf bayésien et KNN avec les diverses méthodes de continuousification. L'ensemble de données utilisé est Mushroom.

Lors de l'utilisation complète de l'ensemble de données, toutes les méthodes de continousification donnent 100\% de bonne classification. Ainsi nous avons réalisé notre étude sur un échantillon de 300 éléments aléatoires. Les conclusions que l'on va tirer sur cet échantillon sont représentatives de ce qu'il se passe en faisant varier la taille de l'échantillon.

Les techniques de continuousification sont les suivantes:
\begin{itemize}
\item[\textbullet] Classifieur naïf bayésien
\item[\textbullet] KNN avec NBF (pour K ayant pour valeur 1, 3, 5)
\item[\textbullet] KNN avec VDM (pour K ayant pour valeur 1, 3, 5)
\item[\textbullet] KNN avec MDV (pour K ayant pour valeur 1, 3, 5)
\item[\textbullet] KNN avec la continuousification naïve (pour K ayant pour valeur 1, 3, 5)
\end{itemize}
Nous utilisons une 10-fold cross validation afin d'obtenir le temps de classification et la moyenne et variance de bonne classifications.\\
L'objectif est d'étudier les points suivants:
\begin{itemize}
\item[\textbullet] Les performances des différentes techniques de continuousification
\item[\textbullet] L'influence du K de KNN sur les résultats de chaque continuousification
\item[\textbullet] Le compromis temps d'exécution, résultats obtenus en fonction des différentes méthodes
\end{itemize}

\subsubsection{Résultats}

\begin{figure}[htbp!]
	\begin{center}
		\includegraphics[width=16cm]{images/continuousification-mushroom}
	\end{center}
\end{figure}

\subsubsection{Analyses}

On peut observer que toutes les méthodes sur cet ensemble de données réduit à 300 échantillons obtiennent de très bon résultats. VDM prend légèrement la tête en obtenant quelques soient les K testés 99\% de bonne classification. NBF et VDM donnent des résultats similaires entre 97\% et 99\%. Comme espéré, la continuousification naïve est la technique la moins performante.

Plus le K de KNN est grand, moins les techniques donnent de bons résultats. Ainsi, avec les méthodes de continuousification, KNN avec K=1 donne les meilleurs résultats.

Au niveau du temps d'exécution, KNN, avec les techniques de continuousification, est un ordre de grandeur plus lent que le classifieur naïf bayésien. Les deux méthodes donnent des résultats similaires, vouloir utiliser KNN est donc une mauvaise stratégie sur cet ensemble de données.

\subsubsection{KD-Tree}

Lors du TP1, l'implémentation de KNN avec un KD-Tree permettait de réduire le temps de calcul pour passer asymptotiquement d'une exécution quadratique à une exécution semi-linéaire. Au vu de l'importance des ensemble de données, nous avons emprunté l'implémentation de KNN avec KD-Tree au groupe de Félix Abecassis et Julien Marquegnies pour accélérer les calculs.

Nous avons été surpris de voir que sur l'ensemble de données Mushroom, cette implémentation était plus lente que l'implémentation classique.

\begin{figure}[htbp!]
	\begin{center}
		\includegraphics[width=13cm]{images/continuousification-mushroom-knn}
	\end{center}
\end{figure}

Le problème vient de la "Curse of Dimensions". En effet, les méthodes de continuousification génèrent un grand nombre de dimensions avec dans chaque dimension un petit nombre de valeurs. Ainsi la recherche dans le KD-Tree devient quasi-linéaire et le temps de construction surpasse le tri réalisé par KNN.

 
\subsection{Courbe ROC}

\subsubsection{Introduction}

Jusqu'à présent on s'intéressait à la moyenne des bons ou mauvais résultats. On va maintenant vouloir étudier les erreurs par classe. Pour ce faire, nous allons utiliser un Graphe ROC (Receiver Operating Characteristic). Pour un problème à deux classes, chaque axe représente le pourcentage de bonne classification par classe.

La Courbe ROC est une courbe qui relie les points du Graphe ROC en faisant varier les seuils du classifieur.


\subsubsection{Protocole}

Pour faire la Courbe ROC on utilise 11 biais différents. Voici la façon dont nous avons modifié les classifieurs pour prendre en compte ce biais.

\begin{enumerate}
\item[Naïf Bayésien] Le classifieur bayésien donne pour chaque classe un score. Par défaut, on prend la classe avec le meilleur score. Afin de faire varier les résultats, on compare le score de la première classe à la somme des scores des deux classes multiplié par un biais. Le biais varie de 0.0 à 1.0 avec un pas de 0.1
\item[KNN] Afin d'obtenir 11 valeurs différentes il faut utiliser un K au moins égal à 10. La première classe est choisie si le nombre de points les plus proches appartenant à cette classe est supérieur au biais. Le biais varie de 0 à 10.
\end{enumerate}

Nous utilisons une 10-fold cross validation pour calculer l'ensemble des valeurs.

\newpage
\subsubsection{Résultats}
\begin{figure}[htbp!]
	\begin{center}
		\includegraphics[width=8cm]{images/roc}
		\includegraphics[width=8cm]{images/roc-zoom}
	\end{center}
\end{figure}

\subsubsection{Analyses}

Grâce à ces courbes ROC on retrouve les résultats établis précédemment. Le naïf bayésien et VDM ont des résultats similaires, de même pour NBF et MDV. La continuousification naïve est également derrière. Pour départager les techniques donnant des résultats similaires, il va falloir donner un poids aux mauvaises réponses de chaque classe.

Si on considère qu'il ne faut absolument aucune erreur sur la première classe, alors il faut prendre l'algorithme qui a comme abscisse la valeur 0 et la plus grande ordonnée possible. Ici c'est VDM.

Dans le cas où les deux erreurs ont le même coût, on va prendre l'algorithme qui est le plus proche du point en haut à gauche. Ici c'est le classifieur naïf bayésien.




