- Structure qui partitionne de façon répétée l’espace des caractéristiques pour classer les données, en choisissant à chaque étape la partition qui apporte le plus grand gain d’information
- Utilise l’entropie (Entropy) pour mesurer la pureté (purity) des données, puis calcule à partir de là le gain d’information (Information Gain)
- L’algorithme ID3 calcule la différence d’entropie entre le nœud parent et les nœuds enfants afin de trouver le meilleur point de partition, puis étend récursivement l’arbre
- On peut aussi utiliser l’impureté de Gini à la place de l’entropie ; les deux méthodes donnent en général des résultats similaires, mais diffèrent en efficacité de calcul
- Une partition excessive provoque du surapprentissage (overfitting) et de l’instabilité ; on peut atténuer cela avec le pruning ou une Random Forest
Concepts de base de l’arbre de décision
- L’arbre de décision partitionne les données de haut en bas et applique à chaque étape des règles conditionnelles pour séparer les données en régions bien distinctes
- Chaque partition est déterminée selon une caractéristique (feature) spécifique et une valeur seuil (cutoff value)
- L’objectif, en classification, est de créer des nœuds purs où les classes sont bien séparées
Définition et propriétés de l’entropie (Entropy)
- L’entropie est une mesure de l’incertitude de l’information, définie pour une probabilité (p_i) par (H = -\sum p_i \log_2(p_i))
- Propriétés principales
- Lorsqu’un seul événement a une probabilité de 1 et que tous les autres sont à 0, (H=0), c’est-à-dire qu’il n’y a aucune incertitude
- Lorsque tous les événements ont la même probabilité, l’entropie est maximale et représente l’état le plus impur
- Plus les probabilités tendent vers une répartition uniforme, plus l’entropie augmente
- Ainsi, un nœud pur a une entropie de 0, tandis qu’un nœud mixte présente une valeur d’entropie élevée
Gain d’information (Information Gain) et algorithme ID3
- Le gain d’information se calcule comme la différence d’entropie avant et après la partition, et représente l’efficacité de la partition des données
- Formule : (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
- Étapes de l’algorithme ID3
- Calculer l’entropie de chaque caractéristique
- Diviser le jeu de données selon différents critères de partition et calculer le gain d’information
- Sélectionner la partition dont le gain d’information est maximal pour créer le nœud de décision
- Créer un nœud feuille lorsqu’il n’est plus possible de partitionner
- Répéter récursivement l’opération sur tous les sous-ensembles, sauf si tous les éléments appartiennent déjà à la même classe
- Par exemple, la condition Diameter ≤ 0.45 a été choisie comme première partition car elle donnait le gain d’information maximal de 0.574
Impureté de Gini et mesure alternative
- L’impureté de Gini (Gini impurity) est une alternative à l’entropie, une autre manière de mesurer l’impureté de l’information
- Elle ne nécessite pas de calcul logarithmique, donc le calcul est plus rapide
- Sur des jeux de données déséquilibrés, l’entropie peut constituer un choix plus prudent
- Les deux méthodes produisent généralement des résultats similaires
Problèmes de surapprentissage et d’instabilité
- L’algorithme ID3 continue à partitionner pour minimiser l’entropie, si bien que l’arbre peut devenir excessivement profond
- Cela provoque du surapprentissage (overfitting) et dégrade la capacité de généralisation sur de nouvelles données
- Il existe aussi un problème d’instabilité (high variance), où de petites variations dans les données peuvent modifier fortement la structure de l’arbre
- Exemple : même en ajoutant un faible bruit gaussien à 5 % des données d’entraînement, on peut obtenir un arbre complètement différent
- Pour y remédier, on peut utiliser le pruning afin de limiter la profondeur de l’arbre, le nombre de feuilles, le nombre minimal d’échantillons, etc.
Extension vers la Random Forest
- Pour réduire l’instabilité d’un arbre de décision unique, on utilise une approche qui entraîne plusieurs arbres sur des échantillons de données différents puis combine leurs prédictions
- Cette approche est la Random Forest, qui offre une forte stabilité et de bonnes performances de généralisation
- Elle compense les limites de l’arbre de décision et est considérée comme l’un des algorithmes de machine learning les plus performants à ce jour
Conclusion et approfondissement
- L’arbre de décision est un modèle facile à interpréter, rapide à entraîner et simple à préparer en amont
- Cependant, pour résoudre les problèmes de surapprentissage et d’instabilité, il faut recourir au pruning ou à des techniques d’ensemble
- L’article ne traite pas des arbres de régression, de la préférence pour les end-cuts, ni des hyperparamètres, et recommande d’approfondir le sujet à l’aide de ressources complémentaires
Aucun commentaire pour le moment.