À faire seul ou en binôme.
Codez de A à Z la classification basée sur un arbre de décision.
Langage “standard” au choix : R, Python, MATLAB, C/C++, Java etc.
Évitez ça https://fr.wikipedia.org/wiki/Brainfuck SVP :-)
Concernant Adult vous pourrez supprimer les lignes incomplètes.
(Il y a des manières plus subtiles de traiter les valeurs manquantes, cf. question II).
Barême indicatif en italique, auquel s'ajouteront peut-être d'éventuels bonus.
I) Réfléchir à la façon dont vous allez coder un arbre. Deux principales options :
Pour l'option a) voir https://www.geeksforgeeks.org/binary-tree-array-implementation/, et
pour l'option b) https://www.geeksforgeeks.org/binary-tree-set-1-introduction/
Vous pouvez préférer utiliser une librairie externe (n'importe laquelle).
Je vous en propose une en C : https://github.com/yagu0/cgds ; voir src/Tree.{h,c}.
Vous pouvez choisir d'aller au plus simple en prenant l'option a) et en ne considérant que les arbres binaires. C'est un peu limité (obligation de découper en deux classes pour une variable symbolique à plusieurs modalités), mais pas tant.
Note : le choix dans le notebook envoyé pendant le cours correspond à l'option a).
Vous pouvez le reprendre et vous en inspirer.
Il y a quelques modifications à faire pour supporter les attributs symboliques.
https://auder.net/miage/E_seance9-10_Classification/Arbre_Classif.ipynb.
3 points : 1 si choix adéquat, 2 si la structure de données est bien expliquée.
II) Écrire une fonction buildTree prenant en entrée des données (stockées dans un fichier), la nature des variables (ordinales, continues ou symboliques), et un critère (entropie et Gini au moins). Comme son nom l'indique cette fonction construit et renvoie l'arbre, non élagué : toutes ses feuilles sont homogènes ("pures", une seule classe).
Réfléchir au traitement des valeurs manquantes, et écrire le code correspondant (dans la même fonction). Il existe des techniques assez élaborées pour cela : on ne vous demande pas de les implémenter. En revanche, votre code ne doit pas se contenter de supprimer les lignes avec valeurs manquantes.
6 points : 1 si calcul correct de la valeur de split continue/ordinale, 1 si calcul correct pour split symbolique, 2 points sur le traitement des valeurs manquantes : 1 si bien expliqué (et relativement pertinent), 1 si implémenté. 1 point si au moins entropie + Gini (argument de la fonction), 1 pour la lisibilité du code.
III) Écrire une fonction predict prenant en entrée un arbre retourné par buildTree, et un vecteur correspondant à une ligne (un nouvel individu). Cette fonction retourne la classe prédite, même si certains attributs du vecteur à prédire sont manquants : réfléchissez à une manière de procéder puis implémentez-la.
Tester sur le jeu de données initial (tout doit être parfaitement classé). Découpez vos données en ensembles d'apprentissage A et de test T (dans des proportions raisonnables, 60-40 par exemple), puis construisez l'arbre sur A et testez sur T. L'erreur devrait alors être élevée.
4 points : 1 pour diviser aléatoirement en A et T, 1 pour la boucle effectuant la prédiction, 1 pour prédire en cas de valeur d'attribut manquante, 1 pour tenir compte de l'élagage (cf. ci-après).
IV) Écrire une fonction pruneTree prenant en entrée un arbre retourné par buildTree et un jeu de données. Cette fonction doit élaguer l'arbre suivant la formule donnée en cours, en estimant l'erreur “réelle” à chaque étape. Un argument supplémentaire sera donc nécessaire : alpha dans [0, 1].
Note : au lieu de retourner un nouvel arbre, vous pouvez dans buildTree marquer chaque noeud avec la valeur de alpha “critique”, au-dessus de laquelle ce noeud est terminal. Cela permet de prédire rapidement la classe d'une nouvelle entrée pour diverses valeurs de alpha.
Enfin, vous devez disposer d'une fonction d'affichage de l'arbre : au minimum un affichage textuel un peu structuré, et idéalement une sortie graphique utilisant GraphViz par exemple.
4 points : 3 pour la première version de la fonction (2 pour la justesse du code, 1 pour la lisibilité), ou bien pour la seconde (2 + 1 aussi), 1 pour la fonction d'affichage.
V) Comparez les performances de votre code à celles du package R rpart. Pour votre information si vous êtes curieux, aller voir comment les choses sont codées dans ce package ou ailleurs ; lecture suggérée : https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf.
3 points : 1 si temps de calcul comparés, 1 si précisions comparées, 1 si commentaires pertinents.
L'essentiel au début est d'avoir un cycle complet "lecture de données / création d'arbre / élagage", sans entrer dans les détails. Vous pourrez ensuite complexifier votre code (ajout de critères, de types de données, traitement des valeurs manquantes). Gardez à l'esprit qu'il vaut mieux un code simple qui tourne bien plutôt qu'un code trop complexe qui plante.
Rédigez un rapport décrivant ce que vous avez fait, comment, pourquoi etc. Bref, une documentation un peu romancée de votre code.
Quant au code lui-même, expliquez-moi comment le faire tourner SVP.