[PDF] Apprentissage de r`egles et arbres de décision

View - Download Apprentissage de r`egles et arbres de décision

Previous PDF

Next PDF

Rech. Intell. et Cooperation

Apprentissage de

regles et arbres de decision

M2 IA&RF / IRR Sept.-Nov. 2015

Introduction

Un agent dans une certaine situation / un certain etatsdoit prendre une decision plusieurs decision possibles, quelle est la((bonne))? depend de l'etat / de la situation

Introduction : Exemples

Un joueur articiel pour un jeu video

)Que faire du ballon ? (Passe, tir, dribble . . . ) Depends de la position du joueur sur le terrain, des positions de ses adversaires. . .2D Simulation Leage { Robocup

Introduction : Exemples

Un banquier devant decider d'accorder ou non un pr^et )depends du demandeur : ^age, profession, statut marital, biens immobiliers, salaire, montant du pr^et, . . .

Introduction : Exemples

Un banquier devant decider d'accorder ou non un pr^et )depends du demandeur : ^age, profession, statut marital, biens immobiliers, salaire, montant du pr^et, . . .

Un medecin devant poser un diagnostique

)depend du resultats d'observations / tests / examens : evre, douleur, toux, rhinorrhee, . . .

Introduction

Decision complexes : dependent de nombreux facteurs

Comment representer le modele de decision ?

on veut un modele comprehensible / interpretable par un humain )regles / arbres de decision Commentapprendre automatiquementle modele de decision ?

Regles et arbres de decision

Situations / etats decrits parnattributsX1;X2;:::;Xn pour chaque attributXi:Xi=dom(Xi) =ensemble des valeurs possibles pourXi )l'ensemble des situations / etats possibles est S=Y X i2Xdom(Xi) un ensemble de decisions /classespossiblesY=fy1;:::g on veut representer / apprendre une fonctionc:S ! Y Regles et arbres de decision : Regles conjonctives

De la formesiXi1=v1etXi2=v2et:::Xik=vkalorsyj

Par exemple:

Regles et arbres de decision : Regles conjonctives

De la formesiXi1=v1etXi2=v2et:::Xik=vkalorsyj

Par exemple:

siposition=devantbut^posgardien=adroite^:::alors tireragauche Regles et arbres de decision : Regles conjonctives

De la formesiXi1=v1etXi2=v2et:::Xik=vkalorsyj

Par exemple:

siposition=devantbut^posgardien=adroite^:::alors tireragauche siage40^proprietaire=oui^:::alors pretok Regles et arbres de decision : Regles conjonctives

De la formesiXi1=v1etXi2=v2et:::Xik=vkalorsyj

Par exemple:

siposition=devantbut^posgardien=adroite^:::alors tireragauche siage40^proprietaire=oui^:::alors pretok Mais: siage>40? siposgardien6=agauche? )une seule regle ne sut pas

Regles et arbres de decision : Arbres

Un arbre de decision pourX1;:::;Xnest un arbre dont : chaque nud interne est etiquete par un test portant sur un ou plusieurs attributs; les ar^etes sous les ls d'un nud interne donne sont etiquetees par des reponses possibles mutuellement exclusives au test porte par ce nud; les feuilles sont etiquetees par des decisions / classes de Y.

Regles et arbres de decision : Arbres

Un arbre de decision pourX1;:::;Xnest un arbre dont : chaque nud interne est etiquete par un test portant sur un ou plusieurs attributs; les ar^etes sous les ls d'un nud interne donne sont etiquetees par des reponses possibles mutuellement exclusives au test porte par ce nud; les feuilles sont etiquetees par des decisions / classes de Y. Un arbre de decisionArepresente une fonctionhA:S ! Y, denie de la maniere suivante : pourx2 S, s'il existe une branche de l'arbre dontx verie toutes les conditions, alorshA(x)est la valeur portee par la feuille correspondante.

Regles et arbres de decision : Arbres

Un arbre de decision pourX1;:::;Xnest un arbre dont : chaque nud interne est etiquete par un test portant sur un ou plusieurs attributs; les ar^etes sous les ls d'un nud interne donne sont etiquetees par des reponses possibles mutuellement exclusives au test porte par ce nud; les feuilles sont etiquetees par des decisions / classes de Y. Un arbre de decisionArepresente une fonctionhA:S ! Y, denie de la maniere suivante : pourx2 S, s'il existe une branche de l'arbre dontx verie toutes les conditions, alorshA(x)est la valeur portee par la feuille correspondante. Inter^et des arbres de decision: facile a lire / interpreter ; representation compacte

Regles et arbres de decision : Arbres

revuebancaire:fr{ 28 Octobre 2014

Regles et arbres de decision : Arbres

allergies:org{ 15 Septembre 2015

Regles et arbres de decision : Arbres

Proprietes

A chaque branche d'un arbre de decision correspond une regle conjonctive. )on peut traduire un arbre en un ensemble de regles Toute fonctionS ! Ypeut ^etre representee par un / plusieurs arbre(s) de decision au pire, une branche par etat / situation )taille potentiellement exponentielle

Apprentissage supervise

Plut^ot que demander a un expert de construire l'enemble de regles ou l'arbre de decision, on peut : lui demander la bonne decision dans certaines situations induireun arbre / un ensemble de regles

Apprentissage supervise

Plut^ot que demander a un expert de construire l'enemble de regles ou l'arbre de decision, on peut : lui demander la bonne decision dans certaines situations induireun arbre / un ensemble de regles

On appelleexempleune paire(x;y)2 S Y:

xrepresente un etat / une situation ; yest la decision correspondante

Apprentissage supervise

Plut^ot que demander a un expert de construire l'enemble de regles ou l'arbre de decision, on peut : lui demander la bonne decision dans certaines situations induireun arbre / un ensemble de regles

On appelleexempleune paire(x;y)2 S Y:

xrepresente un etat / une situation ; yest la decision correspondante Etant donne un ensembleEd'exemples, on chercheh:S ! Y telle quey=h(x)pour tout(x;y)2 E.

Apprentissage supervise : Une regle

Pour la suite, on distingue une valeury02 Y;

pour simplier la presentation, on notey0= +1. )on cherche a apprendre des regles de la forme siXi1=v1etXi2=v2et:::Xik=vkalors+1 qui permettront de predire sic(x) = +1ouc(x)6= +1.

Apprentissage supervise : Une regle

Notations et terminologie :

Pour une regler=

((siXi1=v1etXi2=v2et:::Xik=vkalors+1))on note :

Cond(r) =((Xi1=v1etXi2=v2et:::Xik=vk))

Un exemple(x;y)2 Eest:positifsiy= +1;negatifsinon ;

La regle

exemple(x;y)siXij(x) =vijpourj21:::k. Etant donne un ensemble d'exemplesE, on cherche donc a calculer une regle qui : couvre autant d'exemples positifs que possible ; et couvre aussi peu d'exemples negatifs que possible.

Apprentissage supervise : Une regle

Principe :

On part de la regle trivial((Si vrai alors+1));

cette regle couvre trop d'exemples negatifs (elles les cou- vre tous) ; donc on essaie d'ajouter petit a petit des conditions elementaires / atomes de la formeAi=vi, pour exclure les exemples negatifs, en excluant le moins possible d'exemples positifs.

L'algorithme :

(a)Cond ((rien)); E + fxj(x;+1)2 Eg; E fxj(x;1)2 Eg; (b)

T antque E6=;faire :

i. le((meilleur))atome ; ii.Cond Condet; iii.E E fxjxne verie pasCondg; E + E+ fxjxne verie pasCondg; (c) retourner r=((Si Cond alors+1)).

Apprentissage supervise : Une regle

Un exempleOn a enregistre sur 14 jours si des voiliers etaient sortis sur la mer, ainsi que l'ensoleillement ou non ces jours-la, la temperature, le taux d'humidite, le vent :

Apprentissage supervise : Une regle

ciel temp. humid. ventbateaux ?

1soleil chaude haute nonnon

2soleil chaude haute ouinon

3couvert chaude haute nonoui

4pluie moy. haute nonoui

5pluie froide normal nonoui

6pluie froide normal ouinon

7couvert froide normal ouioui

8soleil moy. haute nonnon

9soleil froide normal nonoui

10pluie moy. normal nonoui

11soleil moy. normal ouioui

12couvert moy. haute ouioui

13couvert chaude normal nonoui

14pluie moy. haute ouinon

)peut-on predire, pour un autre jour, en fonction du soleil, de la temperature, du taux d'humidite, du vent, si on verra

Apprentissage supervise : Une regle

ou non des bateaux ? )peut-on((decouvrir))/induire, d'apres ce tableau, desregles de prediction, par exemple : siciel=soleil et temp=chaude et humid:=haute alors non

Apprentissage supervise : Une regle

Choix d'un((bon))atomeOn cherche, parmi tous lesXi= v ipossibles, un atome qui : exclue autant d'exemples negatifs que possible ; et exclue aussi peu d'exemples positifs que possible.

Pour chaque atome=((Xi=vi)), on note

p() =jfx2E+jXi(x) =vigj =le nombre d'exemples deE+((couverts))par; n() =jfx2EjXi(x) =vigj =le nombre d'exemples deE((couverts))par; )on veut maximiserp()tout en minimisantn().

Exemples de criteres de maximisation possibles :

p()n() p()=(p() +n()) p()( log(p()=(p() +n()))c)(gain d'information) (Voir par exemple [?])

Apprentissage supervise : Un ensemble de regles

En general, ca ne sut pas d'apprendre une regle :

la regle retournee par l'algorithme ci-dessus ne couvre pas d'exemples negatif, mais ne couvre sans doute pas tous les exemples positifs. On va donc cherche a apprendre d'autres regles, qui perme- tte d'apprendre d'autres exemples : on insere l'algorithme ci-dessus dans un boucle qui fait apprendre des regles jusqu'a ce que tous les exemples positifs soient couverts.

Apprentissage supervise : Un ensemble de regles

Algorithme de couverture sequentielle

1.h ;;E+ fxj(x;+1)2 Eg;E fxj(x;1)2 Eg;

2.

T antque E+6=;faire:

(a)Cond ((rien));E E;E+ E+; (b)

T antque E6=;faire :

i. le((meilleur))atome ; ii.Cond Condet; iii.E E fxjxne verie pasCondg; E + E+ fxjxne verie pasCondg; (c)h h[ f((Si Cond alors+1))g; (d)E+ E+ fx2 E+jxnon couvert parhg=E+E+; 3.

Retourner h.

(On dit qu'un exemple(x;y)estcouvertpar un ensemble de regleshs'il y a danshau moins une regle qui couvre(x;y).)

Terminaison de l'algorithme

Etant donnesE+etEtels queE+\ E=;etE+6=;,

on peut toujours trouver un ensemble de regles qui classe

Apprentissage supervise : Un ensemble de regles

bien: h(x) =8 >:+1six2 E+

1sinon

Etant donnesE+etE, tels queE+\E=;etE+6=;,

et une conditionCondveriee par toutx2E+, on peut tou- jours trouver une conditionCond' telle queCond(x)etCond0(x) = fauxpour toutx2E: on choisit unx02E+, et on pose Cond

0(x) =vraisix=x0.

Apprentissage supervise : Arbres de decision

Un algorithme :

Entree : un ensembleE X Y;

1. si p ourtout (x;y);(x0;y0)2 Eon ay=y0: retourner cette valeur ;

2.A le((meilleur))attribut deX;

3. cr eerun nud etiquetepa rA; 4. p ourchaque v2Afaire: (a) cr eerune b ranche etiqueteepa rv; (b) y attacher un a rbrede d ecisionp ourEv=f(x;y)2 E j

A(x) =vg

Apprentissage supervise : Arbres de decision

Choix du((meilleur))attributOn va essayer de trouver l'attribut amenant uneentropieminimale. Etant donnes un ensemble d'exemplesE, un attributAet une valeurv2dom(A): on note :Ev=f(x;y0)2 E jA(x) =vg; pour chaquey2 Y: p yv=jf(x;y0)2 E jA(x) =vety0=ygj=jEvj; p yvest la proportion d'exemples qui ont l'etiquetteyparmi ceux qui ont la valeurvpour l'attributAdansE. Alors on denit l'entropie deEpour l'attributAet la valeur vainsi :

Entropie(E;A;v) =X

y2Ypyvlogpyv

Apprentissage supervise : Arbres de decision

Proprietes de l'entropie :

s'il existe une valeurytelle quepyv= 1: alorsEntropie(E;A;v) = 0; sinonEntropie(E;A;v)>0; la valeur maximale est atteinte lorsquepyv= 1=jYjpour toutey2 Y. Remarque :en theorie de l'information, l'entropie mesure l'incertitude d'une variable aleatoire. SiXpeut prendre deux valeurs0et1avec une probabilite 1/2 pour chacune, l'incertitude sur la valeur qui peut ^etre prise est maximale. Si par contre la probabilite d'avoir 1 est par exemple0;9, l'incertitude est tres faible (c'est tres probable d'avoir1).

Apprentissage supervise : Arbres de decision

On va donc denir le gain ainsi:

G(E;A) =Entropie(E)X

v2dom(A)jE vjjEj

Entropie(E;A;v)

Le second terme est la moyenne des entropies des ensemblesquotesdbs_dbs23.pdfusesText_29

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision

[PDF] arbre de décision définition

[PDF] dénombrement cours 1ere s

[PDF] apollon et daphné résumé

[PDF] apollon et daphné leur histoire

[PDF] expression etre nature

[PDF] tp mise en évidence d'une réaction d'oxydoréduction

[PDF] apollon et daphné peinture

[PDF] apollon et daphné le bernin

[PDF] tp chimie réaction d oxydoréduction