209

Le traitement des descriptions biologiques: KATE et CaseWork

V^ij
k^{est l'ensemble des valeurs observées de yi}
j^{lorsqu'il existe k instances de} l'objet i pour le cas w. Si k = 1, on a V^iji
k^{= V}j^{et Mi = Ni.}

7.1.2 Principe de la classification par arbre de décision

Le but de la méthode de création d'un arbre de décision est d'obtenir une caractérisation des classes décrites dans les exemples en construisant une fonction caractéristique de reconnaissance suffisante des classes entre elles (ce qui correspond à une diagnose, voir figure 2.5).

L'idée centrale des algorithmes d'apprentissage par arbre de décision consiste à diviser récursivement les exemples de l'ensemble W d'apprentissage à l'aide des attributs jusqu'à obtenir des sous-ensembles d'exemples qui soient suffisamment purs, c'est-à-dire ne contenant (presque) que des exemples appartenant tous à la même classe.

Ces sous-ensembles sont alors regroupés au niveau des terminaux de l'arbre de décision.

feuilles

ou

noeuds

Une division d'un noeud intermédiaire est déterminée par l'un des attributs qui décrivent les exemples. Cette division est fonction du nombre de valeurs possibles associées à l'attribut. Par exemple, dans le cas d'un attribut booléen, numérique ou testant l'existence d'un objet, la division est binaire. Elle est n_aire en considérant un ensemble finide valeurs qualitatives nominales ou classifiées.

La division peut aussi être vue comme une question à poser à l'utilisateur pour permettre la séparation des exemples en autant de groupes qu'il y a de valeurs possibles attachées à l'attribut.

L'autre idée est que cette division soit la plus efficace possible de manière à ce que l'effort de recherche pour trouver la solution soit minimal : on désire poser le minimum de questions à l'utilisateur. Cette idée est néanmoins subordonnée à l'utilisation de l'arbre de décision pour faire de la détermination.

Soit T un arbre de décision n_aire construit à partir de W et dun noeud intermédiaire de T correspondant à un sous-ensemble E [!] W, et défini par la division s(figure 7.1). Le noeud d correspond au choix d'un attribut A parmi s, s étant la liste des attributs ordonnés en fonction de leur pouvoir de discrimination. E est l'ensemble des exemples au noeud d, c'est-à-dire l'ensemble qui vérifie la liste des valeurs indexées sur le chemin conduisant de la racine d₀à d (voir § 7.1.4.2.5).