220

Chapitre 7

7.2.1 Formalisation de la procédure de détermination

Une détermination à partir d'un arbre de décision se fait en débutant à la racine de l'arbre T, que nous appellerons d₀. A chaque noeud de T, se trouve un critère de détermination d_i= (A_i, V_i, E) :

- A_iest le nom d'un attribut (A_i[ Y_i[!]S_i),
- V_iest l'ensemble des valeurs observables de A_i, V_i= {v₁,...,v_i,...,v_n}, - E est l'ensemble des exemples w restant au noeud d.

Le cas w à déterminer est apparié à d_i= d₀, puis en fonction de la (ou des) valeur(s) qu'il prend pour l'attribut A_i, le (ou les) noeud(s) fils d_i'devien(nen)t candidat(s) pour l'(les) appariement(s) suivant(s). La procédure s'arrête lorsque l'on atteint une (les) feuille(s) libellée(s) par un nom de concept. Ce nom devient le résultat de la détermination. Lorsque plusieurs feuilles sont atteintes, le résultat est une combinaison de concepts avec des coefficients de vraisemblance associés à chacun d'eux, et calculés en fonction du nombre d'exemples indexés à chacune des feuilles.

Soit D = D_n[!]D_t= {d_i}, l'ensemble des noeuds de T.
D_n= {d_n} est l'ensemble des noeuds intermédiaires,
D_t= {d_t} est l'ensemble des noeuds terminaux.

Le parcours de l'arbre pour la détermination est exprimé par l'algorithme récursif suivant :

Algorithme :

Début :
d_i= d₀,

Apparier (w, d_i)
sid_i[!] D_talors
A_i (w) = c_i[!] w [!] {c_i}
sinon
Pour tout v_i [!] d_i
si y_i (w) = v_ialors Apparier (w, d_i')
Fin pour tout
Fin si
Fin.

7.2.2 Limites de l'approche inductive