III .2 ARBRE DE DECISION (12J , (10J, (11J
III.2 .0 CONCEPTS THEORIQUES SUR LE GRAPHE [12]
Graphe :
Définition :
Un graphe G est un couple G=(X,U) ,X
est un ensemble non vide et au plus dénombrable .
Nota :X est un ensemble fini ,les éléments de x?X
sont appelés les
sommets ou noeuds ,u = une famille d'éléments du
produit
cartésiens XxX .
Les éléments de U=(x,y) ,x,y?X, sont appelés
:
Soit des arcs lorsqu'on tient compte de l'orientation.
Soit les arêtes lorsqu'on ne tient pas compte de
l'orientation.
Graphe connexe :
Définition :
Un graphe est connexe si l'on peut atteindre n'importe quel
sommet à partir d'un sommet quelconque en parcourant les
différentes arêtes.
Exemple : soit G=(X,U)
U8
U7
U9
U1
U3 U4
U5
U6
U2
G=(X,U) est un graphe connexe .
[47]
Arbres et arborescence
1. Arbres :
Définition :
Un arbre est un graphe connexe sans cycle. C'est-à-dire
dont on peut atteindre n'importe quel sommet à partir d'un sommet quel-
conque en parcourant différents arêtes et ses arêtes ne
coïncide pas.
Exemple :
Les notions de branches et de cordes :
Soit G=(X,U) un graphe et notons par T=(X,u') un arbre qui est
un graphe partiel de G ,alors :
Les arêtes appartenant à u' sont appelées
les branches de T (ou relativement T )
Les arêtes de u?u' (c'est-à-dire ? (u /u') sont
appelées cordes relativement T.
Exemple : soit G=(X ,U) un graphe connexe ,on peut en
U4
U10
extraire un arbre.
U1
U8
U9
U6
U2 U3
U11
U5
U12
U7
T=(X ,U') ou u'=(U1,U5,U6,U11,U7) : ce sont les branches
tandis que (U2,U3,U4,U12,U11,U9) : ce sont des cordes.
Chaque réponse possible est prise en compte et permet
de se diriger vers un des fils du noeud. De
[48]
a
c
b
f
e
d
Est un arbre extrait du graphe G=(X ,U)
précédent.
2. Arborescence :
Définition :
Soit G=(X,U),on dit que le sommet r?X
est une racine de G si V x?X,(avec x?r)? un chemin de rà x
.c'est -
à -dire un arbre ayant une racine.
Exemple :
c
b
f
e
d
a
C'est une arborescence de racine a.
Nota : un sommet pendant est un sommet sans successeur . En
informatique on les appelle des feuilles ou feuillets.
III .2.1 INTRODUCTION A L'ARBRE DE DECISION [6J
Un arbre de décision est une structure qui permet de
déduire un résultat à partir de décisions
successives. Pour parcourir un arbre de décision et trouver une
solution, il faut partir de la racine. Chaque noeud est une décision
atomique.
[49]
proche en proche, on descend dans l'arbre jusqu'à
tomber sur une feuille. La feuille représente la réponse
qu'apporte l'arbre au cas ou l'on vient de tester.
? Début à la racine de l'arbre
? Descendre dans l'arbre en passant par les noeuds de test
? La feuille atteinte à la fin permet de classer
l'instance testée. Très souvent on considère qu'un noeud
pose une question sur une variable, la valeur de cette variable permet de
savoir sur quels fils descendre. Pour les variables
énumérées, il est parfois possible d'avoir un fils par
valeurs, on peut aussi décider que plusieurs variables
différentes mènent au même sous arbre.
Pour les variables continues, il n'est pas imaginable de
créer un noeud qui aurait potentiellement un nombre de fils infini, on
doit discrétiser le domaine continu (arrondis, approximation), donc
décider de segmenter le domaine en sous ensembles. Plus l'arbre est
simple, et plus il semble techniquement rapide à utiliser.
En fait, il est plus intéressant d'obtenir un arbre qui
est adapté aux probabilités des variables à tester. La
plupart du temps un arbre équilibré sera un bon résultat.
Si un sous arbre ne peut mener qu'à une solution unique, alors tout ce
sous-arbre peut être réduit à sa simple conclusion, cela
simplifie le traitement et ne change rien au résultat final.
| 
