Arbres de décision : Motivation, algorithmes et applications pratiques

Apprentissage,r seauxdeneuronesetmod lesgraphiques(RCP209)Arbresded cisionMarinFERECATU([email protected])http://cedric.cnam.fr/vertigo/Cours/ml2/D partementInformatiqueConservatoireNationaldesArts&M tiers,Paris,FranceObjectifsetcontenudelenseignement1/34Planducours2Objectifsetcontenudelenseignement3Arbresded cision(motivation,d finitions)4Apprentissageavecarbresded cision5Impl mentation6ExtensionsObjectifsetcontenudelenseignement2/34ObjectifLaraisond tredesstatistiques,cestdevousdonnerraison.AbeBurrowsArbresded cision:motivation,d finition,exemplesApprentissageavecdearbresded cision:classification,r gressionImpl mentationID3,C4.5,C5.0CARTExtensionsGraphesded cisionBaggingdecisiontrees,BoostedtreesForetsal atoires(randomforrests)prochaines anceArbresded cision(motivation,d finitions)2/34Planducours2Objectifsetcontenudelenseignement3Arbresded cision(motivation,d finitions)4Apprentissageavecarbresded cision5Impl mentation6ExtensionsArbresded cision(motivation,d finitions)3/34Arbresded cision(AD)Arbresded cision:Outilutilis danslexplorationdedonn esetinformatiqued cisionnelle.Repr sentationhi rarchiquedelastructuredesdonn essousformedess quencesded cision(tests)envuedelapr dictiondunr sultatouduneclasse.Probl me r soudre:commentr partirunepopulationdindividus(e.g.clients,produit,utilisateursetc.)engroupeshomog nesselonunensembledevariablesdiscriminantes(e.g. ge,tempspass surunsiteWeb,etc.)etenfonctiondunobjectiffix (variabledesortie;parexemple:chiffredaffaires,probabilit decliquersurunepublicit ,etc.)Arbresded cision(motivation,d finitions)4/34Arbresded cision:exemplesSource:https://maximilienandile.github.ioArbresded cision(motivation,d finitions)5/34Arbresded cision:exemplesSource:http://www.labortho.fr,https://jeromechoain.files.wordpress.comArbresded cision(motivation,d finitions)6/34Arbresded cision:exemplesSurviedepassagerssurleTitanic(https://en.wikipedia.org).Apprentissageavecarbresded cision6/34Planducours2Objectifsetcontenudelenseignement3Arbresded cision(motivation,d finitions)4Apprentissageavecarbresded cision5Impl mentation6ExtensionsApprentissageavecarbresded cision7/34Apprentissageavecarbresded cisionRepr sentation:ChaquenSudinternecorrespond unattributChaquenSudtestelattributcorrespondantetg n replusieursbranchesVariablecat gorielle:unebrancheparvaleurdelattributVariablenum rique:testsurvaleurLesfeuillessp cifientlesclassesPrincipedelaconstruction:Larbreestconstruitparpartitionr cursivedelabasedapprentissageenfonctiondelavaleurdelattributtest chaqueit ration(top-downinduction).Leprocessussarr tequandles l mentsdunnSudontlam mevaleurpourlavariablecible(homog n it ).Apprentissageavecarbresded cision8/34Apprentissageavecarbresded cisionGauche:divisiondelespaceimpossible obtenirparpartitionr cursivesurlesattributs.Milieuetdroite:Partitionr cursivedelespaceetarbreobtenu.(source:wikimedia.org)Apprentissageavecarbresded cision9/34Apprentissageavecarbresded cisionGauche:s parationdeclassesparpartitionit rativedesvariables.Droite:s parationparcombinaisonlin airedeplusieursvariables.Apprentissageavecarbresded cision10/34Apprentissageavecarbresded cisionDonn esdentr e:pointsdansunfeaturespacesp cifi parsesattributsvariablescat goriellesounum riquesCible:classe(classification)ouvaleur(r gression)Apprentissageavecarbresded cision11/34Apprentissageavecarbresded cisionImpl mentation11/34Planducours2Objectifsetcontenudelenseignement3Arbresded cision(motivation,d finitions)4Apprentissageavecarbresded cision5Impl mentation6ExtensionsImpl mentation12/34ID3(IterativeDichotomiser3)Quinlan,J.R.,InductionofDecisionTrees.Mach.Learn.1,(Mar.1986),pp.81-106SunnSudinterne:PartitionnerSsurlesvaleursdelacibleenngroupes:C1,...,Cmpi:probabilit quun l mentdeSseretrouvedansCi(piH|Ci|/|S|)H(S)=Pm1=1pilog(pi)entropiedeSH(S)=0siSesthomog ne(tousles l mentssontdanslam meclasse:unpi=1,lereste 0)H(S)=maxsitouslesgroupesCiontlam metaille(p1= =pn=1/n)Impl mentation13/34ID3(IterativeDichotomiser3)Quinlan,J.R.,InductionofDecisionTrees.Mach.Learn.1,(Mar.1986),pp.81-106SunnSudinterne:PartitionnerSsurlesvaleursdelattributaennsous-groupes:S1,...,Snpi:laprobabilit quun l mentdeSappartient Si(piH|Si|/|S|)GI(S;a)=H(S)Pn1=1piH(Si)legaindinformationsurlattributaAlgorithme:Calculerlentropiedechaqueattributpasencoreutilis ChoisirlattributdegaindinformationmaximalCr erunnSudtest(d cision)surcetattributetlessous-nSudscorrespondantsR currencesurlesnSudsrestantsImpl mentation14/34ID3ExempleImpl mentation15/34ID3ExempleImpl mentation16/34ID3ExempleImpl mentation17/34ID3ExempleImpl mentation18/34ID3ExempleImpl mentation19/34ID3ExempleImpl mentation20/34ID3ExempleImpl mentation21/34ID3ExempleImpl mentation22/34ID3(IterativeDichotomiser3)Sortiedelar cursivit :Tousles l mentsdeSsontdanslam meclasse(H(S)=0):SdevientnSudfeuillePasdattributsnonutilis s:nSudfeuillesurleclassemajoritaireS=:nSudfeuillesurleclassemajoritaireduparent(cecasestn cessairepourlaclassificationdenouveau chantillons)Probl mes:Solutionglobalenongarantie(optimumlocal,am lioration:backtracking)Over-fitting(pour viter:pr f rerlesarbresdetailler duite)Pasefficacepourdesdonn esnum riquescontinuesImpl mentation23/34C4.5(IterativeDichotomiser4.5)C4.5:extensiondeID3Lecrit rededivisionestlegaindinformationnormalis maximal(diff rencedentropieavantetapr sladivision)Chaqueattributpeutavoirunpoids(co t)TraitementdevariablescontinuesencherchantdesseuilsquimaximiselegaindinformationTraitementdevaleursmanquantes taped lagageapr slacr ationpourremplacerdesbranchesinutilespardesfeuillesC5.0:extensiondeID4.5Vitesseetutilisationm moireArbrespluspetitsPond rationdescaseterreursdeclassificationImpl mentation24/34ClassificationandRegressionTrees(CART)Breiman,Friedman,Olshen,Stone,Classificationandregressiontrees,Monterey,Brooks/ColeAdvancedBooks,1984.CART:Arbresdeclassificationetr gressionCARTposeseulementdequestionstestbinaires(arbresbinaires)FonctionneaussipourdesattributsauxvaleurscontinuesCARTcherchetouslesattributsettouslesseuilspourtrouverceluiquidonnelameilleurehomog n it dud coupageImpl mentation25/34ClassificationandRegressionTrees(CART)UnnoeudinterneSestcoup surlattributj,seuilaj:Sous-noeudgaucheSg(pgH|Sg|/|S|)etSous-noeuddroitSd(pdH|Sd|/|S|)SoitI(S)lafonctiondelimpuret deSparrapport laclassecible.CART tudielechangementdelimpuret parrapportauseuiletpourtouslesattributs:E =pgI(Sg)+pdI(Sd)I(S)=I(S)E[I(Sgd)=I(S)pgI(Sg)pdI(Sd)Probl medoptimisation:argmaxj;ajI(S)Impl mentation26/34ClassificationandRegressionTrees(CART)Pb.declassificationoptimiselindex(ouimpuret )deGini:Lavraisemblancequun l mentdunSudseraincorrectementlabellis paruntirageal atoirequirespectelaloistatistiquedelacibleestim danslenSud.SunnSudinterne:PartitionnerSsurlesvaleursdelacibleenngroupes:C1,...,Cmpi:probabilit estim quun l mentdeSseretrouvedansCi(piH|Ci|/|S|)IG(S)=Pm1=1pi(1pi)=Pm1=1(pip2i)=1Pm1=1p2iIG(S)=Pi6=jpipjindexdeGiniIG(S)=0siSesthomog ne(tousles l mentssontdanslam meclasseimpuret dugroupenulle)Impl mentation27/34ClassificationandRegressionTrees(CART)Classification:autrestypesdemesuresdimpuret :H(s)=Pipilog(pi)(entropie)E(s)=1maxipi(erreurdeclassification)Comparaisonmesuresdimpuret desnoeuds.Impl mentation28/34ClassificationandRegressionTrees(CART)Pb.der gressionoptimiseler siduquadratiquemoyen:minimiselavariancemoyennedesgroupes.argminj;ajpgVar(Sg)+pdVar(Sd)Classificationdenouvellesdonn es:ParcoursdelarbrepourarriverdansunefeuilleLaclassedominante(majoritaire)danscenoeuddonnelaclassificationPourlar gression:onconsid relesvaleursdominantesdanslesfeuillesAvantagesCART:Formenonparam triquePasdes lectiondevariablesn cessaireInvariableauxtransformationmonotonesdesattributsBonnegestiondesouliersImpl mentation29/34ClassificationandRegressionTrees(CART)Impl mentation30/34ClassificationandRegressionTrees(CART)Sur-apprentissage:Pourdespb.non-lin airesCARTpeutdonnerdesarbresdegrandetaillesavecbeaucoupdefeuillesquiontpeud l ments(souventunseul)Lespremierssplitssontg n ralementlesplusimportantsetlesmoinsd pendantsdel chantillon,tandisquelessuivantsd criventdesparticularit splussubtiles,pouvant trepropres l chantillon.Ilestdoncsouhaitable,afindegarderunniveaucorrectdeg n ralit ,d laguerlarbreconstruit.Untauxderreurdepr dictionparvalidationcrois eestcalcul pourdiff rentestaillesdelarbre(i.e.,diff rentsnombresdefeuillesterminales):larbreestalors laguerauniveauoffrantlerreurminimale.Impl mentation31/34ClassificationandRegressionTrees(CART)Tauxderreurs:constructionversustest.Impl mentation32/34ClassificationandRegressionTrees(CART)Gestiondesdonn esmanquantes:Surrogatesplitsouvariables-substituts:lop rationcontinuesurunautreattributqui, lapprentissage,adonn unsplitsimilaireExtensions32/34Planducours2Objectifsetcontenudelenseignement3Arbresded cision(motivation,d finitions)4Apprentissageavecarbresded cision5Impl mentation6ExtensionsExtensions33/34ExtensionsBaggingdecisiontrees:constructionplusieursarbresparre- chantillonnageavecremise;priseded cisionparvoteconsensuelFor tsdarbresd cisionnels(oufor tsal atoires):apprentissagesurdemultiplesarbresded cisionentra n ssurdessous-ensemblesdedonn esl g rementdiff rents.Extensions34/34R f rencesLivresetarticles:Rokach,Lior;Maimon,Dataminingwithdecisiontrees:theoryandapplications.WorldScientificPubCoInc.,2008Quinlan,InductionofDecisionTrees.MachineLearning1:81-106,KluwerAcademicPublishers1986Hastie,Tibshirani,Friedman,Theelementsofstatisticallearning:Datamining,inference,andprediction.NewYork:SpringerVerlag,2006Breiman,Friedman,Olshen,Stone,Classificationandregressiontrees.Monterey,CA:WadsworthandBrooks/ColeAdvancedBooks1984RomanTimofeev,ClassificationandRegressionTrees(CART)TheoryandApplications,MasterThesis,Universit Humbold,Berlin,2004