<jupyter_start><jupyter_text>TP Arbre des DécisionModifié à partir d'un des TPs rendus.  Code<jupyter_code>import importlib as il
import src.class_Noeud
import src.class_ArbreDecision
import src.code_utils
import src.test_utils as t<jupyter_output><empty_output><jupyter_text>Classe NoeudUn arbre (binaire dans le cas du TP) est composé de noeuds. On distingue deux types de noeuds : - les noeuds internes, qui ont des enfants - les feuilles, qui n'en ont pasChaque noeud contient une référence vers le jeu de données ainsi que l'index de la colonne contenant le label.Il contient également des données qui le définissent : - les indices présents à ce niveau de l'arbre - la classe majoritaire parmi ces indices - l'erreur réalisée à supposer qu'on ne descende pas plus basSi le noeud n'est pas une feuille, alors on stocke aussi des informations relatives au meilleur split trouvé : - l'index de l'attribut (parmi les colonnes) - le seuil (numérique ou ensembliste) - la valeur critique du paramètre alpha (cf. élagage) - des références aux sous-arbres gauche et droit (pointeurs sur racines)Cette structure "fractale" permet d'écrire naturellement des fonctions récursives. Elle évite le surcoût mémoire engendré par l'utilisation d'un tableau (efficace seulement pour les arbres binaires quasi-complets). En revanche le parcours des noeuds est plus complexe qu'avec un tableau.<jupyter_code>il.reload(src.class_Noeud); from src.class_Noeud import Noeud<jupyter_output><empty_output><jupyter_text>Classe ArbreDecisionUn arbre est composé d'un certain nombre de noeuds, organisés hiérarchiquement depuis un noeud racine. Ce dernier permettant de parcourir tout l'arbre, c'est le seul point d'entrée présent ici dans les champs de classe.Afin d'alléger les appels de fonctions, on passe également le jeu de données (par référence) ainsi que l'index de la colonne contenant le label.Le critère de split est stocké à ce niveau car il définit la structure de l'arbre.<jupyter_code>il.reload(src.class_ArbreDecision); from src.class_ArbreDecision import ArbreDecision<jupyter_output><empty_output><jupyter_text>Déroulement de l'algorithme Le constructeur d'ArbreDecision prend trois paramètres : un jeu de données au format pandas.DataFrame, l'index de la colonne contenant le label (de n'importe quel type), et le critère de split : 'g' pour Gini, 'e' pour entropy ou 'm' pour "misclassification error".Le type des données (hors label) est déterminé à la lecture des données : s'il y a quelque chose qui n'est pas un nombre, tout est considéré comme chaîne de caractères. Sinon, on considère qu'un attribut est entier s'il ne prend que des valeurs entières, et flottant dans le cas contraire. L'utilisateur peut également spécifier les types en passant en dernier paramètre un dictionnaire index $\rightarrow$ type ("str", "float" ou "int").Une fois créé, un arbre ne contient qu'un seul noeud vide : sa racine. Un noeud contient toujours une référence au jeu de données complet, un ensemble d'indices correspondant aux individus à ce niveau de l'arbre (donc $[1, n]$ à la racine), et l'index du label. L'apprentissage via la fonction ArbreDecision.learn() consiste à 1. déterminer le meilleur split à la racine 2. l'appliquer pour obtenir deux noeuds enfants 3. déterminer la meilleure division dans chaque noeud enfant 4. l'appliquer dans chaque noeud enfant, etc (récursivement).Voir Noeud.learn(). Les deux fonctions principales sont donc Noeud.get_best_split() et Noeud.do_split(). La première prend en argument un critère et cherche pour chaque attribut à maximiser le gain d'information (= minimiser le critère qui lui mesure le manque d'information). Elle retourne un seuil ainsi qu'un numéro d'attribut, pris au hasard parmi les meilleures coupes trouvées. Noeud.do_split() retourne deux sous-ensembles d'indices correspondants au seuil choisi. Une fois de retour dans la fonction d'apprentissage, on crée alors deux noeuds enfants avec ces sous-ensembles, puis on cherche à les diviser, etc (procédure récursive).La recherche de la meilleure coupure s'effectue naturellement pour les variables numériques en triant d'abord la colonne correspondante, donnant a priori $n-1$ splits potentiels (= les inter-valeurs). Attention il peut y en avoir moins en présence de doublons. Concernant les variables symboliques, on cherche d'abord la modalité séparant le mieux les données, puis on cherche à y adjoindre une autre modalité, etc, tout pendant que la valeur du critère diminue. Exemple : (a/1 a/1 b/1 b/1 c/2 c/2 ...) avec label dans $\{1, 2\}$, et attribut à quatre modalités $\{a, b, c, d\}$. L'algorithme évalue d'abord le split $a$ vs. $\{b, c, d\}$, puis essaye de "fusionner" $a$ et $b$ : cela mène en effet à un critère plus bas.  Gestion des valeurs manquantes On tient compte des valeurs manquantes à trois niveaux : - dans la fonction Noeud.get_best_split() - dans la fonction Noeud.do_split() - pour la prédiction (Noeud.predict())Lors de la recherche de la meilleure division, on ignore simplement les lignes auxquelles il manque la valeur d'attribut courante. Ces lignes sont dupliquées à gauche et à droite du seuil, afin de pénaliser la valeur du critère. En effet une colonne avec beaucoup de valeurs manquantes ne devrait pas être considérée $-$ idéalement l'utilisateur l'aura supprimée en amont.Au moment d'effectuer la division, une ligne avec attribut manquant est envoyée d'un côté déterminé par le tirage d'une variable aléatoire de Bernoulli. Le paramètre de cette loi est la proportion d'individus "à gauche" ayant le même label que celle à l'attribut manquant. C'est une manière assez simpliste de gérer les valeurs manquantes. rpart utilise plutôt les "surrogate splits" : voir par exemple vers le bas de [cette page](http://www.learnbymarketing.com/methods/classification-and-regression-decision-trees-explained/)Enfin, au niveau de la fonction de prédiction on retourne simplement un label au hasard parmi les classes majoritaires à ce stade.  Élagage Une première idée d'application de la formule du cours (slides2, page 26) consiste à remonter l'arbre depuis les feuilles, en mettant à jour l'erreur globale + alpha x nombre de feuilles. On arrêterait de fusionner quand ce terme commence à croître. En plus de devoir spécifier une valeur de alpha, cette approche n'est pas très satisfaisante car elle nécessite d'effectuer un parcours "bottom-up" de l'arbre (il faudrait ajouter des pointeurs sur le noeud parent).En réfléchissant un peu à la formule, on en vient ensuite à une meilleure idée : après une fusion dans le cas d'un arbre binaire, on a enlevé exactement une feuille. Ce regroupement sera donc validé uniquement si alpha est inférieur ou égal à l'augmentation de l'erreur (en pourcentages). Le paramètre alpha critique d'un noeud correspond ainsi simplement à la différence entre son erreur et la somme de celles de ses enfants. Attention, cela est valable si l'on parcourt toujours l'arbre de bas en haut. Afin de rendre l'approche valide aussi dans l'autre sens, on modifie les valeurs alpha à chaque noeud $n$ : $\alpha(n) \leftarrow \max(\alpha(n), \{ \alpha(m), m \texttt{ descendant de } n \})$ (voir la fonction adjust_alpha()).Note : on peut exprimer alpha soit en absolu (équivaut alors à un nombre d'erreurs), soit en relatif (après division par $n$ : taux d'erreur). Cette dernière option est a priori préférable car on s'affranchit de la taille du jeu de données.Finalement, il suffit de s'arrêter lorsque l'alpha courant est inférieur strict à celui fournit en paramètre, que ce soit pour la prédiction ou pour l'affichage. L'arbre entier reste en mémoire, et on n'a pas besoin de créer d'autres arbres.  Tests<jupyter_code>import numpy as np
import pandas as pd
# Quelques fonctions utiles
il.reload(t); pass<jupyter_output><empty_output><jupyter_text>Quelques mots sur rpartLa librairie R "rpart" que nous avons utilisée en TP réalise beaucoup plus de tâches que le code ci-dessus. Pour une comparaison juste, l'argument "control" sera fixé à la liste suivante :```rlist(  minsplit = 2,  minbucket = 1,  maxcompete = 0,  maxsurrogate = 0,  usesurrogate = 0,  xval = 0,  surrogatestyle = 0,  maxdepth = 30) avec cp = alpha (cf. code ci-dessus)```Voir ?rpart.control pour les détails.En l'état, ce code Python est de toutes façons beaucoup plus lent pour deux raisons : - il n'est pas compilé - il n'est pas écrit efficacementC'est pourquoi les timings devraient être calculés sur une réécriture en C $-$ à suivre.D'une manière générale les valeurs critiques trouvées pour alpha diffèrent entre mon code et rpart $-$ le calcul doit y être un peu différent. Le nombre de valeurs critiques est cependant à peu près le même, ce qui est tout de même rassurant, ainsi que l'ordre de grandeur des erreurs.  Données iris<jupyter_code>iris = pd.read_csv("data/iris.data")<jupyter_output><empty_output><jupyter_text>L'arbre est en général très simple (trois feuilles) pour un choix de alpha entre 0.01 et 0.1.<jupyter_code>a = ArbreDecision(iris, 4, 'g') #indice de Gini
a.learn()
a.plot(0.05)
t.eval_predict(a, iris, 0.05) #erreur de l'ordre de 4%<jupyter_output><empty_output><jupyter_text>Ces données sont tellement simples que l'erreur est souvent minimale pour l'arbre non élagué.<jupyter_code>t.best_alpha(iris, 0.4, 4, 'g')<jupyter_output><empty_output><jupyter_text>Données tic-tac-toe<jupyter_code>ttt = pd.read_csv("data/tic-tac-toe.data")<jupyter_output><empty_output><jupyter_text>L'arbre est déjà plus complexe (et le temps d'apprentissage plus élevé).<jupyter_code>a = ArbreDecision(ttt, 9, 'e')
a.learn()
a.plot(0.02)
t.eval_predict(a, ttt, 0.01)
t.best_alpha(ttt, 0.4, 9, 'e')<jupyter_output><empty_output><jupyter_text>Données "vais-je courir ?"<jupyter_code>courir = pd.read_csv("data/courir.data")
courir
a = ArbreDecision(courir, 4, 'g')
a.learn()
a.plot()<jupyter_output><empty_output><jupyter_text>Conforme à l'arbre construit pendant l'examen.<jupyter_code>a.get_alphas()<jupyter_output><empty_output><jupyter_text>Cet exemple (certes très artificiel) est intéressant car il montre les limites de l'élagage automatique. En effet fusionner les dernières feuilles augmente l'erreur d'exactement 1/10, et fusionner les feuilles résultantes l'augmente aussi de 0.1. On a donc seulement deux valeurs critiques de alpha : une qui élague tout sauf le split à la racine, et l'autre qui ne garde que la racine. Cependant, il semble intéressant de garder aussi le niveau intermédiaire "retard oui / non" ; mais sans intervention humaine c'est impossible à deviner.<jupyter_code># Essayons avec un critère de split (en général) moins bon
a = ArbreDecision(courir, 4, 'm')
a.learn()
a.plot()<jupyter_output><empty_output><jupyter_text>Le second split s'effectue toujours au seuil 25.25. Cela paraît étrange, car le calcul manuel de la valeur de split donne - $3/7 \times (1 - 2/3) = 1/7$ au seuil 19 - $6/7 \times (1 - 5/6) = 1/7$ au seuil 25.25Alors alors, où est le bug ? En fait "il n'y en a pas" (sur ce point précis !). Une erreur d'arrondi favorise un split plutôt que l'autre :```python>>> (3/7) * (1 - 2/3)0.14285714285714288>>> (6/7) * (1 - 5/6)0.14285714285714282```Anecdotique puisque ce critère considérant les situations "non vs. non + 5 x oui" et "4 x oui vs. oui + 2 x non" équivalentes, il vaut mieux l'oublier. Intéressant en revanche pour des raisons numériques : les problèmes d'arrondis sont en effet fréquents.  Données adult<jupyter_code>adult = pd.read_csv("data/adult.data", na_values=['?',''])
a = ArbreDecision(adult, 11, 'g')
a.learn()
a.affiche(0.005)
t.best_alpha(adult, 0.4, 11, 'g')
adult_test = pd.read_csv("data/adult.test", na_values=['?',''])
ap = a.predict(adult_test, 0.000358294518093873)
np.mean(ap != adult_test.iloc[:,11])<jupyter_output><empty_output><jupyter_text>On trouve un taux d'erreur acceptable (16% au lieu de 14% dans mon ancien rapport, mais j'avais fait des réglages difficilement reproductibles et encore moins automatisables). Le temps de calcul est en revanche rédhibitoire : quelques minutes au lieu de quelques secondes.  Données letter<jupyter_code>letter = pd.read_csv("data/letter-recognition.data")
a = ArbreDecision(letter, 0, 'e')
a.learn()
a.get_alphas()
a.plot(0.01)
t.eval_predict(a, letter, 0.01)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07888082225303858, 'fraction_numerical': 0.014193653642222042, 'mean_word_length': 5.23284189120488, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '550304', 'license': '0BSD', 'n_tokens_mistral': 4241, 'n_tokens_neox': 4186, 'n_words': 1626, 'path': 'TP.ipynb', 'repo_name': 'yagu0/TP_arbre', 'size': '12259'}