Rappel de cours sur les arbres de décision

Cédric Herpson

Description

nonnonnonUniversite Paris 7 - Denis Diderot Introduction a l’IAerM1 info Annee 2009-2010, 1 semestreRappel de Cours n 3Arbres de DecisionProbleme : Disposer de procedures de classi cation aisement interpretables par des non experts.Les arbres de decision, de par leur representation graphique des regles de decision, sont unesolution a ce probleme (parmi d’autre).Exemple : Supposons que nous sommes medecin. Nous avons 3 patients que nous connaissonset que nous decrivons suivant l’apparition ou non de 2 sympt^ omes (tousse et tc corporelle). :Tousse tc 38 ClassePatient 1 oui oui maladePatient 2 oui nonPatient 3 non non seinL’objectif est de representer ces malades par une structure de donnee permettant de bien lesclassi er et de diagnostiquer correctement (on l’espere) de nouveaux patients arrivant a l’h^ opital.tc 38cMalade Tousse TousseMalade : Malade Malade : MaladeCes 2 arbres permettent de classer correctement les 3 patients ( l’ensemble d’apprentissage). Onse rend deja compte que l’ordre dans lequel sont utilise les descripteurs in ue sur la taille del’arbre.Si une nouvelle personne, qui ne tousse pas mais possede une temperature superieure a 38c, sepresente a l’h^ opital, on va utiliser l’arbre construit pour etablir un diagnostic. Dans le cas present,l’arbre de gauche va considerer qu’elle est malade en se basant uniquement sur sa temperature.L’arbre de droite va quant- a-lui decider que le patient ...

Informations

• Publié par: Phawyar
• Nombre de lectures: 185
• Langue: Français

Extrait

Universit´eParis7-DenisDiderotIntroduction`al’IA er M1infoAnne´e2009-2010,1semestre ◦ Rappel de Cours n 3 ArbresdeDe´cision

Proble`me:Disposerdeproc´eduresdeclassificationaise´mentinterpre´tablespardesnonexperts. Lesarbresded´ecision,deparleurrepre´sentationgraphiquedesr`eglesdede´cision,sontune solution`aceprobl`eme(parmid’autre). Exemple:Supposonsquenoussommesm´edecin.Nousavons3patientsquenousconnaissons etquenousd´ecrivonssuivantl’apparitionounonde2symptˆomes(tousseett˚ccorporelle).:

Patient 1 Patient 2 Patient 3

Tousse oui oui non

t˚c≤38 oui non non

Classe malade malade sein

L’objectifestderepre´sentercesmaladesparunestructurededonn´eepermettant classifieretdediagnostiquercorrectement(onl’espe`re)denouveauxpatientsarrivant

Malade

t˚c≥38˚c

Tousse

Tousse

de bien les a`l’hˆopital.

Malade¬Malade Malade¬Malade Ces 2 arbres permettent de classer correctement les 3 patients ( l’ensemble d’apprentissage). On serendd´ejacomptequel’ordredanslequelsontutilise´lesdescripteursinfluesurlataillede l’arbre. Siunenouvellepersonne,quinetoussepasmaisposse`deunetemp´eraturesup´erieure`a38˚c,se pr´esentea`l’hˆopital,onvautiliserl’arbreconstruitpoure´tablirundiagnostic.Danslecaspr´esent, l’arbredegauchevaconside´rerqu’elleestmaladeensebasantuniquementsursatempe´rature. L’arbrededroitevaquant-`a-luid´eciderquelepatientestseinensebasantuniquementsurle fait qu’il ne tousse pas! !. Onvoitdoncquelaformedel’arbreinfluenonseulementsurlastructuremaise´galementsur lad´ecision.

Definition 0.1Arbre parfaitrbnapareairfstteselpmexUontelquetoutlesenurarbdedee´icis del’ensembled’apprentissagesoientbienclass´es.

1

L’objectifestd’obtenirl’arbrelepluspetitpossible(facilitantlarecherche)toutene´tablissant un compromis entre les taux d’erreur sur l’ensemble d’apprentissage et sur l’ensemble de test 1 afindepouvoirbieng´en´eraliser.Pourcefaire,onintervient`a2niveaux: 1.Ons´electionnelesattributsquiminimisentlatailledel’arbretoutenclassantcorrectement les exemples de l’ensemble d’apprentissage. 2.On´elaguecertainesbranchesdemani`ere`agarderunpouvoirdege´n´eralisation(quittea` faireaugmenterl’erreursurl’ensembled’apprentissage).Cet´elagagepeutsefairependant laconstructiondel’arbre(pre´-e´lagage)ouapr`es(post-e´lagage).

1Se´lectiondesattributsdiscriminants Ide´ege´ne´rale:Pourlaconstructiondel’arbredede´cision,onmesurele”d´esordre”initialde l’ensembled’apprentissage.Onmesureensuitelede´sordredecemˆemeensembleapre`savoirtri´e celui-ciaveclesdiffe´rentsattributsdisponible.Oncompareensuitecesdiffe´rentesmesuresde ”d´esordre”etonse´lectionnel’attributquipermetdeminimisercelui-ci.Danslapratique,les2 m´ethodeslesplusconnuessont: 1.L’Entropiedel’information(Shannon)[algosID3etC4.5propos´esparQuinlan] P n Entropie(X) =−E[log 2 (P(C i ))] =−P(C i )∗log 2 (P(C i )) i=1 2.IndicedeGini[algoCART,propos´eparBreiman] P P n n 2 Gini(X) = 1−P(C i ) =P(C i )∗(1−P(C i )) i=1i=1 2 avecP(C i ) =|C i |/|X|uoseteeosnedx`eamlp’leXncsoermrbelesdpC i dxffie´eruasse.esntascl Sionprendl’exempled’unprobl`emeo`uiln’yaque2classes,+et-,etsil’onconside`reque notreensembleded´epartXestconstitu´edepexemplesdelaclasse+etdenexemplesdela classe -, alors : p p n n E(X) =E(p, n) =−[∗log+( )∗log( )] p+n p+n p+n p+n p 2 n 2 Gini(X) = 1−) ]+ ([( ) p+n p+n Ontpeu´egalementconsid´ererces2grandeurscommedesmesuresdelaquantite´d’informa- tionn´ecessairepourpouvoir”rangercorrectement”X.Danstoutlescas,pluscesvaleurssont importantes,etmoinsles´ele´mentssontordonne´s. Legaind’informationapport´eparchaqueattribut(A),calcule´afindechoisirceluidontlegain estleplus´elev´e,estobtenucommesuit: P v n i +p i Gain(A)= F(X) - Reste(A) . avec :Reste(A) =∗F(n i , p i ) i=1 p+n o`uvAedensioest`utoerbmoneltaulavedReste(A)li’utsere´ede”d´esordre”qseltqaautnti a`traiterapre`savoirutilise´l’attributAu`oteF´eepd´eronsiioncreelminisircuodrstcnofaltse attributs (Entropie ou Gini). Desexercicescorrig´esassocie´s`al’utilisationdeces2grandeurspourlaconstructiond’unAD sontdisponibles`al’adressesuivante:http://www-desir.lip6.fr/ herpsonc/ia1.htm ~ 1.Cflerappeln˚2surl’apprentissagesupervise´pourfaireladistinctionles2typesd’erreur 2.Ontrouve´egalementcetteformuleavecP(C i |Xcleadaepal)`P(C i ).P(C i |X) =P(C i ∩X)/P(X) or C i ⊂XetX= Ω, on retombe donc surP(C i )

2