Arbres de décision

Objectif

L'arbre de décision dessine la logique d'une décision unique et répétable: l'ensemble des règles qui, à partir d'un jeu d'éléments de données, sélectionnent une issue parmi plusieurs. Son intérêt propre est spatial. Là où une table aligne les règles en lignes, l'arbre les déploie en parcours, de sorte qu'une partie prenante suit une suite de conditions jusqu'à une issue sans avoir à lire une grille. Cette disposition rend lisible ce qu'une table garde implicite: les règles qui partagent leurs premières conditions partagent les mêmes nœuds hauts.

C'est ce qui explique la force que le BABOK reconnaît à la technique, la segmentation. Router une demande, un dossier ou un client le long d'un chemin jusqu'au segment ou à l'action qui lui revient est précisément ce qu'un arbre montre bien. La décision reste atomique, une seule issue est retenue à chaque passage, mais le chemin qui y mène reste lisible par quelqu'un qui ne connaît pas la notation.

Le livrable est l'arbre lui-même: une racine, des nœuds de décision qui testent chacun un élément de données, des branches qui portent les conditions et des feuilles qui portent les issues, avec la garantie que tout jeu d'entrées valide aboutit à une feuille et une seule. Une variante répond à un autre objectif, comparer des options dont les conséquences sont incertaines. Elle ajoute des nœuds de hasard, une probabilité par branche sortante et un gain à chaque feuille, puis retient l'option dont la valeur attendue est la plus élevée. Les deux partagent la forme en arbre, elles ne répondent pas à la même question, et les confondre est le premier piège de la technique.

Usage

Quand l'utiliser

• Règles partageant leurs premières conditions: les nœuds hauts rendent la structure commune visible.
• Segmentation d'une clientèle ou d'un flux de dossiers: router chaque entrée jusqu'à son segment ou son action.
• Petit ou moyen jeu de règles à communiquer: un parcours se suit plus vite qu'une grille dense.
• Décision à conditions séquentielles et dépendantes: quand l'ordre d'évaluation porte lui-même du sens, l'arbre le montre.
• Choix entre options sous incertitude: la variante à nœuds de hasard compare les valeurs attendues.

Quand ne pas l'utiliser

• Nombreuses conditions indépendantes sur des données communes: l'arbre explose et duplique ses sous-arbres, préférer une table de décision.
• Décision complexe se décomposant en sous-décisions: un arbre unique masque les dépendances, cartographier d'abord avec un diagramme des exigences de décision.
• Logique à apprendre depuis des données historiques: c'est de la classification statistique, elle relève du data mining.

Description

Les éléments de l'arbre

Quatre éléments composent l'arbre, et chacun porte une contrainte qu'il faut tenir sous peine de produire un arbre qui ment. Les nœuds de décision sont les nœuds internes; chacun teste un seul élément de données, une variable de condition comme le montant d'un prêt, un âge ou un taux d'endettement. Leur ordre compte: l'élément le plus discriminant se place près de la racine, parce que c'est lui qui sépare le plus tôt les cas et qui garde l'arbre petit. Les branches sortant d'un nœud portent chacune une condition sur l'élément testé, et les branches d'un même nœud doivent être mutuellement exclusives et exhaustives: aucune valeur ne tombe dans deux branches, aucune valeur ne tombe hors de toutes. Les feuilles portent les issues, une par chemin, et l'ensemble des feuilles doit rester lui aussi mutuellement exclusif et collectivement exhaustif, de sorte que tout jeu d'entrées valide atterrisse sur exactement une feuille. Les niveaux, enfin, correspondent par convention à un élément de données chacun: un niveau interroge le montant, le suivant le taux d'endettement et ainsi de suite. Le BABOK pose ainsi la propriété qui fait tenir l'ensemble: chaque chemin complet, de la racine à la feuille, est une règle et une seule.

Construire l'arbre

Le standard donne les éléments plutôt qu'une procédure numérotée. La pratique les ordonne en séquence.

1. Nommer la décision et son jeu d'issues
   Écrire la décision en un énoncé sans ambiguïté et lister les actions possibles, qui seront les feuilles.
2. Lister les éléments de données
   Ceux dont la décision dépend, ceux-là seuls qui font basculer l'issue.
3. Ordonner les éléments
   Placer près de la racine l'élément le plus discriminant, ou celui que le plus de règles partagent, pour que la structure commune remonte en haut de l'arbre.
4. Dessiner l'arbre
   Un élément de données par niveau, une branche par valeur de condition, jusqu'à ce que chaque chemin atteigne une issue.
5. Valider par trois contrôles
   L'exhaustivité, chaque chemin finit sur une feuille et aucune valeur n'est laissée sans branche; la cohérence, aucun jeu d'entrées ne satisfait deux chemins menant à des issues différentes; l'exclusivité, les branches de chaque nœud ne se recouvrent pas.

La variante d'analyse de décision

La même forme sert un objectif distinct lorsque les conséquences d'un choix sont incertaines, et la notation se dote alors de deux formes de nœuds qu'il faut distinguer. Un nœud de décision, dessiné en carré, est un point où l'analyste choisit entre des options. Un nœud de hasard, dessiné en cercle, est un point où l'issue échappe au choix: chaque branche sortante porte une probabilité, et les probabilités d'un même nœud de hasard somment à 1. Chaque feuille porte un gain, en général une valeur en francs. L'arbre s'évalue par remontée, des feuilles vers la racine: à chaque nœud de hasard on calcule la valeur attendue, la somme des probabilités multipliées par les gains, et à chaque nœud de décision on retient la branche dont la valeur attendue est la meilleure. C'est l'analyse par valeur monétaire attendue, que le PMI place parmi les outils d'analyse quantitative des risques. Étiqueter les deux formes de nœuds porte le sens: une probabilité posée sur une branche que l'analyste contrôle n'a aucun sens, et c'est la distinction du carré et du cercle qui l'interdit.

Arbre, table et diagramme des exigences

Trois techniques de la modélisation des décisions se ressemblent assez pour qu'on les confonde, et la frontière décide du bon choix. La table de décision porte la même logique de règles d'une décision atomique, en forme tabulaire: une ligne par règle, une colonne par condition ou par action. Même logique, autre forme. La table l'emporte quand les règles sont nombreuses et indépendantes et qu'on veut contrôler l'exhaustivité et l'absence de contradiction; l'arbre l'emporte quand les règles partagent des conditions et qu'on veut montrer le parcours et la segmentation. Le diagramme des exigences de décision est autre chose: la carte de ce qui alimente quoi. Il montre comment une décision complexe se décompose en sous-décisions, en données d'entrée, en modèles de connaissances métier et en sources de connaissances, reliés en réseau. Un seul nœud de ce diagramme, un modèle de connaissances, peut lui-même contenir un arbre ou une table. Table et arbre sont deux dessins des règles d'une décision; le diagramme des exigences est le dessin de la façon dont plusieurs décisions se connectent.

Les pièges

Explosion combinatoire

Chaque nouvel élément de données peut multiplier le nombre de feuilles, et l'arbre devient illisible. Un arbre qui a débordé de la page indique qu'il faut passer à une table.

Sous-arbres dupliqués ou déséquilibrés

La même sous-décision qui reparaît sous plusieurs branches est un signe fort que la logique est en réalité tabulaire ou qu'une sous-décision partagée devrait être extraite dans un diagramme des exigences.

Incomplétude

Une branche manquante, une valeur non prévue, laisse une entrée sans issue: la décision échoue en silence ou passe à travers sans que personne l'ait décidé.

Règles qui se chevauchent ou se contredisent

Deux chemins qu'une même entrée réelle satisfait donnent deux issues. L'arbre le masque moins qu'une table, mais des conditions imbriquées peuvent encore le cacher.

Probabilités masquées ou confondues

Mêler l'arbre de règles et l'arbre de valeur attendue sans dire lequel on dessine trompe le lecteur. Un arbre de règles ne porte aucune probabilité; les branches d'un nœud de hasard d'un arbre de valeur attendue somment à 1. Étiqueter les formes de nœuds évite la confusion.

Surajustement à la main

Ajouter une branche spéciale pour chaque cas particulier vu le trimestre passé finit par graver des anecdotes plutôt qu'une politique. Un cas particulier appartient d'ordinaire à une règle d'exception.

Mauvais choix de racine

Un ordre mal choisi des éléments de données rend le même arbre plusieurs fois plus grand et plus difficile à lire qu'il n'a besoin de l'être.

Considérations IA

Une difficulté propre à cette technique tient à ce qu'une autre discipline lui a emprunté sa forme et son nom. L'arbre de décision d'un analyste métier est un encodage construit et gouverné de règles connues. L'arbre de décision de l'apprentissage automatique (CART, ID3, C4.5 ou un ensemble comme la forêt aléatoire ou le gradient boosting) est induit de données historiques: un algorithme choisit les coupures qui maximisent le gain d'information ou minimisent l'impureté, afin de prédire une issue. Même dessin, épistémologie inverse, l'un écrit depuis la politique, l'autre inféré depuis les données.

L'assistance sert trois travaux. Elle produit un premier jet d'arbre à partir d'un référentiel de règles documenté ou d'une table de décision et convertit l'un en l'autre. Elle effectue une vérification mécanique: repérer un chemin sans feuille, une branche inatteignable, deux règles qui se recouvrent. Elle propose un ordre des coupures tiré de décisions passées, comme point de départ que l'analyste gouverne ensuite. Ce sont des gains de mise en forme et de contrôle. Le jugement reste à l'analyste.

Trois limites sont fermes. Un arbre induit ne doit jamais devenir en silence la logique de décision gouvernée: dans un cadre suisse réglementé, un octroi de crédit sous la loi sur le crédit à la consommation, une règle d'éligibilité à une assurance, la décision doit être explicable et défendable au regard de la politique et de la loi. Les biais de la donnée d'entraînement et les variables mandataires cachées entrent invisiblement dans un arbre induit, là où un jeu de règles gouverné est auditable. Enfin, les probabilités d'un arbre de valeur attendue sont un jugement sur le monde: un modèle peut les proposer, une partie prenante les possède.

Exemples

Router une demande de crédit à la consommation

Une décision d'octroi de crédit à la consommation (LCC) est routée sur deux éléments de données, le montant demandé et le taux d'endettement du demandeur. L'arbre porte quatre règles, une par chemin, et les deux règles sous chaque branche du montant partagent leur première condition, ce nœud commun n'étant dessiné qu'une seule fois: c'est le cas d'école des règles qui partagent une condition, que le dessin montre mieux qu'une grille. Les quatre mêmes règles s'écriraient tout aussi bien en table de décision; l'arbre est retenu parce que le parcours donne à un guichet la suite d'une demande d'un seul regard.

Décider de soumissionner sous incertitude

Une PME évalue s'il faut déposer une offre sur une soumission publique. La décision, un nœud carré, oppose soumissionner et ne pas soumissionner. Soumissionner mène à un nœud de hasard, un cercle: le marché est remporté avec une probabilité de 0.35 pour un gain de CHF 52'000 (marge nette du contrat de CHF 60'000 moins CHF 8'000 de coût de soumission), perdu avec une probabilité de 0.65 pour une perte de CHF 8'000, le coût de soumission engagé en vain. La valeur attendue de soumissionner vaut 0.35 × 52'000 + 0.65 × (−8'000), soit CHF 13'000, contre CHF 0 pour ne pas soumissionner: on soumissionne. Le seul point qu'un lecteur pourrait manquer est que la conclusion tient à la probabilité: en deçà d'un seuil de rentabilité d'environ 0.13, la valeur attendue passe sous zéro et la décision s'inverse.

Visualisations

L'arbre de règles se dessine en nœuds rectangulaires reliés par des branches étiquetées, lues de la racine, à gauche ou en haut, vers les feuilles. L'éventail des branches à un nœud est l'endroit où se lit l'exclusivité: chaque branche sortante est une valeur de l'élément testé, et ensemble elles doivent couvrir toutes les valeurs. Le sous-arbre partagé se lit comme un ancêtre commun, un nœud proche de la racine se trouvant sur le chemin de chaque règle en dessous de lui, ce qu'une table ne montre pas d'un coup d'œil.

La variante d'analyse de décision emploie deux formes distinctes: un carré pour un nœud que l'analyste contrôle, un cercle pour un nœud que le monde contrôle. Perdre la distinction, c'est perdre le sens, puisqu'une probabilité sur une branche que l'analyste contrôle serait absurde. Le dessin porte la nature du nœud; un tableau des mêmes chiffres ne la porte pas.

Au-delà d'une poignée d'éléments de données, l'arbre déborde de la page et duplique ses sous-arbres. C'est le signal de changer de représentation: la logique qui a fait exploser l'arbre est celle qu'une table condense, et le passage de l'un à l'autre ne change que le dessin, les règles restent les mêmes.

Coût

Outils

Le tableau blanc et le papier suffisent aux premiers jets et aux ateliers: tant que l'ordre des éléments se discute encore, déplacer une branche est gratuit.

Le tableur porte les mêmes règles sous forme de table de décision dès qu'elles se multiplient, et il tient l'arithmétique de remontée de la variante de valeur attendue, une colonne de probabilités, une colonne de gains, une valeur attendue par nœud.

Les outils de diagramme (draw.io/diagrams.net, Lucidchart, Visio) produisent un arbre propre à publier, à revoir ou à intégrer dans un document. Ils dessinent, ils ne contrôlent ni l'exhaustivité ni l'exclusivité.

Les plateformes DMN et de gestion des décisions (Camunda, Drools/KIE, Signavio) sont le palier où la décision s'exécute. Elles se normalisent sur la table de décision et le diagramme des exigences, si bien qu'un arbre y est généralement d'abord conçu, puis transcrit en table pour l'exécution.

Les outils d'analyse de décision (PrecisionTree et @RISK, TreeAge, le paquet dtree sous R) servent la variante à nœuds de hasard: ils tiennent les probabilités, les gains et la remontée de la valeur attendue, puis calculent le seuil de rentabilité au-delà duquel la décision s'inverse.

Sources

• IIBA, A Guide to the Business Analysis Body of Knowledge (BABOK Guide) v3, §10.17 Decision Modelling: la définition de l'arbre de décision, la propriété qui fait de chaque chemin une règle, le partage des conditions, la force en segmentation et les limites de la modélisation des décisions.
• Object Management Group, Decision Model and Notation (DMN): le contexte de la famille de modélisation des décisions et de ses voisins. L'OMG normalise la table de décision et le diagramme des exigences de décision, non une notation d'arbre.
• PMI, A Guide to the Project Management Body of Knowledge (PMBOK Guide): le traitement de l'arbre de décision par la valeur monétaire attendue dans l'analyse quantitative des risques, qui fonde la variante à nœuds de décision et de hasard.
• Howard Raiffa, Decision Analysis: Introductory Lectures on Choices under Uncertainty, Addison-Wesley, 1968: la référence primaire de l'arbre d'analyse de décision, nœuds de décision et de hasard, valeur attendue et évaluation par remontée.