Arbre de décision

Un arbre de décision est un outil d'aide à la décision représentant un ensemble de choix sous la forme graphique d'un arbre. Les différentes décisions possibles sont situées aux extrémités des branches (les « feuilles » de l'arbre), et sont atteintes en fonction de décisions prises à chaque étape. L'arbre de décision est un outil utilisé dans des domaines variés tels que la sécurité, la fouille de données, la médecine, etc. Il a l'avantage d'être lisible et rapide à exécuter. Il s'agit de plus d'une représentation calculable automatiquement par des algorithmes d'apprentissage supervisé.

Exemple simple

Exemple d'un arbre de décision pour décider si une personne a des risques d'avoir un accident cardiovasculaire.

Prenons l'exemple du risque d'avoir un accident cardiovasculaire. Dans un arbre de décision, on pose des questions. On descend dans l'arbre jusqu'à obtenir la réponse « peu de risque » ou « grand risque ». La figure donne un exemple d'un arbre de décision. Il y a deux attributs : l'âge et le fait que la personne soit fumeuse. On pose d'abord la question de l'âge. Si on a moins de 30 ans, il y a peu de risque. Si on a plus de 30 ans, on pose la question si la personne est fumeuse. Si non, peu de risque. Si oui, le risque est grand.

Présentation

Les arbres de décision sont utilisés dans des domaines d'aide à la décision (par exemple l'informatique décisionnelle) ou l'exploration de données. Ils décrivent comment répartir une population d'individus (clients d'une entreprise, utilisateurs d'un réseau social, …) en groupes homogènes selon un ensemble de variables discriminantes (âge, temps passé sur un site Web, catégorie socio-professionnelle, …) et en fonction d'un objectif fixé (aussi appelé « variable d'intérêt » ou « variable de sortie » ; par exemple : chiffre d'affaires, probabilité de cliquer sur une publicité, …).

Par exemple, l'arbre de décision ci-dessous (tiré de l'ouvrage de Quilan^[1]) illustre le cas où l'on cherche à prédire le comportement de sportifs (la variable à prédire Jouer prenant l'une des deux valeurs « oui » ou « non ») en fonction de données météorologiques (Ensoleillement, Température, Humidité ou Vent), appelées variables prédictives.

Arbre de décision sur les données Weather

Chaque nœud de l’arbre décrit la distribution de la variable Jouer à prédire. Dans le cas du premier nœud, la racine de l’arbre, nous constatons qu’il y a 14 observations dans notre fichier : 9 cas où une partie a eu lieu (Jouer = oui) et 5 où aucune partie n'a eu lieu (Jouer = non). Ce premier nœud a plusieurs fils construits en utilisant la variable Ensoleillement : le plus à gauche (Ensoleillement = Soleil) comporte 5 observations, le suivant (Ensoleillement = couvert) en comporte 4, et ainsi de suite. La suite de décisions continue jusqu'à ce que, dans l'idéal, les observations dans un nœud soient toutes « oui » ou toutes « non ». On dit alors que le nœud est homogène.

Le processus de décision s'arrête aux feuilles de l’arbre. Dans l'arbre ci-dessus, toutes les feuilles sont homogènes, c'est-à-dire que les variables prédictives utilisées permettent de prédire complètement (sur ce fichier de données) si une partie va avoir lieu ou non. (Notons qu'il serait possible de construire l'arbre selon un ordre différent des variables de météo, par exemple en considérant l'humidité plutôt que l'ensoleillement à la première décision). L'arbre se lit intuitivement de haut en bas, ce qui se traduit en termes de règles logiques sans perte d’informations : par exemple, la feuille la plus à gauche se lit : « si ensoleillement = soleil et humidité < 77,5 % alors jouer = oui ».

Exemple d'arbre en contexte décisionnel

Cet exemple d'arbre de décision, au sens de la Recherche opérationnelle, est librement inspiré d'un ouvrage de James Evans^[2].

Version textuelle

Les estimations de coûts et les probabilités ne sont pas réalistes, ce ne sont que de simples illustrations. De même, il existe d'autres paramètres de calcul des solutions aux arbres de décision, ignorés ici par souci de simplicité.

Vous êtes chargé du développement d'un médicament. Les essais de Phase II ont été très encourageants et vous souhaitez déterminer si le lancement de cette préparation sera ou non rentable pour votre société. Remarque liminaire : les coûts des études réalisées jusque-là sont irrécupérables et n'entrent donc pas dans le processus de décision. Ce dernier comprend :

• Une phase de décision, lancer ou non la phase III. Si non, l'affaire s'arrête et si oui, cela vous coûtera 250 M€.
• Une phase aléatoire (chance) : 30% de chances que cette phase soit concluante, 70% de chances d'échec.
• Une nouvelle phase de décision, en cas de réussite uniquement : soumettre une demande d'agrément à l'ANSM ou, aux États-Unis, à la FDA. Vous estimez les coûts des aller-retours prévisibles à 25 M€.
• Une deuxième phase aléatoire : 60% de chances que votre proposition soit acceptée.
• Pas d'autre phase de décision : si c'est approuvé vous lancez le produit.
• Mais, là, une dernière phase aléatoire :
  • Avec une probabilité de 60%, votre médicament sera un succès éclatant, générant au moins 4,5 Md€ ;
  • Pour 30% des cas, le succès sera moindre, le retour n'étant que de 2,2 Md€ ;
  • Dans 9,9% des cas, des concurrents lanceront des solutions proches, limitant vos gains à 1,5 Md€ ;
  • Enfin, et même si cela est très improbable (0,1% de chances), l'affaire peut virer au fiasco avec des procès vous conduisant à débourser 10 Md€ de dommages et intérêts.

Question simple : lancez-vous la phase III ou non ?

Vue de l'arbre de décision

Cet arbre a été obtenu grâce à la procédure Dtree de SAS/OR ^[3], légèrement édité ensuite.

Légende :

• Les carrés sont les phases de décision, les ronds ouverts les phases aléatoires, les ronds fermés les phases de fin ;
• Les lignes plus sombres sont les décisions suggérées par le modèle ;
• r : coût d'une décision unique ;
• CR : coût cumulé des décisions jusque-là ;
• EV : espérance mathématique de gain.

Le calcul de ces dernières se fait à rebours, de droite à gauche. L'espérance est positive pour la première décision, donc on lance le processus.

Utilisation en apprentissage automatique

Un avantage majeur des arbres de décision est qu'ils peuvent être calculés automatiquement à partir de bases de données par des algorithmes d’apprentissage supervisé. Ces algorithmes sélectionnent automatiquement les variables discriminantes à partir de données non structurées et potentiellement volumineuses. Ils peuvent ainsi permettre d'extraire des règles logiques de cause à effet (des déterminismes) qui n'apparaissaient pas initialement dans les données brutes.

Extensions

Certains formalismes alternatifs proposent d'ajouter des règles de transition plus complexes dans chaque nœud. Ces formalismes sont alors utiles non pas pour l’apprentissage automatique mais pour la construction incrémentale de bases de connaissances, quand on dispose d'un expert dans le domaine d'application visé. On peut citer les Règles Dé-Roulées (Ripple Down Rules (en)), les EDAG (Exception directed acyclic graphs)^[4], ou les nœuds de situation (nos) du logiciel libre EdiNoS.

Par ailleurs, un autre usage en apprentissage automatique consiste à construire non pas un arbre mais une forêt d'arbres de décision. Une décision est alors prise en faisant « voter » l'ensemble des arbres et en choisissant la réponse majoritaire (pour un choix discret) ou la moyenne des réponses (pour une variable continue).

Voir aussi

Sur les autres projets Wikimedia :

• Arbre de décision, sur Wikiversity

Articles connexes

• Arbre enraciné
• Forêt d'arbres décisionnels

Liens externes

• Ressource relative à la santé :
  • Medical Subject Headings
• Notices dans des dictionnaires ou encyclopédies généralistes :

  • Britannica
  • Gran Enciclopèdia Catalana
• Notices d'autorité :

  • GND
  • Israël
  • Tchéquie
• Une introduction aux arbres de décision
• EdiNoS, logiciel libre permettant de construire des graphes décisionnels étendus

Références

1. R. Quinlan: C4.5: Programs for Machine Learning, Morgan Kaufmann Publishers Inc., 1993.
2. James R. Evans et Ayanendranath Basu, Statistics, data analysis, and decision modeling, Pearson, coll. « Always learning », 2013 (ISBN 978-0-273-76822-7 et 978-0-13-274428-7)
3. (en) SAS Institute Inc., SAS/OR 15.2 User's Guide: Project Management, Cary, NC, SAS Institute Inc., 2020 (lire en ligne)
4. (en) Brian Gaines, « Exceptions DAGS as Knowledge Structure », AAAI Technical Report WS-94-03,‎ 1994 (lire en ligne)

• Portail des probabilités et de la statistique