Rappel de cours sur les arbres de décision
2
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
2
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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
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[log2(P(Ci))] =−P(Ci)∗log2(P(Ci)) i=1 2.IndicedeGini[algoCART,propos´eparBreiman] P P n n 2 Gini(X) = 1−P(Ci) =P(Ci)∗(1−P(Ci)) i=1i=1 2 avecP(Ci) =|Ci|/|X|uoseteeosnedx`eamlp’leXncsoermrbelesdpCidxffie´eruasse.esntascl Sionprendl’exempled’unprobl`emeo`uiln’yaque2classes,+et-,etsil’onconside`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´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 ni+pi Gain(A)= F(X) - Reste(A) . avec :Reste(A) =∗F(ni, pi) i=1p+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(Ci|Xcleadaepal)`P(Ci).P(Ci|X) =P(Ci∩X)/P(X) or Ci⊂XetX= Ω, on retombe donc surP(Ci)
2
