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,FranceObjectifsetcontenudel’enseignement1/34Planducours2Objectifsetcontenudel’enseignement3Arbresdedécision(motivation,définitions)4Apprentissageavecarbresdedécision5Implémentation6ExtensionsObjectifsetcontenudel’enseignement2/34Objectif“Laraisond’êtredesstatistiques,c’estdevousdonnerraison.”—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/34Planducours2Objectifsetcontenudel’enseignement3Arbresdedécision(motivation,définitions)4Apprentissageavecarbresdedécision5Implémentation6ExtensionsArbresdedécision(motivation,définitions)3/34Arbresdedécision(AD)Arbresdedécision:Outilutilisédansl’explorationdedonnéesetinformatiquedécisionnelle.Représentationhiérarchiquedelastructuredesdonnéessousformedesséquencesdedécision(tests)envuedelaprédictiond’unrésultatoud’uneclasse.Problèmeàrésoudre:commentrépartirunepopulationd’individus(e.g.clients,produit,utilisateursetc.)engroupeshomogènesselonunensembledevariablesdiscriminantes(e.g.âge,tempspassésurunsiteWeb,etc.)etenfonctiond’unobjectiffixé(variabledesortie;parexemple:chiffred’affaires,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/34Planducours2Objectifsetcontenudel’enseignement3Arbresdedécision(motivation,définitions)4Apprentissageavecarbresdedécision5Implémentation6ExtensionsApprentissageavecarbresdedécision7/34ApprentissageavecarbresdedécisionReprésentation:ChaquenœudinternecorrespondàunattributChaquenœudtestel’attributcorrespondantetgénèreplusieursbranchesVariablecatégorielle:unebrancheparvaleurdel’attributVariablenumérique:testsurvaleurLesfeuillesspécifientlesclassesPrincipedelaconstruction:L’arbreestconstruitparpartitionrécursivedelabased’apprentissageenfonctiondelavaleurdel’attributtestéàchaqueitération(top-downinduction).Leprocessuss’arrêtequandlesélémentsd’unnœudontlamêmevaleurpourlavariablecible(homogénéité).Apprentissageavecarbresdedécision8/34ApprentissageavecarbresdedécisionGauche:divisiondel’espaceimpossibleàobtenirparpartitionrécursivesurlesattributs.Milieuetdroite:Partitionrécursivedel’espaceetarbreobtenu.(source:wikimedia.org)Apprentissageavecarbresdedécision9/34ApprentissageavecarbresdedécisionGauche:séparationdeclassesparpartitionitérativedesvariables.Droite:séparationparcombinaisonlinéairedeplusieursvariables.Apprentissageavecarbresdedécision10/34ApprentissageavecarbresdedécisionDonnéesd’entrée:pointsdansun”featurespace”spécifiéparsesattributsvariablescatégoriellesounumériquesCible:classe(classification)ouvaleur(régression)Apprentissageavecarbresdedécision11/34ApprentissageavecarbresdedécisionImplémentation11/34Planducours2Objectifsetcontenudel’enseignement3Arbresdedécision(motivation,définitions)4Apprentissageavecarbresdedécision5Implémentation6ExtensionsImplémentation12/34ID3(IterativeDichotomiser3)Quinlan,J.R.,InductionofDecisionTrees.Mach.Learn.1,(Mar.1986),pp.81-106Sunnœudinterne:PartitionnerSsurlesvaleursdelacibleenngroupes:C1,...,Cmpi:probabilitéqu’unélémentdeSseretrouvedansCi(pi≈|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-106Sunnœudinterne:PartitionnerSsurlesvaleursdel’attributaennsous-groupes:S1,...,Snpi:laprobabilitéqu’unélémentdeSappartientàSi(pi≈|Si|/|S|)GI(S;a)=H(S)−Pn1=1piH(Si)legaind’informationsurl’attributaAlgorithme:Calculerl’entropiedechaqueattributpasencoreutiliséChoisirl’attributdegaind’informationmaximalCréerunnœudtest(décision)surcetattributetlessous-nœudscorrespondantsRécurrencesurlesnœudsrestantsImplé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):SdevientnœudfeuillePasd’attributsnonutilisés:nœudfeuillesurleclassemajoritaireS=∅:nœudfeuillesurleclassemajoritaireduparent(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èrededivisionestlegaind’informationnormalisémaximal(différenced’entropieavantetaprèsladivision)Chaqueattributpeutavoirunpoids(coût)Traitementdevariablescontinuesencherchantdesseuilsquimaximiselegaind’informationTraitementdevaleursmanquantesÉ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ésurl’attributj,seuilaj:Sous-noeudgaucheSg(pg≈|Sg|/|S|)etSous-noeuddroitSd(pd≈|Sd|/|S|)SoitI(S)lafonctiondel’impuretédeSparrapportàlaclassecible.CARTétudielechangementdel’impuretéparrapportauseuiletpourtouslesattributs:E[I(Sgd)]=pgI(Sg)+pdI(Sd)∆I(S)=I(S)−E[I(Sgd)=I(S)−pgI(Sg)−pdI(Sd)Problèmed’optimisation:argmaxj;aj∆I(S)Implémentation26/34ClassificationandRegressionTrees(CART)Pb.declassificationoptimisel’index(ouimpureté)deGini:Lavraisemblancequ’unélémentdunœudseraincorrectementlabelliséparuntiragealéatoirequirespectelaloistatistiquedelacibleestimédanslenœud.Sunnœudinterne:PartitionnerSsurlesvaleursdelacibleenngroupes:C1,...,Cmpi:probabilitéestiméqu’unélémentdeSseretrouvedansCi(pi≈|Ci|/|S|)IG(S)=Pm1=1pi(1−pi)=Pm1=1(pi−p2i)=1−Pm1=1p2iIG(S)=Pi6=jpipjindexdeGiniIG(S)=0siSesthomogène(touslesélémentssontdanslamêmeclasse—impuretédugroupenulle)Implémentation27/34ClassificationandRegressionTrees(CART)Classification:autrestypesdemesuresd’impureté:H(s)=−Pipilog(pi)(entropie)E(s)=1−maxipi(erreurdeclassification)Comparaisonmesuresd’impuretédesnoeuds.Implémentation28/34ClassificationandRegressionTrees(CART)Pb.derégressionoptimiselerésiduquadratiquemoyen:minimiselavariancemoyennedesgroupes.argminj;ajpgVar(Sg)+pdVar(Sd)Classificationdenouvellesdonnées:Parcoursdel’arbrepourarriverdansunefeuilleLaclassedominante(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’élaguerl’arbreconstruit.Untauxd’erreurdeprédictionparvalidationcroiséeestcalculépourdifférentestaillesdel’arbre(i.e.,différentsnombresdefeuillesterminales):l’arbreestalorsàélaguerauniveauoffrantl’erreurminimale.Implémentation31/34ClassificationandRegressionTrees(CART)Tauxd’erreurs:constructionversustest.Implémentation32/34ClassificationandRegressionTrees(CART)Gestiondesdonnéesmanquantes:Surrogatesplitsouvariables-substituts:l’opérationcontinuesurunautreattributqui,àl’apprentissage,adonnéunsplitsimilaireExtensions32/34Planducours2Objectifsetcontenudel’enseignement3Arbresdedécision(motivation,définitions)4Apprentissageavecarbresdedécision5Implémentation6ExtensionsExtensions33/34ExtensionsBaggingdecisiontrees:constructionplusieursarbresparre-échantillonnageavecremise;prisededécisionparvoteconsensuelForêtsd’arbresdé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