Den beslutning læring træ er en metode baseret på anvendelsen af en beslutningstræ som en prædiktiv model. Det bruges især i datamining og i maskinlæring .
I disse træstrukturer repræsenterer bladene værdierne for målvariablen, og grenene svarer til kombinationer af inputvariabler, der fører til disse værdier. I beslutningsanalyse kan et beslutningstræ bruges til eksplicit at repræsentere de trufne beslutninger og de processer, der fører til dem. I læring og datamining beskriver et beslutningstræ dataene, men ikke selve beslutningerne, træet vil blive brugt som udgangspunkt for beslutningsprocessen.
Det er en overvåget læringsteknik : vi bruger et sæt data, som vi kender værdien af målvariablen for at opbygge træet (såkaldte mærkede data), så ekstrapolerer vi resultaterne til datasættet. Beslutningstræer er blandt de mest populære algoritmer inden for maskinindlæring .
Beslutningstræindlæring er en klassisk metode til maskinlæring . Dens formål er at oprette en model, der forudsiger værdien af en målvariabel ud fra værdien af flere inputvariabler.
En af inputvariablerne er valgt ved hvert indre knudepunkt (eller internt knudepunkt, som ikke er terminal) i træet ifølge en metode, der afhænger af algoritmen, og som vil blive diskuteret senere. Hver kant til en undernode svarer til et sæt værdier for en inputvariabel, således at kantsættet til undernoderne dækker alle mulige værdier for inputvariablen.
Hvert blad (eller terminalens knudepunkt i træet) repræsenterer enten en værdi af målvariablen eller en sandsynlighedsfordeling af de forskellige mulige værdier for målvariablen. Kombinationen af værdierne for inputvariablerne er repræsenteret af stien fra roden til bladet.
Træet er generelt bygget ved at adskille datasættet i delmængder baseret på værdien af en inputkarakteristik. Denne proces gentages på hvert delsæt, der opnås rekursivt, så det er en rekursiv partitionering .
Rekursionen afsluttes ved en node, enten når alle undergrupper har den samme værdi af målfunktionen, eller når adskillelsen ikke længere forbedrer forudsigelsen. Denne proces kaldes top-down induktion af beslutningstræer (TDIDT), det er en grådig algoritme, da vi på hver node af træet søger den optimale deling for at opnå den bedst mulige deling på hele beslutningstræet. Dette er den mest almindelige strategi for at lære beslutningstræer ud fra data.
I datamining kan beslutningstræer hjælpe med beskrivelsen, kategoriseringen eller generaliseringen af et fast datasæt .
Træningssættet leveres normalt i form af optegnelser af typen:
Variablen betegner den målvariabel, som man søger at forudsige, klassificere eller generalisere. Vektoren består af inputvariabler mv. der bruges til dette formål.
Der er to hovedtyper af beslutningstræer i datamining:
Udtrykket Klassifikation og regressionstræanalyse ( CART , efter akronymet) er et generisk udtryk, der henviser til de procedurer, der tidligere er beskrevet og introduceret af Breiman et al.. De træer, der anvendes i tilfælde af regression og i tilfælde af klassificering, har ligheder, men også forskelle, især med hensyn til den procedure, der anvendes til at bestemme forgreningsadskillelserne.
Beslutningstræindlæring består i at bygge et træ fra et træningssæt, der består af mærkede tupler . Et beslutningstræ kan beskrives som et dataflowdiagram (eller rutediagram ), hvor hver intern node beskriver en test på en læringsvariabel, hver gren repræsenterer et resultat af testen, og hvert blad indeholder værdien af målvariablen. (En klasse tag for klassificeringstræer, en numerisk værdi for regressionstræer).
Normalt bygges algoritmerne til opbygning af beslutningstræerne ved at dividere træet fra toppen til bladene ved ved hvert trin at vælge en inputvariabel, der opnår den bedste deling af objektsættet som beskrevet tidligere. For at vælge separationsvariablen på en knude tester algoritmerne de forskellige mulige inputvariabler og vælger den, der maksimerer et givet kriterium.
Tilfælde af klassificeringstræerI tilfælde af klassificeringstræer er dette et automatisk klassificeringsproblem . Partitionevalueringskriteriet karakteriserer homogeniteten (eller gevinsten i homogenitet) af de undergrupper, der opnås ved opdeling af sættet. Disse målinger anvendes til hver kandidatsubmængde, og resultaterne kombineres (f.eks. Gennemsnit) for at producere et mål for kvaliteten af adskillelsen.
Der er et stort antal af sådanne kriterier, de mest anvendte er Shannons entropi , Gini-mangfoldighedsindekset og deres varianter.
Tilfælde af regressionstræer
I tilfælde af regressionstræer kan det samme separationsskema anvendes, men i stedet for at minimere klassificeringsfejlfrekvensen forsøger vi at maksimere inter-klassevarianten (at have undergrupper, hvis værdier af målvariablen er så spredt som muligt). Generelt bruger kriteriet chi-kvadrat- testen .
BemærkningerVisse kriterier gør det muligt at tage højde for, at målvariablen tager ordrede værdier ved hjælp af passende mål eller heuristik.
Hvert sæt værdier i segmenteringsvariablen producerer en undernode. Læringsalgoritmerne kan variere på antallet af producerede underordnede noder: nogle (såsom CART ) producerer systematisk binære træer og søger derfor den binære partition, som optimerer segmenteringskriteriet. Andre (som CHAID ) søger at lave de mest relevante grupperinger baseret på statistiske kriterier. Afhængigt af teknikken opnår vi mere eller mindre brede træer. For at metoden skal være effektiv, skal man være forsigtig med at undgå for stor opdeling af dataene for ikke at producere for små grupper af ansatte, som ikke svarer til nogen statistisk virkelighed.
I tilfælde af kontinuerlige segmenteringsvariabler skal det valgte segmenteringskriterium være tilstrækkeligt. Generelt sorteres dataene efter den variabel, der skal behandles, så testes de forskellige mulige afskæringspunkter ved at evaluere kriteriet for hvert tilfælde, det optimale afskæringspunkt er det, der maksimerer segmenteringskriteriet.
I praksis er det ikke altid ønskeligt at bygge et træ, hvis blade svarer til perfekt homogene undergrupper set fra målvariablen. Faktisk udføres uddannelsen på en prøve, som man håber at være repræsentativ for en befolkning. Udfordringen ved enhver læringsteknik er at indfange nyttige oplysninger om befolkningens statistiske struktur eksklusive de specifikke egenskaber for det undersøgte datasæt. Jo mere kompleks modellen er (jo større træet er, jo flere grene har den, jo flere blade har den), jo mere løber vi risikoen for, at denne model ikke kan ekstrapoleres til nye data. Det vil sige at give en konto af den virkelighed, som man søger at forstå.
Især i det ekstreme tilfælde, hvor træet har så mange blade, som der er individer i befolkningen (af poster i datasættet), laver træet ingen fejl i denne prøve, da det gifter sig med alle dets egenskaber, men det kan ikke være generaliseret til en anden prøve. Dette problem, kaldet overtræning eller overskridelse ( overmontering ), er et klassisk emne inden for maskinlæring og datamining.
Vi søger derfor at bygge et træ, der er så lille som muligt og samtidig sikre den bedst mulige ydeevne. Efter princippet om parsimonium , jo mindre et træ, jo mere stabilt vil det være i dets fremtidige prognoser. Det er nødvendigt at foretage en afvejning mellem ydeevne og kompleksitet i de anvendte modeller. For sammenlignelig ydelse foretrækker vi altid den enkleste model, hvis vi vil være i stand til at bruge denne model på nye prøver.
Problemet med overmontering af modellerFor at udføre ydeevne / kompleksitetsvoldgift af de anvendte modeller evalueres ydeevnen for en eller flere modeller på de data, der er brugt til konstruktionen (træningseksemplet (erne)), men også på en (eller flere) valideringseksempler : tilgængelige mærkede data, men som man frivilligt beslutter ikke at bruge i konstruktionen af modeller.
Disse data behandles som testdataene, stabiliteten af ydeevnen af modellerne på disse to typer prøver gør det muligt at bedømme dets overmontering og derfor dets evne til at blive brugt med en kontrolleret risiko for fejl under reelle forhold, hvor dataene er ikke kendt på forhånd.
I den modsatte graf observerer vi udviklingen af en beslutningstræs justeringsfejl som en funktion af antallet af blade på træet (som her måler kompleksiteten). Vi bemærker, at hvis fejlen konstant falder på indlæringsprøven, fra et bestemt niveau af kompleksitet, bevæger modellen sig væk fra virkeligheden, en virkelighed, som vi prøver at estimere på valideringsprøven. (Kaldet testprøven i grafen ).
I tilfælde af beslutningstræer er flere typer algoritmiske løsninger blevet overvejet for at forsøge at undgå så meget som muligt overlæring af modellerne: teknikkerne til for- eller efterbeskæring af træer.
Nogle statistiske teorier søger at finde det optimale mellem den fejl, der er foretaget i træningsprøven, og den, der er lavet i testprøven. Den teori Vapnik-Chervonenkis Structured Risk Minimering (eller SRM), anvender en variabel kaldet dimension VC, at bestemme det optimale af en model. Det kan derfor bruges til at generere modeller, der sikrer det bedste kompromis mellem kvalitet og robusthed i modellen.
Disse algoritmiske løsninger supplerer de sammenlignende præstations- og stabilitetsanalyser udført på trænings- og valideringsprøverne.
ForbeskæringDen første strategi, der kan bruges til at undgå beslutningstagningstræer med overlæring, består i at foreslå stopkriterier i ekspansionsfasen. Dette er princippet om forbeskæring. Når gruppen er for lille i størrelse, eller når homogeniteten af en delmængde har nået et tilstrækkeligt niveau, anses det for ikke længere nødvendigt at adskille prøven. Et andet kriterium, der ofte optræder i denne sammenhæng, er brugen af en statistisk test til at evaluere, om segmenteringen introducerer et signifikant input af information til forudsigelse af målvariablen.
Efter beskæringDen anden strategi består i at bygge træet i to faser: vi fremstiller først træet, hvis blade er så homogene som muligt i en ekspansionsfase ved hjælp af en første brøkdel af dataprøven (prøve d 'lærer ikke at forveksles med totaliteten af prøven, kaldet på engelsk voksende sæt for at fjerne tvetydigheden), reduceres træet, afhængigt af en anden brøkdel af dataene for at optimere træets ydeevne er efterbeskæringsfasen. Afhængigt af tilfældet er denne anden del af dataen betegnet med udtrykket valideringsprøve eller testprøve, hvilket indfører forveksling med den prøve, der bruges til at måle ydeevnen for modellerne. Udtrykket beskæringsprøve gør det muligt at betegne det uden tvetydighed, det er den direkte oversættelse af det engelske navn beskæringssæt .
De tilgængelige data er ofte ufuldstændige i den forstand, at kun en del af inputvariablerne er tilgængelige for en post. Flere muligheder er mulige i dette tilfælde:
I tilfælde af klassificeringstræer skal tildelingsreglen specificeres i arkene, når træet er konstrueret. Hvis bladene er homogene, er der ingen tvetydighed. Hvis dette ikke er tilfældet, er en simpel regel at beslutte klassen på arket efter majoritetsklassen, den der er mest repræsenteret.
Denne meget enkle teknik er optimal i det tilfælde, hvor dataene kommer fra et ikke-partisk tilfældigt valg i befolkningen; matrixen for omkostningerne ved forkert fordeling er enhed (symmetrisk): korrekt fordeling til nul pris og forkert fordeling af omkostninger 1 uanset tilfældet. Uden for denne ramme er flertalsregel ikke nødvendigvis berettiget, men er let at bruge i praksis.
Nogle teknikker, kaldet sætmetoder ( alle metoder ), forbedrer forudsigelsens kvalitet eller pålidelighed ved at bygge flere beslutningstræer ud fra dataene:
Beslutningstræer kombineres undertiden med hinanden eller med andre læringsteknikker: diskriminerende analyse, logistiske regressioner, lineære regressioner, neurale netværk ( multilayer perceptron , radial basis funktionsnetværk ) eller andre.
Procedurer til aggregering af ydeevnen for de forskellige anvendte modeller (såsom beslutninger efter konsensus) er indført for at opnå maksimal ydeevne, samtidig med at niveauet for kompleksiteten af de anvendte modeller kontrolleres.
Sammenlignet med andre dataminingmetoder har beslutningstræer flere fordele:
På den anden side har det visse ulemper:
I et beslutningstræ bruger alle stier fra rod til blade AND- stikket . I en beslutningsgraf kan vi også bruge OR- stikket til at forbinde flere stier ved hjælp af den minimale beskedlængde (MML). Generelt producerer beslutningsgrafer grafer med færre blade end beslutningstræer.
Af evolutionære algoritmer bruges til at undgå adskillelse, hvilket fører til lokalt optimalt.
Man kan også prøve træet ved hjælp af MCMC- metoder i et Bayesisk paradigme .
Træet kan bygges ved hjælp af en bottom-up (bottom-up) tilgang.
Der er flere algoritmer til at bygge beslutningstræer, herunder:
ID3 og CART blev uafhængigt opfundet i årtierne 1970-1980, men bruger lignende tilgange til at lære beslutningstræer fra læringssættet.
Alle disse algoritmer er kendetegnet ved de anvendte segmenteringskriterier ved de beskæringsmetoder, der er implementeret, ved deres måde at håndtere de manglende data i forudsigerne på.
Mange data mining software tilbyder biblioteker til at implementere en eller flere beslutningstræ læringsalgoritmer. For eksempel indeholder Open Source R- softwaren flere implementeringer af CART, såsom rpart, party og randomForest, den gratis software Weka og Orange (og dets orngTree-modul) eller det gratis Python-bibliotek scikit-learning ; men også Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server [1] .