16

Chapitre 1

décision), puis à la détermination de nouvelles déductive). Ces algorithmes sont les suivants :

1.2.1 Neddie

observations²

(par

méthode

Neddieest un descendant d'ID₃[Quinlan, 1983]. A partir d'exemples de plusieurs concepts, il fabrique un arbre de décision qui sépare les concepts de manière efficace. En termes de stratégies de recherche, Neddie effectue une recherche en gradient ("divide and conquer", pas de retour en arrière) du plus général au plus spécifique en utilisant un critère d'évaluation numériqueappelé gain d'information qui est fondée sur la mesure d'entropie de Shannon (1949). Neddie possède les fonctionnalités permettant de transformer un arbre de décision en règles [Corlett, 1983] ou encore l'arrêt de la construction de l'arbre avant son terme en utilisant le test du c²quand toutes les variables candidates à un noeud (les attributs³explicatifs) sont indépendantes de la variable décision (la maladie à expliquer). Néanmoins au départ, Neddie était limité dans son mode de représentation des connaissances et n'utilisait pas de théorie initiale du domaine : chaque exemple était décrit dans une ligne d'un tableau de données (représentation plane ou "attribut-valeur") sans possibilité d'introduire de logique d'ordre 1 (avec variables) dans une description. En outre, cette connaissance "à- plat" ne permet pas de prendre en compte les connaissances de bon sens entre les différents composants d'une description et issues d'une modélisation initiale du domaine [Manago & Conruyt, 1989]. Nous verrons avec KATE (§ 1.4) que ces possibilités sont impératives pour exploiter la richesse des domaines vivants que nous voulons traiter.

1.2.2 Main

Mainest une implantation partielle de l'algorithme de l'étoile AQ [Michalski et al., 1981] version 11 [Michalski, 1983]. Prenant des exemples positifs et négatifs d'un concept (les exemples négatifs⁴sont ceux qui n'appartiennent pas au concept), il génère un ensemble de descriptions conjonctives qui couvrent tous les exemples positifs et un nombre prédéfini par l'utilisateur d'exemples négatifs CE [Manago, 1988].

L'algorithme commence par sélectionner au hasard un exemple e₁ (le noyau) dans l'ensemble des exemples positifs. La liste des attributs de l'exemple est ensuite généralisée à l'aide de règles de généralisation (règle de l'oubli, règle

2_{L'observation est définie mathématiquement par le couple (d(w), Ø) du fait que le nom de la} classe n'est pas connu et reste à déterminer.
3_{Dans cette thèse, la sémantique choisie pour le mot "attribut" est celle du domaine de} l'intelligence artificielle ou de l'analyse des données, c'est à dire la "variable" (ex : couleur, forme, taille, etc.) et non pas dans le sens de "ce qui est attribué à un individu" que nous appelerons la "valeur".
4_{Ou contre-exemples du concept.}