- 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
1 commentaires
Commentaires sur Hacker News
Mon arme secrète qui a très bien marché pour moi quand j’apprenais les classifieurs, c’était d’abord d’entraîner un bon classifieur linéaire
puis d’entraîner un arbre de décision en utilisant la sortie non seuillée de ce classifieur linéaire comme dimension de caractéristique supplémentaire, avant d’encapsuler le tout dans un système d’arbres boostés
De cette façon, le modèle linéaire compense les faiblesses de l’arbre de décision, et inversement l’arbre traite les cas où le modèle linéaire a du mal
On peut aussi envisager une rotation des données ou une normalisation des axes, mais dans la plupart des cas ce n’était pas nécessaire
En revanche, quand les caractéristiques sont très clairsemées, les arbres ont du mal à trouver des points de coupure
On ajoute des calculs à l’état brut pour construire un état observé (observed state), puis on entraîne dessus
Par exemple, dans le jeu Snake, on n’apprend pas seulement à partir des coordonnées du serpent, mais aussi de caractéristiques dérivées comme le nombre de chemins d’évasion
Si on ne nettoie pas les données et qu’on ne conçoit pas bien les caractéristiques, on obtient des résultats bien pires qu’avec des modèles boîte noire comme les réseaux de neurones
Ironiquement, les réseaux de neurones découvrent eux-mêmes ce type de caractéristiques latentes, mais il reste difficile d’interpréter pourquoi ils fonctionnent ainsi
Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), Hierarchical Mixture of Experts (HME), entre autres
Quand je travaillais au CERN vers 2010, le Boosted Decision Tree était le classifieur le plus populaire
C’était grâce à son bon équilibre entre explicabilité et pouvoir d’expression, et à l’époque on était culturellement réticent à utiliser des réseaux de neurones pour l’analyse en physique
Les temps ont bien changé depuis
En physique, comprendre les mécanismes causaux est plus important que simplement bien ajuster une courbe
C’est comme le système des épicycles de Ptolémée, qui reproduisait mieux le mouvement des astres sans pour autant en expliquer la cause
Dès qu’on augmente un peu la profondeur, ça devient une véritable jungle presque impossible à interpréter
C’est pareil pour les réseaux de neurones : on peut suivre les calculs internes, mais on ne sait toujours pas pourquoi ils prennent telle décision
Le même site propose aussi une explication de Random Forest → mlu-explain/random-forest
Fait intéressant : un réseau de neurones à 1 bit (single-bit neural network) est en pratique un arbre de décision
En théorie, on peut « compiler » la plupart des réseaux de neurones en chaînes de if-else, mais on ne sait pas encore clairement dans quels cas cela fonctionne bien
Cela ressemble surtout à une généralisation du concept, et une correspondance directe paraît difficile
Donc j’aimerais bien qu’on explique plus précisément dans quel sens c’est affirmé
Le plus grand avantage des arbres de décision, c’est la vitesse
Dans des environnements à très faible latence, j’ai essayé de remplacer un classifieur à base d’arbres par un petit réseau de neurones, mais même avec une précision un peu meilleure, le temps d’inférence (latency) du réseau était plus de 100 fois supérieur
En revanche, les arbres boostés ou baggés sont complexes, et les autres algorithmes de ML classiques sont eux aussi moins portables
Dans un manuel de ML (probablement ESL), les arbres de décision étaient décrits ainsi
« interprétables, rapides, efficaces sur des données variées, peu sensibles au scaling, avec peu de paramètres à régler… mais ils ne marchent pas bien »
Le bagging et le boosting permettent certes de compenser ce défaut, mais au prix d’une perte partielle de leurs avantages d’origine
J’aime vraiment les arbres de décision. C’est mon algorithme de ML classique préféré
J’en ai réalisé une implémentation parallèle purement fonctionnelle en GNU Guile → lien vers le code
Cela dit, Guile n’a rien de comparable à NumPy ou DataFrame, donc la représentation des données y est inefficace
Guile convient bien à la manipulation d’arbres, donc il est naturel pour implémenter un arbre de décision
Cela dit, ce serait plus efficace en le compilant en code machine
À ce sujet, Lush(https://lush.sourceforge.net/) et aiscm(https://wedesoft.github.io/aiscm/) valent peut-être aussi le détour
Même les décisions floues d’experts peuvent souvent être modélisées par un simple arbre de décision ou une chaîne de décision
Les experts eux-mêmes pensent souvent que leur raisonnement est complexe, alors qu’un arbre simple l’explique parfois mieux
Autrefois, la régression ou le clustering fondé sur la distance paraissaient plus sophistiqués, mais les arbres sont bien plus efficaces
Le chapitre 7 de Oxford Handbook of Expertise traite cela en détail
Au fond, un arbre de décision divise l’espace des possibles, un peu comme un kD-Tree, puis assigne une action à chaque région
La subtilité du jugement expert vient du raffinement des frontières, mais les arbres fournissent tout de même une assez bonne approximation
Le site était intéressant et la présentation réussie
En revanche, le contraste des couleurs de certains textes était trop faible, ce qui rendait la lecture difficile
L’accessibilité n’est pas seulement une question de handicap, c’est aussi un élément de base de la lisibilité
À l’époque actuelle du deep learning, les arbres de décision sont sous-estimés
Pourtant, ils restent interprétables, rapides et suffisamment pratiques
J’ai conçu un système de notation pour l’analyse de sites web fondé sur des arbres,
qui évalue des critères comme « y a-t-il une méta-description ? », « le site charge-t-il en moins de 3 secondes ? », ou « est-il adapté au mobile ? »
L’utilisateur comprend immédiatement pourquoi il a reçu cette note
Expliquer pourquoi un réseau de neurones a donné 73 points est impossible, alors qu’avec un arbre c’est facile
L’arbre diagnostique d’Esagil-kin-apli vers 1000 av. J.-C. en serait l’un des premiers exemples