Den læring beslutningstre er en metode basert på bruken av et beslutningstre som en prediktiv modell. Det brukes spesielt i data mining og i maskinlæring .
I disse trestrukturene representerer bladene verdiene til målvariabelen, og grenene tilsvarer kombinasjoner av inngangsvariabler som fører til disse verdiene. I beslutningsanalyse kan et beslutningstreet brukes til å eksplisitt representere beslutningene som er gjort og prosessene som fører til dem. I læring og datautvinning beskriver et beslutningstreet dataene, men ikke selve beslutningene, treet vil bli brukt som utgangspunkt for beslutningsprosessen.
Det er en overvåket læringsteknikk : vi bruker et sett med data som vi vet verdien av målvariabelen for å bygge treet (såkalte merkede data), og deretter ekstrapolerer vi resultatene til datasettet. Beslutningstrær er blant de mest populære algoritmene innen maskinlæring .
Beslutningstrelæring er en klassisk metode innen maskinlæring . Hensikten er å lage en modell som forutsier verdien av en målvariabel ut fra verdien på flere inngangsvariabler.
En av inngangsvariablene er valgt ved hver indre node (eller intern, node som ikke er terminal) i treet i henhold til en metode som avhenger av algoritmen og som vil bli diskutert senere. Hver kant til en undernode tilsvarer et sett med verdier til en inngangsvariabel, slik at kantsettet til underordnede noder dekker alle mulige verdier for inngangsvariabelen.
Hvert blad (eller terminalnode på treet) representerer enten en verdi av målvariabelen, eller en sannsynlighetsfordeling av de forskjellige mulige verdiene for målvariabelen. Kombinasjonen av verdiene til inngangsvariablene er representert av banen fra roten til bladet.
Treet bygges vanligvis ved å skille datasettet i delmengder basert på verdien av en inngangskarakteristikk. Denne prosessen gjentas på hvert delsett oppnådd rekursivt, så det er en rekursiv partisjonering .
Rekursjonen fullføres ved en node, enten når alle delmengdene har samme verdi av målfunksjonen, eller når separasjonen ikke lenger forbedrer prediksjonen. Denne prosessen kalles top-down induksjon av beslutningstrær (TDIDT), det er en grådig algoritme siden vi på hver node av treet søker den optimale delingen, for å oppnå best mulig deling over hele beslutningstreet. Dette er den vanligste strategien for å lære beslutningstrær fra data.
I datamining kan beslutningstrær hjelpe til med beskrivelsen, kategoriseringen eller generaliseringen av et fast datasett .
Treningssettet tilbys vanligvis i form av poster av typen:
Variabelen angir målvariabelen som man søker å forutsi, klassifisere eller generalisere. Vektoren består av inngangsvariabler etc. som brukes til dette formålet.
Det er to hovedtyper av beslutningstrær i datautvinning:
Begrepet Classification and Regression Tree Analysis ( CART , after the acronym) er en generisk betegnelse som refererer til prosedyrene som tidligere er beskrevet og introdusert av Breiman et al. forskjeller, spesielt med hensyn til prosedyren som brukes til å bestemme forgreningsskiller.
Beslutningstrelæring består i å bygge et tre fra et treningssett som består av merkede tupler . Et avgjørelsestre kan beskrives som et dataflytdiagram (eller flytskjema ) der hver intern node beskriver en test på en læringsvariabel, hver gren representerer et testresultat, og hvert blad inneholder verdien av målvariabelen. klassifiseringstrær, en numerisk verdi for regresjonstrær).
Vanligvis blir algoritmene for å konstruere beslutningstrærne bygget ved å dele treet fra toppen til bladene ved å velge hvert inngangsvariabel som oppnår den beste delingen av settet med objekter, som beskrevet tidligere. For å velge separasjonsvariabelen på en node, tester algoritmene de forskjellige mulige inngangsvariablene og velger den som maksimerer et gitt kriterium.
Tilfelle av klassifiseringstrærNår det gjelder klassifiseringstrær, er dette et automatisk klassifiseringsproblem . Partisjonen evalueringskriteriet karakteriserer homogeniteten (eller gevinsten i homogenitet) av delsettene oppnådd ved deling av settet. Disse beregningene brukes på hver kandidatundermengde, og resultatene kombineres (f.eks. Gjennomsnitt) for å produsere et mål på kvaliteten på separasjonen.
Det er et stort antall slike kriterier, de mest brukte er Shannons entropi , Gini-mangfoldighetsindeksen og deres varianter.
Tilfelle av regresjonstrær
Når det gjelder regresjonstrær , kan samme separasjonsskjema brukes, men i stedet for å minimere klassifiseringsfeilfrekvensen, søker vi å maksimere mellomklassevariansen (å ha delmengder hvis verdier av målvariabelen er så spredt som mulig). Generelt bruker kriteriet chi-kvadrat- testen .
MerknaderEnkelte kriterier gjør det mulig å ta hensyn til det faktum at målvariabelen tar ordnede verdier, ved hjelp av passende tiltak eller heuristikk.
Hvert verdisett av segmenteringsvariabelen produserer en undernode. Læringsalgoritmene kan avvike fra antall produserte barn noder: noen (som CART ) produserer systematisk binære trær, og søker derfor den binære partisjonen som optimaliserer segmenteringskriteriet. Andre (som CHAID ) søker å lage de mest relevante grupperingene basert på statistiske kriterier. Avhengig av teknikken vil vi få mer eller mindre brede trær. For at metoden skal være effektiv, må det utvises forsiktighet for å unngå å dele opp dataene for ikke å produsere for små grupper av ansatte, som ikke tilsvarer noen statistisk virkelighet.
Når det gjelder kontinuerlige segmenteringsvariabler, må det valgte segmenteringskriteriet være tilstrekkelig. Generelt sorteres dataene i henhold til variabelen som skal behandles, deretter testes de forskjellige mulige avskjæringspunktene ved å evaluere kriteriet for hvert tilfelle, det optimale avskjæringspunktet vil være det som maksimerer segmenteringskriteriet.
Det er ikke alltid ønskelig i praksis å konstruere et tre der bladene tilsvarer perfekt homogene delmengder sett fra målvariabelen. Faktisk blir opplæringen utført på et utvalg som man håper å være representativt for en befolkning. Utfordringen med enhver læringsteknikk er å fange opp nyttig informasjon om befolkningens statistiske struktur, unntatt egenskapene som er spesifikke for datasettet som ble studert. Jo mer kompleks modellen (jo høyere treet, jo flere grener det har, jo flere blader har det), jo mer risikerer vi at denne modellen ikke kan ekstrapoleres til nye data. Det vil si å gi en konto av virkeligheten som man søker å gripe.
Spesielt, i ekstreme tilfeller der treet har så mange blader som det er individer i befolkningen (av poster i datasettet), gjør treet ingen feil på dette eksemplet siden det tiltrer alle dets egenskaper, men det kan ikke være generalisert til et annet utvalg. Dette problemet, kalt overtrening eller overskyting ( overmontering ), er et klassisk tema for maskinlæring og datautvinning.
Vi søker derfor å bygge et tre som er så lite som mulig, samtidig som vi sikrer best mulig ytelse. I henhold til prinsippet om parsimonium , jo mindre et tre, jo mer stabilt vil det være i fremtidige prognoser. Det er nødvendig å avveie ytelse og kompleksitet i modellene som brukes. For sammenlignbar ytelse, vil vi alltid foretrekke den enkleste modellen, hvis vi ønsker å kunne bruke denne modellen på nye prøver.
Problemet med overmontering av modellerFor å utføre ytelse / kompleksitet-voldgift av modellene som brukes, blir ytelsen til en eller flere modeller evaluert på grunnlag av dataene som ble brukt for konstruksjonen (treningsprøven (e)), men også på en (eller flere) valideringsprøve (r) : merkede data tilgjengelig, men som man frivillig bestemmer seg for ikke å bruke i konstruksjonen av modeller.
Disse dataene blir behandlet som testdataene, stabiliteten til ytelsen til modellene på disse to prøvene vil gjøre det mulig å bedømme overmontering og derfor evnen til å bli brukt med en kontrollert risiko for feil under reelle forhold der dataene er ikke kjent på forhånd.
I grafen motsatt observerer vi utviklingen av justeringsfeilen til et beslutningstre som en funksjon av antall blader på treet (som her måler kompleksiteten). Vi bemerker at hvis feilen stadig avtar på læringsprøven, fra et visst nivå av kompleksitet, beveger modellen seg bort fra virkeligheten, en virkelighet som vi søker å estimere på valideringsprøven. (Referert til som testprøven i grafen) .
Når det gjelder beslutningstrær, har flere typer algoritmiske løsninger blitt vurdert for å prøve å unngå så mye som mulig overlæring av modellene: teknikkene for pre- eller post-beskjæring av trær.
Noen statistiske teorier søker å finne det optimale mellom feilen som ble gjort på treningsprøven og den som ble gjort i testprøven. Den teori Vapnik-Chervonenkis Strukturert risikominimaliseringstiltak (eller SRM), benytter en variabel kalt dimensjon VC, for å bestemme det optimale for en modell. Den kan derfor brukes til å generere modeller som sikrer det beste kompromisset mellom kvalitet og robusthet i modellen.
Disse algoritmiske løsningene er komplementære til de sammenlignende ytelses- og stabilitetsanalysene som er utført på trenings- og valideringsprøvene.
ForbeskjæringDen første strategien som kan brukes for å unngå overlæring av beslutningstrær består i å foreslå stoppekriterier i utvidelsesfasen. Dette er prinsippet for forhåndsbeskjæring. Når gruppen er for liten i størrelse, eller når homogeniteten til en delmengde har nådd et tilstrekkelig nivå, anses det at det ikke lenger er nødvendig å skille prøven. Et annet kriterium som ofte forekommer i denne sammenhengen er bruken av en statistisk test for å evaluere om segmenteringen introduserer en betydelig innspill av informasjon for prediksjon av målvariabelen.
EtterbeskjæringDen andre strategien består i å konstruere treet i to trinn: vi produserer først treet hvis bladene er så homogene som mulig i en utvidelsesfase, ved å bruke en første brøkdel av dataprøven (prøve d lærer ikke å forveksles med totaliteten av prøven, kalt på engelsk voksende sett for å fjerne tvetydigheten), reduseres treet ved å stole på en annen brøkdel av dataene for å optimalisere ytelsen til treet er etterbeskjæringsfasen. Avhengig av tilfelle er denne andre delen av dataene betegnet med begrepet valideringsprøve eller testprøve, og innfører forvirring med prøven som brukes til å måle ytelsen til modellene. Begrepet beskjæringsprøve gjør det mulig å betegne det uten tvetydighet, det er den direkte oversettelsen av det engelske navnet beskjæringssett .
Dataene som er tilgjengelige er ofte ufullstendige, i den forstand at bare en del av inngangsvariablene er tilgjengelige for en post. Flere muligheter er mulige i dette tilfellet:
Når det gjelder klassifiseringstrær, må tildelingsregelen spesifiseres i arkene når treet er konstruert. Hvis bladene er homogene, er det ingen tvetydighet. Hvis dette ikke er tilfelle, er en enkel regel å bestemme arkklassen i henhold til majoritetsklassen, den som er mest representert.
Denne veldig enkle teknikken er optimal i tilfelle der dataene kommer fra et ikke-partisk tilfeldig utvalg i befolkningen; matrisen for kostnadene ved feilallokering er enhetlig (symmetrisk): hensiktsmessig fordeling til null kostnad, og feil fordeling av kostnader 1 uansett tilfelle. Utenfor dette rammeverket er majoritetsregelen ikke nødvendigvis berettiget, men er lett å bruke i praksis.
Noen teknikker, kalt settmetoder ( alle metoder ), forbedrer prediksjonens kvalitet eller pålitelighet ved å bygge flere beslutningstrær fra dataene:
Beslutningstrær kombineres noen ganger med hverandre eller med andre læringsteknikker: diskriminerende analyse, logistiske regresjoner, lineære regresjoner, nevrale nettverk ( multilayer perceptron , radial basis function network ) eller andre.
Prosedyrer for å samle ytelsen til de forskjellige modellene som brukes (for eksempel avgjørelser etter konsensus) er satt i verk for å oppnå maksimal ytelse, mens man kontrollerer kompleksitetsnivået til modellene som brukes.
Sammenlignet med andre data mining metoder har beslutningstrær flere fordeler:
På den annen side har den visse ulemper:
I et beslutningstreet bruker alle stier fra rot til blader AND- kontakten . I en avgjørelsesgraf kan vi også bruke ELLER- kontakten til å koble til flere baner ved hjelp av MML ( Minimum message length ). Generelt produserer beslutningsgrafer grafer med færre blader enn beslutningstrær.
Av evolusjonære algoritmer brukes for å unngå separasjon som fører til lokal optimalitet.
Man kan også prøve treet ved hjelp av MCMC- metoder i et Bayesisk paradigme .
Treet kan bygges ved å bruke en nedenfra og opp (nedenfra og opp) tilnærming.
Det er flere algoritmer for å bygge beslutningstrær, inkludert:
ID3 og CART ble oppfunnet hver for seg i tiårene 1970-1980, men bruker lignende tilnærminger for å lære beslutningstrær fra læringssettet.
Alle disse algoritmene er preget av segmenteringskriteriene som brukes, av beskjæringsmetodene som er implementert, ved å håndtere de manglende dataene i prediktorene.
Mange data mining programvare tilbyr biblioteker for å implementere en eller flere beslutningstreet læringsalgoritmer. For eksempel inneholder Open Source R- programvaren flere implementeringer av CART, for eksempel rpart, party og randomForest, den gratis programvaren Weka og Orange (og dens orngTree-modul) eller det gratis Python-biblioteket scikit-learning ; men også Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server [1] .