Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Projet-1` ere Partie IFT-4102 et IFT-7025 : Techniques avanc´ ees en Intelligen

Projet-1` ere Partie IFT-4102 et IFT-7025 : Techniques avanc´ ees en Intelligence Artiﬁcielle ` A rendre avant le 25 mars 2019 ` a 23h55 Introduction Dans cette premi` ere partie du projet, vous devez impl´ ementer deux techniques d’appren- tissage machine : les K plus proches voisins et la classiﬁcation na¨ ıve bay´ esienne. La meilleure fa¸ con d’apprendre c’est de programmer sans avoir recours aux biblioth` eques d´ ej` a prˆ etes ` a faire tout le travail d’apprentissage (telle que scikit-learn), il est donc interdit d’utiliser toute biblioth` eque ou tout programme d´ ej` a fait. D` es lors, il vous faut programmer de A ` a Z et si jamais vous voulez utiliser une partie d´ ej` a faite il vous faut demander l’autorisation ` a Amar Ali-Bey. Aﬁn d’´ evaluer l’eﬃcacit´ e de ces techniques, vous devez entrainer et tester votre code sur des bases de donn´ ees (datasets) r´ eelles. 1 Bases de donn´ ees (Datasets) Les datasets (bases de donn´ ees) fournis ici proviennent tous du site UCI 1 (un d´ epˆ ot de datasets d’apprentissage machine). Sous la cat´ egorie classiﬁcation, nous avons s´ electionn´ e trois datasets qui, selon nous, donneront une diversit´ e de r´ esultats avec les m´ ethodes d’ap- prentissage automatique s´ electionn´ ees. Note : tous ces datasets sont fournis dans le dossier Code/datasets en attach´ e. 1.1 Classiﬁcation des Iris (Iris Dataset) Ce dataset 2 classe les ﬂeurs en trois diﬀ´ erentes classes d’iris en fonction de la taille des diﬀ´ erentes caract´ eristiques (longueur du s´ epale, largeur du s´ epale, longueur du p´ etale et largeur du p´ etale). Il s’agit d’un probl` eme de classiﬁcation simple et classique. C’est un m´ elange de classes lin´ eairement s´ eparables et ins´ eparables. Quelques caract´ eristiques sur le dataset Le ﬁchier contenant le dataset s’appelle bezdekIris.data et se trouve dans ce r´ epertoire 3. — Nombre d’instances (entrainement et test) : 150 (50 instance dans chaque classe) — Nombre d’attributs pour chaque instance : 4 num´ eriques, et un d´ eﬁnissant la classe ` a laquelle appartient l’instance (´ etiquette). 1. http://archive.ics.uci.edu/ml/datasets.html 2. https://archive.ics.uci.edu/ml/datasets/Iris 3. http://archive.ics.uci.edu/ml/machine-learning-databases/iris/ 1 — D´ etails sur les attributs : chaque ligne dans le ﬁchier du dataset repr´ esente une instance sous la forme : <attr1>,<attr2>,<attr3>,<attr4>,<class> — attr1 : longueur du s´ epale (en cm) — attr2 : largeur du s´ epale (en cm) — attr3 : longueur du p´ etale (en cm) — attr4 : largeur du p´ etale (en cm) — class : on en distingue 3 types — Iris-setosa — Iris-versicolour — Iris-virginica 1.2 Base pour des probl` emes MONKS (MONKS Problems Data- set) Ce dataset 4 contient des attributs arbitraires et utilise un classiﬁcation binaire (0 et 1 sont utilis´ es comme ´ etiquettes pour chaque exemple). Il reﬂ` ete 3 probl` emes MONKS diﬃciles ` a r´ esoudre, et a ´ et´ e utilis´ e pour une comp´ etition d’algorithmes d’apprentissage. Assurez vous d’avoir fait vos tests sur les trois probl` emes. Ce dataset est un peu plus diﬃcile, ne vous attendez pas ` a de tr` es bonnes performances. Quelques caract´ eristiques sur le dataset Les ﬁchiers d’entraˆ ınement et de test sont respectivement monks-i.train et monks-i.test (i = 1,2,3), et se trouvent dans ce r´ epertoire 5. — Nombre d’instances (entraˆ ınement et test) : 432 — Nombre d’attributs dans chaque instance : 8 y compris le label (l’´ etiquette de la classe 0 ou 1) — D´ etails sur les attributs : Chaque ligne dans le dataset repr´ esente une instance sous la forme : <class> <attr1> <attr2> <attr3> <attr4><attr5> <attr6> <Id> — class : {0, 1} — attr1 : {1, 2, 3} — attr2 : {1, 2, 3} — attr3 : {1, 2} — attr4 : {1, 2, 3} — attr5 : {1, 2, 3, 4} — attr6 : {1, 2} — Id : un nom unique pour chaque instance Notez que certains attributs ont des domaines de valeurs diﬀ´ erents. Pour plus de d´ etails sur le dataset, visitez ce lien 6 4. https://archive.ics.uci.edu/ml/datasets/MONK’s+Problems 5. http://archive.ics.uci.edu/ml/machine-learning-databases/monks-problems/ 6. http://archive.ics.uci.edu/ml/machine-learning-databases/monks-problems/monks.names 2 1.3 Base d’enregistrements de votes au Cong` es (Congressional Voting Records Dataset) Ce dataset 7 classe les membres du Congr` es en D´ emocrates et R´ epublicains en fonction de leur dossier de vote. C’est un probl` eme un peu plus facile ` a r´ esoudre, et vous devriez atteindre des performances assez ´ elev´ ees. Il s’agit d’un bon dataset ` a tester pour le d´ ebogage. Il vous revient de regarder de plus pr` es et d’analyser son contenu. Remarque : il est important de noter que le symbole ≪?≫dans ce dataset ne signiﬁe pas que la valeur de l’attribut est inconnue ou manquante, il signiﬁe simplement que la valeur n’est pas ≪oui≫ou ≪non≫, voir plus de d´ etails ici 8. 2 Techniques d’apprentissage automatique ` a d´ evelopper Cette section d´ ecrit les techniques d’apprentissage automatique que vous aurez ` a impl´ ementer pour mettre en œuvre et tester les datasets fournis. En Apprentissage Automatique, plusieurs termes sont utilis´ es pour ´ evaluer les performances des diﬀ´ erentes techniques. Nous trouvons par exemple l’Accuracy (exactitude) qui est tout simplement le pourcentage des exemples bien classiﬁ´ es par rapport au nombre total des exemples pr´ esent´ es ` a l’algorithme. 1. Faites une recherche et d´ eﬁnissez les termes suivants : — La matrice de confusion (Confusion matrix) pour la classiﬁcation — La pr´ ecision (Precision) — Le rappel (Recall) Remarques : — Vous pouvez voir sur Wikipedia. C’est ` a vous de faire un petit r´ esum´ e et d’inclure dans votre rapport une d´ eﬁnition de chaque terme. — En g´ en´ eral, les termes Pr´ ecision et Rappel sont d´ eﬁnis pour les probl` emes de classiﬁ- cation binaire. Pour le dataset Iris, la classiﬁcation n’est pas binaire (les instances sont de 3 diﬀ´ erentes classes). Dans ce cas il convient de calculer la Pr´ ecision et le Rappel s´ epar´ ement pour chaque classe (une approche de un-contre-tous). — Pensez ` a utilisez la matrice de confusion pour vous aider ` a d´ eduire la Pr´ ecision et le Rappel. 2.1 K plus proches voisins (K-nearest neighbors ) Pour cette m´ ethode vous devez impl´ ementer la technique des K plus proches voisins introduite au chapitre 18.8.1 et tr` es bien expliqu´ ee sur Wikip´ edia 9. 1. Mentionnez la m´ etrique de distance que vous avez choisie, et justiﬁez votre choix ; 2. Donnez le pseudo-code (et l’initialisation des param` etres s’il y a lieux) de l’algorithme que vous avez impl´ ement´ e. 3. Donnez alors : 7. https://archive.ics.uci.edu/ml/datasets/Congressional+Voting+Records 8. https://archive.ics.uci.edu/ml/machine-learning-databases/voting-records/ house-votes-84.names 9. https://fr.wikipedia.org/wiki/Recherche_des_plus_proches_voisins 3 — L’exactitude (Accuracy) — La matrice de confusion (Confusion matrix) — La pr´ ecision (Precision) — Le rappel (Recall) 4. Pour le choix de K : — IFT-4102 seulement : utilisez K = 5 (vous avez aussi la possibilit´ e de tester avec d’autres valeurs de K). — IFT-7025 seulement : utilisez la validation crois´ ee (cross-validation) pour d´ eterminer la meilleure valeur de K. Expliquez votre d´ emarche pour la validation crois´ ee et d´ etaillez, dans la mesure du possible, votre d´ emarche. Pour la validation crois´ ee et pour chacun des K variant entre KMin, . . . , KMax, on divise l’´ echantillon original en L ´ echantillons, puis on s´ electionne un des L ´ echantillons comme ensemble de validation et les (L−1) autres ´ echantillons consti- tueront l’ensemble d’apprentissage. On calcule alors l’erreur. Puis on r´ ep` ete l’op´ eration en s´ electionnant un autre ´ echantillon de validation parmi les (L −1) ´ echantillons qui n’ont pas encore ´ et´ e utilis´ es pour la validation du mod` ele. L’op´ eration se r´ ep` ete ainsi L fois (g´ en´ eralement 10 fois) pour qu’en ﬁn de compte chaque sous-´ echantillon ait ´ et´ e utilis´ e exactement une fois comme ensemble de validation. La moyenne des L erreurs est enﬁn calcul´ ee pour estimer l’erreur de pr´ ediction. On choisit alors le K entre KMin, . . . , KMax qui donne la plus faible erreur. 2.2 Classiﬁcation Na¨ ıve Bay´ esienne Ce type de classiﬁcation est d´ ecrit dans le chapitre 20.2 du livre, mais aussi sur Wi- kip´ edia 10. 1. Donnez le pseudo-code (avec l’initialisation des param` etres) de l’algorithme impl´ ement´ e. 2. Impl´ ementez ce mod` ele et faites les tests sur les datasets. 3. Donnez alors : — L’exactitude (Accuracy) — La matrice de confusion (Confusion matrix) — La pr´ ecision (Precision) — Le rappel (Recall) 3 Directives Commencez par voir de plus pr` es le code ( voir dossier Code) qui vous est donn´ e, vous devez compl´ eter les fonctions de lecture (ou chargement) des datasets, ensuite, impl´ ementer les deux techniques en suivant le squelette des classes tel qu’impos´ e dans les ﬁchier python en attach´ e. — Compl´ etez le ﬁchier load_datasets.py, cela uploads/S4/ projet-partiel.pdf