Analyse de données CM 5 - Arbre de Décision v2.pptx

Cours rédigé par : Mathieu SEURIN et Nancy CHENDEB [email protected] [email protected] ANALYSE DE DONNÉE S PÔL E LÉONAR D DE VIN CI P Ô L E L É O N A R D D E V I N C I QU’EST CE QU’UN ARBRE DE DÉCISION? Un arbre de décision est un algorithme d'apprentissage supervisé. Les arbres de dé...

Cours rédigé par : Mathieu SEURIN et Nancy CHENDEB [email protected] [email protected] ANALYSE DE DONNÉE S PÔL E LÉONAR D DE VIN CI P Ô L E L É O N A R D D E V I N C I QU’EST CE QU’UN ARBRE DE DÉCISION? Un arbre de décision est un algorithme d'apprentissage supervisé. Les arbres de décision sont utilisés pour les tâches de classification et de régression, fournissant des modèles faciles à comprendre. Il a une structure nœuds internes arborescente hiérarchique de nœuds feuilles 2 un nœud racine (sommet) Température >15°? Branch e Fau x Vra i Pluie? Soleil? Fau x Vra i Pull Paraplu ie Fau x Pull Vra i T-shirt P Ô L E L É O N A R D D E V I N C I TERMINOLOGIE 3 Nœud racine/sommet : nœud initial au début d'un arbre de decision Nœuds de décision : Nœuds résultant du fractionnement (split) des nœuds racines. Ces nœuds sont des conditions intermédiaires Nœuds feuilles ou terminaux : nœuds où une division ultérieure n'est pas possible, indiquant la classification ou le résultat final. Branch or Sub tree (Sousarbre) : sous-section d'un arbre de décision. Nœud parent et enfants : Un nœud divisé en sous-nœuds est appelé nœud parent, et les sousnœuds qui en émergent sont appelés nœuds enfants (ou fils). Température >15°? Fau x Vra i Pluie? Soleil? Fau x Vra i Pull Paraplu ie Fau x Pull Vra i T-shirt PRÉDICTION AVEC UN ARBRE 𝑥 𝑖 =[12 ° , 𝑃𝑙𝑢𝑖𝑒 ] P Ô L E L É O N A R D D E V I N C I ( ) Les arbres de décision commence par la racine en haut, puis cette racine est divisée en plusieurs nœuds. Fau x C’est un ensemble d'instructions if-else Vra i Pluie? Si la condition est vraie, il passe au nœud suivant attaché à cette décision. Sinon, il passe au nœud suivant attaché à la décision contraire 5 Température >15°? Et ainsi de suite jusqu’à prendre décision… Soleil? Fau x Vra i Pull Paraplu ie Fau x Pull Vra i T-shirt P Ô L E L É O N A R D D E V I N C I LES ARBRES DE DÉCISION 6 - Principalement pour de la classification - Gère à la fois des caractéristiques catégorielles et numériques. - Modèle très expressif - Très bon sur données tabulaires - Peu interprétable (quand il y a peu de variables et peu de nœud) - Modèle à la base de beaucoup de modèles qui gagnent des compétitions kaggle (XGBoost, LightGBM) - Optimisation très différentes de ce qu’on a vu jusqu’à présent Comment construire un arbre de décision ? FRONTIÈRE DE DÉCISION Nœud = une décision P Ô L E L É O N A R D D E V I N C I jeu de données moment 9 Feuilles = assignation à une catégorie (classe majoritaire dans cette feuille) Problème à deux classes pour le ? L É O N A R D P Ô L E 1 0 𝑥1 =1 1er idée de coût : %de bonne classification au niveau des feuilles Arbre 1 : 3/10 + 3/10 = 60% d’accuracy True 3 D E V I N C I FONCTION DE COÛT Arbre 2 : 2/10 + 3/10 + 3/10 = 80% d’accuracy 2 2 3 𝑥1 =1 True Meilleur! Remarque : une fois dans une partie de l’arbre, les changement n’affecte pas la précision de l’autre branche Fals e Fals e 𝑥2 =1 True 0 2 2 Fals e 3 0 3 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 SUFFISANT ? P Ô L E L É O N A R D D E V I N C I Formalisation du cout : 10 2e arbre : 8/30 + 12/30 = 60% 60% de précision et arbre plus complexe mais, distribution plus « marquée » pour la feuille 1 Comment formaliser une distribution plus « marquée » ? 1 1 20 1er arbre : 60% de précision 𝑥1 =1 True 8 Fals e 2 12 8 P Ô L E L É O N A R D D E V I N C I UN PEU DE THÉORIE DE L’INFORMATION L’entropie est un concept qui revient dans beaucoup de domaine, et à pleins d’interprétations, pleins de manière d’être décrite (Mesure de dispersion, mesure du chaos etc…) Dans le cadre des statistiques, on va parler d’entropie d’une distribution notée. 5 5 1 7 3 0.88 10 0 0 Une entropie forte = proche de la loi uniforme Une entropie faible = distribution moins équilibrée Entropie nulle = Division pure L'entropie mesure l'impureté d'un nœud. L'impureté est le degré de hasard ; cela indique à quel point nos données sont aléatoires. 1 2 𝑥1 =1 𝑥2 =1 True V I N C I D E 100 L= 1 1 3 : un arbre avec Feuille, la fonction qui renvoie la distribution des s à la feuille où tombe - Et P Ô L E L É O N A R D FONCTION DE COÛT POUR UN ARBRE DE DÉCISION 100 25 75 L= 0.81 True Fals e 75 L= 0.81 25 90 Fals e 10 90 L= 0.47 10 V I N C I COÛT ET GAIN D’INFORMATION P Ô L E L É O N A R D D E Et 100 100 25 75 Loss1 = 1 Loss3 = 0.47 gain de ~0.19 75 25 90 10 Loss2 = 0.81 gain de ~0.34 On parle de Gain d’Information (diminution de l’entropy) 2 0 90 10 OPTIMISATION DE LA FONCTION DE COÛT P Ô L E L É O N A R D D E V I N C I Sur quelle caractéristique on fait le split ? 2 1 - Première idée : - Recherche greedy du meilleur split (on parcours toutes les features et on test tous les seuils) - Recherche à une profondeur de 1 - Algorithme : - Calcul du gain d’information d’ajouter un split pour chaque feature Sélectionner le split qui apporte le plus de gain Trier les données dans cette nouvelle feuille Répéter jusqu’à un critère d’arrêt (à définir) TROUVER LE MEILLEUR SPLIT def meilleur_features(arbre, dataset): information_gains = [] information_gains = gain_pour_feature(arbre, dataset, feat) meilleur_info_gain = information_gains[meilleur_feat] return meilleur_feat P Ô L E D E meilleur_feat = argmax(information_gains) L É O N A R D V I N C I for feat in range(#features): def gain_pour_feature(arbre, dataset, feat): return entropy(arbre, dataset) - split_entropy(arbre, dataset, feat) def split_entropy(arbre, dataset, feat): somme_entropy = 0 for splitted_distrib in SplitByFeaturesValues(arbre, S, feat): somme_entropy += entropy(splitted_distrib) * len(splitted_distrib) 2 2 P Ô L E L É O N A R D D E V I N C I MEILLEUR SPLIT SUR UNE FEATURE 2 3 Meilleur seuil QUAND ARRÊTER L’ALGO ? V I N C I - Critère sur le coût - Une feuille est pure - Quand un split ne change plus le coût (seuil à définir) Quand il n’y plus de features sur laquelle on peut faire un split (ça n’arrivera pas sur les valeurs continues) P Ô L E L É O N A R D D E - - - La feuille contient moins de K samples (avec K un seuil à définir) - - 2 4 Critère sur le nombre de sample au niveau de la feuille Critère de complexité du modèle - Nombre de nœud dépasse un seuil - La profondeur de l’arbre dépasse un seuil - Pénalité sur la complexité de l’arbre Un mix de tout ça ! TYPE DE DONNÉES DES FEATURES P Ô L E L É O N A R D D E V I N C I - Features numériques jusqu’à présent (trouver un seuil etc…) Mais les arbres peuvent aussi gérer : - Features booléenne Maths 5 12 o Pas de seuil à calculer pour le split - Catégorie : Numérique ou Non ! o Un enfant par catégorie possible o 1 vs le reste o 1 ensemble vs le reste 2 5 Option de l’étudiant Attention : scikit ne permet pas d’utiliser des variables catégorielles Sciences Ingé Info 10 20 17 Option de l’étudiant Maths / Info 15 Sciences Ingé 32 17 5 5 V I N C I D E L É O N A R D P Ô L E CONSIDÉRATION S PRATIQUES 2 6 LIKE,SHARE, FOLLOW ! @esilv_paris ESILV.FR Si on a énormément de features, trouver le meilleur seuil pour toutes peut être chronophage. (calcul de l’entropy pour chaque seuil) P Ô L E L É O N A R D D E V I N C I TROUVER LE MEILLEUR SPLIT POUR CHAQUE FEATURE Idée simple : Faire des intervalles (problème de sensibilité) Idée maligne et plus rapide : Plutôt que de regarder TOUS les seuils, prendre ceux endroits il y a une alternance des deux classes Idée encore plus simple : Prendre un seuil aléatoire (n’est en fait pas si mauvais si on sample un peu) On verra ça en TD! SORTIE MULTIPLE Changement pour les arbres : - Chaque feuille stocke k valeurs au lieu de 2 (nombre de classes) - Changement du critère pour tenir compte de k classes P Ô L E L É O N A R D D E V I N C I Pour le moment, seulement 2 classes, pas très général … - Possibilités de garder un seul seuil à chaque nœud - Tant que l’entropy diminue avec un split, c’est bon! 2 8 5 5 5 1 7 3 1 0.72 18 1 1 0.35 0 0 10 0 Pour le moment, on a vu : - Loss de classification - Entropy Le critère utilisé en pratique (notamment par sklearn) est l’index de Gini (pureté) : - avec la proba pour un objet d’être dans la classe i (plus efficace niveau calcul, avec tendances similaires) P Ô L E L É O N A R D D E V I N C I AUTRE FONCTION DE COÛT : GINI Uniforme : Score de 0.5 Plus piquée : Tend vers 0 2 9 5 5 0.5 7 3 0.42 1 9 0.18 10 0 0 L’arbre étant un modèle très expressif, le sur-apprentissage risque d’être encore plus présent P Ô L E L É O N A R D D E V I N C I LE SUR-APPRENTISSAGE 3 0 Deux méthodes de pruning : - Pre-pruning - Post-pruning P Ô L E L É O N A R D D E V I N C I PRUNING 3 1 Pruning (Élagage) : processus de suppression ou de réduction de nœuds spécifiques dans un arbre de décision pour éviter le surapprentissage et simplifier le modèle. L'élagage aide à améliorer les performances de l'arbre de décision en supprimant les nœuds ou sous-nœuds qui ne sont pas significatifs. Il supprime aussi les branches qui ont une très faible importance. Il existe principalement 2 façons de tailler : Pre-pruning (Pré-taillage) – nous pouvons arrêter la croissance de l’arbre plus tôt, ce qui signifie que nous pouvons élaguer/supprimer/couper un nœud s’il a peu d’importance lors de la croissance de l’arbre. Post-pruning (Post-élagage) – une fois que notre arbre a atteint sa profondeur , nous pouvons commencer à tailler les nœuds en fonction de leur importance. P Ô L E L É O N A R D D E V I N C I PRE-PRUNING 3 2 Choisir des paramètres pour limiter la croissance : (dans sklearn) max_depth : Limiter la profondeur max de l’arbre min_samples_split : Limiter le nombre de sample avant de faire un split min_samples_leaf : Après un split, il doit y avoir plus de min_samples_leaf dans chaque feuille P Ô L E L É O N A R D D E V I N C I POST-PRUNING 3 3 Post Pruning, réduire l’arbre a posteriori : ( la loss entropy/gini) avec le nombre de nœud terminaux et un paramètre de régularisation (comme pour la régression, il équilibre entre la loss d’entropy et la régularisation) Supprime ensuite les nœuds qui ne change que peu le score de classification. P Ô L E L É O N A R D D E V I N C I CLASSES DÉSÉQUILIBRÉES Quand les classes sont déséquilibrées : Problème dans le critère de classification (Ici un algo qui prédit y=0 obtient 90% de précision …) Durant l’optimisation, peut créer des (surtout quand les classes sont fortement déséquilibrées) Exemple : Prendre la classe majoritaire au sein d’une feuille risque => Risque de ne jamais prédire 1 Une solution : Mettre un poids plus important aux éléments de la classe minoritaire. (Pas spécifique aux arbres de décisions) 3 4 900 100 P Ô L E L É O N A R D D E V I N C I INTERPRÉTATION 3 5 - Les variables en haut de l’arbre ont le plus d’importance dans la décision - Permet parfois d’identifier des valeurs intéressantes pour les caractéristiques - Mais globalement, beaucoup de variables, arbres profond = Impossible à analyser 230 𝑥3 >2.23 156 90 376 199 227 97 4 403 167 89 P Ô L E L É O N A R D 𝑥10 =1 80 D E V I N C I RANDOM FOREST ET CALCUL EN PARALLÈLE 𝑥4