La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Rappel de cours sur les arbres de décision

De
2 pages
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 ...
Voir plus Voir moins
Universit´eParis7-DenisDiderotIntroduction`alIA er M1infoAnne´e2009-2010,1semestre Rappel de Cours n 3 ArbresdeDe´cision
Proble`me:Disposerdeproc´eduresdeclassicationaise´mentinterpre´tablespardesnonexperts. Lesarbresded´ecision,deparleurrepre´sentationgraphiquedesr`eglesdede´cision,sontune solution`aceprobl`eme(parmidautre). Exemple:Supposonsquenoussommesm´edecin.Nousavons3patientsquenousconnaissons etquenousd´ecrivonssuivantlapparitionounonde2symptˆomes(tousseett˚ccorporelle).:
Patient 1 Patient 2 Patient 3
Tousse oui oui non
t˚c38 oui non non
Classe malade malade sein
Lobjectifestderepre´sentercesmaladesparunestructurededonn´eepermettant classieretdediagnostiquercorrectement(onlespe`re)denouveauxpatientsarrivant
Malade
t˚c38˚c
Tousse
Tousse
de bien les a`lhˆopital.
Malade¬Malade Malade¬Malade Ces 2 arbres permettent de classer correctement les 3 patients ( l’ensemble d’apprentissage). On serendd´ejacomptequelordredanslequelsontutilise´lesdescripteursinuesurlataillede l’arbre. Siunenouvellepersonne,quinetoussepasmaisposse`deunetemp´eraturesup´erieure`a38˚c,se pr´esentea`lhˆopital,onvautiliserlarbreconstruitpoure´tablirundiagnostic.Danslecaspr´esent, larbredegauchevaconside´rerquelleestmaladeensebasantuniquementsursatempe´rature. Larbrededroitevaquant-`a-luid´eciderquelepatientestseinensebasantuniquementsurle fait qu’il ne tousse pas! !. Onvoitdoncquelaformedelarbreinuenonseulementsurlastructuremaise´galementsur lad´ecision.
Definition 0.1Arbre parfaitrbnapareairfstteselpmexUontelquetoutlesenurarbdedee´icis delensembledapprentissagesoientbienclass´es.
1
Lobjectifestdobtenirlarbrelepluspetitpossible(facilitantlarecherche)toutene´tablissant un compromis entre les taux d’erreur sur l’ensemble d’apprentissage et sur l’ensemble de test 1 andepouvoirbieng´en´eraliser.Pourcefaire,onintervient`a2niveaux: 1.Ons´electionnelesattributsquiminimisentlatailledelarbretoutenclassantcorrectement les exemples de l’ensemble d’apprentissage. 2.On´elaguecertainesbranchesdemani`ere`agarderunpouvoirdege´n´eralisation(quittea` faireaugmenterlerreursurlensembledapprentissage).Cet´elagagepeutsefairependant laconstructiondelarbre(pre´-e´lagage)ouapr`es(post-e´lagage).
1Se´lectiondesattributsdiscriminants Ide´ege´ne´rale:Pourlaconstructiondelarbredede´cision,onmesureled´esordreinitialde lensembledapprentissage.Onmesureensuitelede´sordredecemˆemeensembleapre`savoirtri´e celui-ciaveclesdie´rentsattributsdisponible.Oncompareensuitecesdie´rentesmesuresde d´esordreetonse´lectionnelattributquipermetdeminimisercelui-ci.Danslapratique,les2 m´ethodeslesplusconnuessont: 1.LEntropiedelinformation(Shannon)[algosID3etC4.5propos´esparQuinlan] P n Entropie(X) =E[log2(P(Ci))] =P(Ci)log2(P(Ci)) i=1 2.IndicedeGini[algoCART,propos´eparBreiman] P P n n 2 Gini(X) = 1P(Ci) =P(Ci)(1P(Ci)) i=1i=1 2 avecP(Ci) =|Ci|/|X|uoseteeosnedx`eamlpleXncsoermrbelesdpCidxie´eruasse.esntascl Sionprendlexempledunprobl`emeo`uilnyaque2classes,+et-,etsilonconside`reque notreensembleded´epartXestconstitu´edepexemplesdelaclasse+etdenexemplesdela classe -, alors : p pn n E(X) =E(p, n) =[log+( )log( )] p+n p+n p+n p+n p2n2 Gini(X) = 1) ]+ ([( ) p+n p+n Ontpeu´egalementconsid´ererces2grandeurscommedesmesuresdelaquantite´dinforma-tionn´ecessairepourpouvoirrangercorrectementX.Danstoutlescas,pluscesvaleurssont importantes,etmoinsles´ele´mentssontordonne´s. Legaindinformationapport´eparchaqueattribut(A),calcule´andechoisirceluidontlegain estleplus´elev´e,estobtenucommesuit: P v ni+pi Gain(A)= F(X) - Reste(A) . avec :Reste(A) =F(ni, pi) i=1p+n o`uvAedensioest`utoerbmoneltaulavedReste(A)liutsere´eded´esordreqseltqaautnti a`traiterapre`savoirutilise´lattributAu`oteF´eepd´eronsiioncreelminisircuodrstcnofaltse attributs (Entropie ou Gini). Desexercicescorrig´esassocie´s`alutilisationdeces2grandeurspourlaconstructiondunAD sontdisponibles`aladressesuivante:http://www-desir.lip6.fr/ herpsonc/ia1.htm ~ 1.Cflerappeln˚2surlapprentissagesupervise´pourfaireladistinctionles2typesderreur 2.Ontrouve´egalementcetteformuleavecP(Ci|Xcleadaepal)`P(Ci).P(Ci|X) =P(CiX)/P(X) or CiXetX= Ω, on retombe donc surP(Ci)
2
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin