Arbres de décision en Machine Learning : tout comprendre

L'arbre de décision est l'un des premiers algorithmes de Machine Learning que les Data Scientists apprennent au cours de leur formation. Il est utilisé pour représenter visuellement et explicitement les décisions et la prise de décision pour des problèmes de classification ainsi que pour des problèmes de régression. Il représente aussi l'élément de base de plusieurs modèles comme le Random Forest ou XGBoost.

Par conséquent, il est important de comprendre les concepts et les algorithmes qui se cachent derrière les arbres de décision. Dans cet article, nous allons détailler le principe de fonctionnement de l'arbre de décision et l'algorithme CART, responsable de sa construction à partir de données.

Principe de fonctionnement de l'arbre de décision

Tout d'abord, qu'est-ce qu'un arbre de décision ? Visuellement, cela ressemble à une structure descendante composée de noeuds : chaque noeud possède une condition qui amène à plusieurs réponses, ce qui dirige à un prochain noeud.

Lorsqu'un nœud donne la réponse, on dit que le nœud est terminal. Prenons l'arbre de décision suivant qui indique si l'on doit prendre un parapluie avec nous en fonction du temps.

Dans cet exemple, un jour ensoleillé donnera directement la réponse NON, alors qu'un jour nuageux donnera la réponse OUI ou NON en fonction de l'humidité.

Sur ce graphique, chaque nœud peut avoir aucune ou plusieurs possibilités: cela va dépendre de s'il est terminal ou non.

Un arbre de décision binaire est un arbre où chaque nœud non terminal possède exactement deux possibilités (gauche et droite). Prenons l'arbre suivant qui indique la mention obtenue à un examen pour un étudiant, et s'il a le droit à des rattrapages en cas de note inférieure à 10.

Plusieurs points sont à noter :

• Le premier noeud est appelé noeud racine et possède toujours exactement deux noeuds enfants.
• Chaque noeud non terminal possède toujours deux noeuds enfants.
• Les conditions de noeuds ne peuvent avoir que deux états : Vrai ou Faux.
• Le noeud enfant de gauche correspond toujours (dans cet arbre) à la situation où la condition est vérifiée (Vrai), et inversement le noeud enfant de droite correspond toujours à la situation où la condition n'est pas vérifiée (Faux).

Prenons un autre exemple où l'on souhaite estimer le prix d'un logement sur Airbnb en fonction du nombre de personnes (persons), du nombre de chambres (bedrooms) et de lits (beds). La variable réponse \(y\) correspond au prix du logement par nuit.

À lire aussi : découvrez notre formation MLOps

Un exemple d'arbre de décision binaire de profondeur 3 serait le suivant.

La première condition cherche à savoir s'il y a qu'une seule personne (nœud enfant gauche) ou plusieurs personnes (nœud enfant droite) dans le logement. Si une seule personne est présente, alors l'arbre de décision binaire s'intéresse ensuite à savoir s'il y a une chambre (nœud enfant droite) ou non (nœud enfant gauche). En revanche, si plusieurs personnes sont présentes, c'est d'abord un critère selon le nombre de lits qui est étudié.

Une fois l'arbre obtenu, il est très facile de calculer y (le prix du logement): il suffit de suivre la trajectoire dans l'arbre en fonction des conditions si elles sont vérifiées ou non.

Mais alors, comment un arbre de décision comme le précédent est automatiquement construit? Comment savoir le nombre des nœuds dans l'arbre? Comment définir les divisions successives ? Et surtout, comment décider à quel nœud faut-t-il arrêter? C'est justement l'algorithme CART qui va le faire.

L'algorithme CART

L'algorithme CART dont l'acronyme signifie « Classification And Regression Trees » à pour rôle de construire des arbres binaires de classification et de régression.

Il existe d'autres algorithmes pouvant construire des arbre de décision.

• L'algorithme ID3 (Iterative Dichotomiser 3) publié en 1986, ne permet que de créer des arbres de classification mais ne construit pas seulement des arbres binaires (un nœud peut avoir plus de deux enfants).
• L'algorithme C4.5 est basé sur ID3 mais ajoute quelques améliorations, notamment en se basant sur la mesure de l'entropie pour construire l'arbre de décision.

Il ne faut pas confondre l'arbre de décision avec son algorithme, car le premier et un modèle prédictif de Machine Learning alors que le deuxième est l'algorithme qui permet de le construire.

L'algorithme CART est très avantageux par rapport aux autres algorithmes, il est non seulement capable de gérer les arbres de régression mais aussi les arbres de classification en utilisant des métriques spécifiques dans chaque cas:

• Dans le cas d'arbre de régression la métrique utilisée est la MSE (Mean Squared Error).
• Dans le cas d'arbre de classification la métrique utilisée est l'impureté de Gini.

Arbre de régression

Commençons par les arbres de régression, qui vont chercher à prédire une quantité. Prenant cet exemple, en a une seule variable x et les observations suivent cette forme:

Chaque arbre va contenir des nœuds qui vont subdiviser l'espace sous forme de rectangles : en fonction de la trajectoire d'une décision dans l'arbre, on se dirigera dans tel ou tel rectangle.

À lire aussi : découvrez notre formation MLOps

On appellera le nombre \(\alpha\) un split, c'est-à-dire la valeur où l'on sépare en deux l'espace : d'un côté, les observations donc x est inférieur ou égal à \(\alpha\), et les autres lorsque x est supérieur à \(\alpha\). Cette valeur est déterminée par CART en utilisant la MSE, une métrique de mesure de performances. Il nous faut donc minimiser la MSE pour avoir le meilleur modèle.

La formule de la MSE est la suivante:

Ainsi, l'algorithme CART va tester plusieurs valeurs pour \(\alpha\) et calculer la MSE a chaque fois. Il finira par choisir la \(\alpha\) qui aura minimisé cette métrique au maximum.

Sur les 6 valeurs possibles pour \(\alpha\), la RMSE (MSE en racine carré) la plus petite est atteinte pour \(\alpha=0\) : ainsi, CART sélectionnera, pour premier nœud.

Arbre de classification

Dans cette situation, la prédiction n'est plus une quantité mais une classe.

Deux classes sont présentes : orange et bleu. L'arbre de décision va subdiviser le plan sous forme de rectangle, et l'objectif de CART est de construire l'arbre de sorte qu'il y ait le plus d'homogénéité possible dans chaque rectangle. C'est justement ici que l'impureté de Gini intervient.

L'impureté de Gini est le produit d'une probabilité \(p\) avec son inverse : elle vaut \(p(1−p)\). Elle permet de calculer très facilement l'homogénéité pour une classification binaire.

Notons \(p\) la proportion d'observations dont \(y\) vaut 1 .

• S'il n'y a que des points bleus (\(y\) vaut 0), alors \(p=0, 1−p=1\) et donc \(p(1−p)=0\) : il y a une parfaite homogénéité.
• S'il n'y a que des points oranges (\(y\) vaut 1), alors \(p=1, 1−p=0\) et donc \(p(1−p)=0\) : il y a là-aussi une parfaite homogénéité.
• À l'inverse, s'il y a autant de points bleus que de points oranges, alors il y a 50% de \(y\) à 0 et 50% de \(y\) à 1. Ainsi, \(p=0.5\) et \(1−p=0.5\) donc \(p(1−p)=0.25\) : il y a une pleine hétérogénéité.

On cherche à se rapprocher au maximum de 0 qui correspond à une situation où aucune couleur n'est mélangée. En appliquant successivement ce calcul sur chacun des nœuds, l'arbre de décision prend forme en fonction des différents \(\alpha\) choisis.

Le sur-apprentissage

Le risque de sur-apprentissage (créer un arbre avec une très grande profondeur) est très élevé pour les modèles non-paramétriques, dont fait partie l'arbre de décision.

Si l'arbre décide d'effectuer une subdivision sur un seul point, on est dans le cas de sur-apprentissage, car ce point est très éloigné de l'ensemble des autres points, c'est un point extrême. On obtiendra des résultats très différents de la réalité si ce type de points est pris considération par le modèle.

Pour détecter le sur-apprentissage, il faut diviser le jeu de données en deux parties.

• Une partie majoritaire appelée ensemble d'entrainement (training set) : c'est l'échantillon sur lequel notre modèle va s’entraîner.
• Une partie appelé ensemble de test (test set) : c'est un échantillon que notre modèle ne connaît pas.

Le deuxième ensemble va permettre d'évaluer la performance du modèle en calculant le pourcentage des prédictions correctes.

Pour limiter le sur-apprentissage, le choix d'hyper-paramètres est important. Il permettent au Data Scientist de contrôler son modèle et ils ne varient pas lors de l'entraînement.

Ces hyper-paramètres limiteront le sur-apprentissage dans les arbres de décision une fois optimisés.

• La profondeur maximale (max_depth).
• Le gain minimum de performances à obtenir lors du passage à une nouvelle profondeur (min_impurity_decrease).
• Le nombre d'observations minimal dans un nœud pour effectuer un split (min_samples_split) ou dont un nœud enfant doit avoir (min_samples_leaf).

Quand faut-il utiliser un arbre de décision ?

L'arbre de décision un outil qui a des applications couvrant plusieurs domaines différents. Il est facile à comprendre, même par des utilisateurs non experts, sa structure arborescente le rend lisible par un être humain, contrairement à d’autres approches où le modèle construit est une boîte noire.

• Cet algorithme est très intéressant pour extraire de l’information d’une source de données obscure. Il permet de trouver les propriétés qui apportent le plus d’information pour déterminer la classe de chaque objet. C'est pourquoi il est fréquemment adopté dans le cas de données peu ordonnées et claires.

• L'arbre de décision nécessite très peu de préparation des données, mais il est incapable de prédire des valeurs qui n'existent pas déjà dans son jeu de données. C'est pourquoi il ne peut pas être considéré comme le choix optimal dans le cas d'extrapolation de données et les données continues (régression).

À lire aussi : découvrez notre formation MLOps

En bref, l'arbre de décision est un outil élémentaire et indispensable de machine Learning qu'il vous faut maîtriser. Il est à la fois simple et lisible mais il constitue une méthode efficace de prise de décision.

Apprendre les arbres de décision

Les arbres de décisions sont des modèles de Machine Learning très utilisés par les Data Scientists. Ils sont utilisés dans de nombreuses situations qui nécessitent un parfait équilibre entre performance et explicabilité.

La formation Data Scientist de Blent permet de maîtriser tous les aspects techniques des arbres de décision, de leur optimisation et du choix judicieux des hyper-paramètres.

Cette formation permet également de maîtriser les modèles de Machine Learning les plus populaires avec les Random Forest ou XGBoost, et couvre également de nombreux sujets tels que l'interprétabilité et l'explicabilité des modèles, l'optimisation des hyper-paramètres et le déploiement de modèles sur des serveurs.