215

Le traitement des descriptions biologiques: KATE et CaseWork

Dans notre algorithme, A = meilleure_division (E, s) correspond au choix de l'attribut de s possédant le gain d'information relatif le plus élevé pour séparer au mieux les exemples en fonction du but à atteindre qui est de faire de la discrimination sur l'attribut C.

7.1.4.3 Critèred'Arrêt (E)

Il existe plusieurs moyens d'arrêter la construction d'un arbre de décision :

1)" w [!] E , Classe(w) = c_i.

C'est la condition d'arrêt la plus naturelle, c'est-à-dire lorsque tous les cas d'un noeud ont la même modalité c_i pour la variable décision.

2)Card (E) > seuil donné.

Un inconvénient du premier critère d'arrêt est qu'il conduit à une séparation totale des classes, ce qui fait que certaines branches terminales ne possèdent que très peu d'exemples. Donc, séparer les exemples lorsqu'il n'en reste que 2 ou 3 n'est pas significatif d'un point de vue statistique : cela relève le plus souvent du hasard et ne contribue pas à une véritable connaissance du domaine [Crémilleux, 1991].

C'est pourquoi certains algorithmes imposent un nombre minimal d'exemples pour continuer à construire le sous-arbre (segmenter le noeud courant) comme le fait le système CART [Breiman et al., 1984] en attribuant a priorila valeur 5 à ce seuil.

3)Card (E) / Card (W) > seuil donné.

Au lieu d'appliquer le critère absolu du 2), on dépendant du nombre total de cas [Cestnik, 1987].

4)Card ({ w [!] E / Classe(w) = c_i}) > seuil donné.

peut

fixer

un

seuil

relatif

Au lieu de comptabiliser les cas indépendamment de la classe auxquels ils ont été attribués, on peut décider d'arrêter la construction de l'arbre lorsque le nombre de cas d'une même classe dépasse un certain seuil.

5)La profondeur de l'arbre est limitée à un seuil donné.

Soit D = {d_i}, l'ensemble des noeuds de l'arbre T, soit d₀un noeud particulier appelé la racine de l'arbre.