35

Le cheminement conceptuel

description de l'objet courant au niveau de ses attributs ou encore de ses spécialisations.

Si un seul des exemples au noeud courant ne contient pas un objet du même type, le gain d'information du test "existe(objet)" est calculé et les tests portants sur ses champs ne sont pas considérés.

*

Pour les détails concernant l'algorithme, voir le chapitre 7.

Cet arbre peut dans un deuxième temps être exploité pour identifier un nouveau cas : les noeuds de l'arbre correspondent à des questions posées à l'utilisateur, les feuilles correspondent aux diagnostics donnés par le système expert.

L'algorithme ID₃utilise la mesure numérique du gain d'informationdérivée des travaux en théorie de l'information fondée sur l'entropie [Shannon, 1949]. Le but est de déterminer à chaque niveau les critères les plus discriminants. En phase d'apprentissage de l'arbre, le gain d'information des différents critères est calculé et celui estimé le plus discriminant est sélectionné de façon irrévocable (pas de retour en arrière ou de recherche en faisceau). Ce processus est répété récursivement jusqu'à ce qu'il ne reste plus que des exemples de la même classe (ici le nom du diagnostic). ID₃utilise une stratégie de recherche heuristique en gradient [Nilsson 1980] qui tend à produire un arbre globalement efficace : en moyenne, un nombre minimum de questions sont posées à l'utilisateur durant la consultation interactive de l'arbre de décision.

L'induction permet de transformer une base de données brutes en une connaissance opérationnelle exploitable. Elle permet en outre d'apprendre automatiquement trois types de connaissances :

[!]

[!]

[!]

un ensemble de critères optimaux (en un certain sens) pour reconnaître efficacement un concept (une généralisationdes exemples d'apprentissage), un ordre sur les critères en fonction de leur capacité à discriminer les exemples des différentes classes (information de contrôle), une partition des exemples d'apprentissage aux feuilles de l'arbre.

Outre la construction d'un arbre de décision, des règles de production peuvent ensuite être obtenues par élagage de l'arbre [Manago, 1988].

Comparé à d'autres algorithmes d'induction, ID₃présente certains avantages : plusieurs exemples peuvent appartenir à la même classe dans la base à traiter, il peut y avoir plus de deux classes différentes à discriminer (nous ne sommes pas limité à un apprentissage de type exemples et contre-exemples), les critères nominaux (à valeurs discrètes) peuvent avoirs plusieurs valeurs pour marquer l'imprécision des réponses de l'utilisateur, etc.. Les implantations de l'algorithme ID₃gèrent également les critères à valeurs continues et ordonnées