216

Chapitre 7

Tout noeud d_iautre que d₀est relié par un arc à un autre noeud d_i'appelé le fils de d_i. Si d_i'est filsde d_ialors d_iest appelé pèrede d_i'. Cet arc est une branche avec un sommet d_i' et une extrémité d_i. Elle contient la valeur v_i à observer pour déterminer l'individu (cf. figure 7.1).

D_t= {d_t} est l'ensemble des noeuds terminaux ou feuilles de l'arbre T, une feuilleest un noeud d_k= d_tqui n'a pas de fils.

Soit la relation ">" ("père de").

Supposons que d₁, d₂, ..., d_k soit une séquence de noeuds de T telle que d₁ > d₂ > ... > d_k-1> d_k.Cette séquence est appelée un chemindepuis d₁ jusqu'à d_kdans T. La longueur du chemin est k - 1.

La profondeur de l'arbre Test la longueur du chemin maximal menant de d₀à d_t.

6)Tester si toutes les variables candidates à un noeud de l'arbre sont jugées "indépendantes" de la variable décision. Pour ce faire, on calcule le test du c² pour chaque variable à partir du tableau de contingence défini par celle-ci et la variable décision. Puis on compare ce calcul avec le gain d'information. Ce dernier tend vers un c² lorsque le nombre de cas au noeud courant est élevé.

Remarque: ce dernier point n'est souvent pas vérifié dans nos application pour la significativité du test, ce qui est un inconvénient pour arrêter la construction de l'arbre de manière fiable. Ce test est à considérer pour les noeuds terminaux dont le nombre d'exemples est élevé ainsi que le nombre de modalités de la variable décision [Crémilleux, 1991].

7)Il ne reste plus aucune variable candidate pour segmenter le noeud. En effet, à chaque fois qu'une variable est choisie comme test pour l'arbre de décision, elle est éliminée de la liste des variables candidates pour les noeuds suivants. Cette règle ne s'applique pas pour les variables numériques qui peuvent être réutilisées plusieurs fois (voir § 7.1.4.4). De même, les variables classifiées présentent des valeurs différentes si elles ont déjà été utilisées une fois pour la segmentation : il faut pour cela exploiter l'ordre introduit par les noeuds intermédiaires de la taxonomie des valeurs possibles : la variable est examinée paliers par paliers jusqu'aux feuilles terminales avant d'être éliminée de la liste des variables candidates.