Decision Tree

Un arbre de décision est un modèle d'apprentissage supervisé qui prédit en posant une série de questions auxquelles on répond par oui ou non sur les caractéristiques d'une entrée, comme « Le revenu dépasse-t-il 50 000 $ ? », puis en suivant les réponses de la racine jusqu'à une feuille contenant la prédiction. Les arbres de classification prédisent une classe à chaque feuille, et les arbres de régression prédisent un nombre. Chaque prédiction est une chaîne de règles lisible, ce qui fait des arbres un outil courant d'IA explicable (XAI). Les arbres sont aussi les éléments de base des forêts aléatoires et des ensembles à boosting par gradient, qui surpassent encore l'apprentissage profond sur les jeux de données tabulaires de taille moyenne. L'algorithme CART de Breiman, Friedman, Olshen et Stone (1984), ainsi que ID3 (1986) et C4.5 (1993) de Ross Quinlan, ont établi les méthodes d'apprentissage des arbres à partir de données.

Construction d'un arbre de décision#

Les arbres se développent de haut en bas par partitionnement récursif. À chaque nœud, l'algorithme évalue des divisions candidates — chacune définie par une caractéristique et un seuil pour les caractéristiques numériques —, conserve celle qui rend les deux nœuds enfants les plus homogènes, puis répète la recherche dans chaque enfant. Les arbres de classification mesurent l'homogénéité à l'aide de l'impureté de Gini, soit la probabilité de mal étiqueter un échantillon choisi au hasard dans le nœud si les étiquettes étaient attribuées selon les proportions des classes du nœud, ou de l'entropie, dont la réduction est appelée gain d'information. Les arbres de régression choisissent la division qui réduit le plus l'erreur quadratique, et chacune de leurs feuilles prédit la moyenne des valeurs cibles des échantillons d'entraînement. La croissance s'arrête quand un nœud est pur, contient trop peu d'échantillons ou atteint une profondeur maximale. Chaque division ne regarde qu'une étape à l'avance : cette recherche gloutonne construit rapidement un bon arbre, alors que trouver l'arbre optimal garanti est un problème NP-difficile.

DecisionTreeClassifier de scikit-learn implémente une version optimisée de CART. Cet exemple fait croître un arbre de profondeur 2 sur le jeu de données des iris et affiche les règles qu'il a apprises :

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=42)

# A depth limit keeps the tree small enough to read and less prone to overfitting
clf = DecisionTreeClassifier(max_depth=2, random_state=42)
clf.fit(X_train, y_train)

print(export_text(clf, feature_names=iris.feature_names))
print(f"Test accuracy: {clf.score(X_test, y_test):.2f}")

L'arbre n'utilise que la longueur des pétales : les fleurs dont la longueur est inférieure ou égale à 2.45 cm sont des setosa (classe 0), et un deuxième seuil à 4.75 cm sépare les versicolor (classe 1) des virginica (classe 2). Ces règles classent correctement 97 % des fleurs mises de côté.

Chaque division correspond à une règle fondée sur un seuil de ce type, qu’un arbre apprend à partir des données et qu’une personne peut aussi définir manuellement. Le moniteur d’entraînement AIGym d’Ultralytics définit manuellement deux règles de ce type pour les sorties du modèle YOLO26 d’estimation de pose : il étiquette une image « en haut » lorsque l’angle du coude, calculé à partir des points clés de l’épaule, du coude et du poignet, dépasse 145° et « en bas » lorsqu’il passe sous 90°, puis compte une répétition à chaque passage de « en haut » à « en bas ».

Surapprentissage et élagage#

Un arbre développé jusqu'à ce que chaque feuille soit pure mémorise ses données d'entraînement, bruit compris : c'est un cas classique de surapprentissage. Le pré-élagage arrête la croissance prématurément en fixant des limites, comme une profondeur maximale ou un nombre minimal d'échantillons par feuille. Le post-élagage fait croître l'arbre complet, puis supprime les branches qui apportent peu ; scikit-learn implémente l'élagage par complexité-coût minimale au moyen du paramètre ccp_alpha, les valeurs les plus élevées entraînant un élagage plus important. Ces deux types de limites sont des hyperparamètres choisis par validation croisée.

Même élagué, un arbre présente une forte variance : une petite modification des données d'entraînement peut changer la division à la racine et, par conséquent, toutes les divisions suivantes. Les ensembles répondent à ce problème en combinant de nombreux arbres : soit en calculant la moyenne d'arbres entraînés sur des échantillons bootstrap, comme le font les forêts aléatoires, soit en ajoutant les arbres un par un pour corriger les erreurs des précédents, comme le fait le boosting par gradient.

Points forts et limites#

Les arbres gèrent à la fois les caractéristiques numériques et catégorielles, ne nécessitent aucune normalisation des caractéristiques, capturent les interactions et les effets non linéaires sans ingénierie des caractéristiques manuelle, et prédisent au moyen de quelques comparaisons. Leurs divisions sont alignées sur les axes : une frontière diagonale comme « les dépenses dépassent le revenu » devient donc un escalier composé de nombreuses divisions, à moins d'ajouter une caractéristique de ratio. Les arbres de régression prédisent une valeur constante dans chaque feuille ; contrairement à la régression linéaire, ils ne peuvent donc pas extrapoler une tendance au-delà de la plage des données d'entraînement.

Applications#

• Décisions de crédit : Les prêteurs utilisent des arbres peu profonds et des barèmes de score fondés sur des arbres pour classer les demandes selon le risque. Chaque décision renvoie aux seuils de revenu, d'historique de crédit et d'endettement qui l'ont produite.
• Triage clinique : Les règles de décision clinique présentées sous forme d'arbres orientent les patients en fonction de leurs signes vitaux et symptômes, par exemple pour déterminer s'ils ont besoin d'une imagerie immédiate.
• Attrition de la clientèle : Les arbres répartissent les clients selon leur utilisation, leur ancienneté et leur historique de support en segments présentant un risque d'annulation élevé ou faible. Les parcours décrivent clairement chaque segment.
• Maintenance prédictive : Les arbres à boosting par gradient utilisant les caractéristiques de vibration, de température et de durée de fonctionnement évaluent quelles machines risquent de tomber en panne avant leur prochaine intervention.

Arbres de décision et notions apparentées#

• Forêts aléatoires : Elles calculent la moyenne de nombreux arbres entraînés sur des échantillons bootstrap et des sous-ensembles aléatoires de caractéristiques, au prix d'une moindre lisibilité qu'un arbre unique, mais avec une meilleure exactitude et une plus grande stabilité.
• XGBoost, LightGBM et CatBoost : Des bibliothèques de boosting par gradient qui ajoutent les arbres un par un pour corriger les erreurs des précédents. LightGBM est conçu pour accélérer le traitement des grands jeux de données, et CatBoost pour gérer nativement les caractéristiques catégorielles.
• Apprentissage profond : Les réseaux de neurones apprennent les caractéristiques à partir d'images, d'audio et de texte bruts, tandis que les arbres se divisent en fonction de caractéristiques déjà présentes dans les colonnes d'un tableau.
• Arbres d'analyse décisionnelle : En recherche opérationnelle et en planification d'entreprise, un arbre de décision est aussi un diagramme dessiné à la main par un analyste, avec des nœuds de décision, des nœuds aléatoires et des gains, pour comparer les options en fonction de leur valeur espérée. Il est construit à partir de probabilités estimées plutôt qu'appris sur des données d'entraînement.