Beslutningstræ

Et beslutningstræ (også kaldet et klassifikationstræ eller regressionstræ) er et beslutningsstøtteværktøj , der bruges i maskinlæring , dataanalyse og statistik . Strukturen af ​​et træ er "blade" og "grene". På kanterne ("grene") af beslutningstræet er de funktioner, som den objektive funktion afhænger af, skrevet, værdierne af den objektive funktion er skrevet i "bladene" , og i de resterende noder er de funktioner, som sagerne er forskellige. For at klassificere et nyt tilfælde skal man gå ned i træet til et blad og returnere den tilsvarende værdi.

Sådanne beslutningstræer er meget udbredt i data mining. Målet er at skabe en model , der forudsiger værdien af ​​målvariablen baseret på flere inputvariabler.

Hvert blad repræsenterer værdien af ​​målvariablen, når den ændres fra roden langs trækanterne til bladet. Hver intern node er afbildet til en af ​​inputvariablerne.

Træet kan også "læres" ved at opdele de oprindelige sæt af variabler i undersæt baseret på kontrol af funktionsværdier. Denne handling gentages på hvert af de resulterende undersæt. Rekursionen slutter, når en delmængde i en node har de samme målvariableværdier, så den tilføjer ingen værdi til forudsigelserne. Top-down processen, decision tree induction (TDIDT) [1] , er et eksempel på en absorberende grådig algoritme, og er langt den mest almindelige beslutningstræ strategi for data, men det er ikke den eneste mulige strategi.

I data mining kan beslutningstræer bruges som matematiske og beregningsmæssige teknikker til at hjælpe med at beskrive, klassificere og generalisere et sæt data, som kan skrives som følger:

Den afhængige variabel Y er den målvariabel, der skal analyseres, klassificeres og opsummeres. Vektoren består af inputvariablerne , osv ., som bruges til at udføre denne opgave.

Grundlæggende definitioner

Beslutningstræanalyse bruger et visuelt og analytisk beslutningsstøtteværktøj til at beregne forventede værdier (eller forventede fordele) af konkurrerende alternativer.

Beslutningstræet består af tre typer knudepunkter:

• Beslutningsknudepunkter - normalt repræsenteret ved firkanter
• Sandsynlighedsnoder - repræsenteret som en cirkel
• Afslutningsknuder - repræsenteret som en trekant

I figuren ovenfor skal beslutningstræet læses fra venstre mod højre. Beslutningstræet kan ikke indeholde cykliske elementer, det vil sige, at hvert nyt blad efterfølgende kun kan opdeles, der er ingen konvergerende stier. Når vi konstruerer et træ manuelt, kan vi således støde på problemet med dets dimension, derfor kan vi som regel få et beslutningstræ ved hjælp af specialiseret software. Typisk præsenteres et beslutningstræ i form af en skematisk tegning, som gør det lettere at forstå og analysere.

Trætypologi

Beslutningstræer, der bruges i datamining , er af to hovedtyper:

• Et træ til at klassificere, når det forudsagte resultat er den klasse, som dataene tilhører;
• Træ til regression, når det forudsagte resultat kan betragtes som et reelt tal (f.eks. prisen på et hus eller længden af ​​en patients ophold på et hospital).

De ovenfor nævnte udtryk blev først introduceret af Breiman et al. [2] De anførte typer har nogle ligheder (rekursive konstruktionsalgoritmer), såvel som nogle forskelle, såsom kriterierne for at vælge en partition ved hver node. [2]

Nogle metoder giver dig mulighed for at bygge mere end ét beslutningstræ (ensembler af beslutningstræer):

1. Bagning over beslutningstræer, den tidligste tilgang . Opbygger flere beslutningstræer, interpolerer gentagne gange dataene med erstatning ( bootstrap ), og giver som et konsensussvar træernes stemme (deres gennemsnitlige forudsigelse); [3]
2. Random Forest - klassifikatoren er baseret på bagging , men udover den vælger den tilfældigt en undergruppe af funktioner ved hver knude for at gøre træerne mere uafhængige;
3. Træforstærkning kan bruges til både regressions- og klassifikationsproblemer. [4] En implementering af træforstærkning, XGBoost- algoritmen , er gentagne gange blevet brugt af vindere af dataanalysekonkurrencer.
4. "Skovrotation" - træer, hvor hvert beslutningstræ analyseres ved den første anvendelse af hovedkomponentanalysen (PCA) på tilfældige delmængder af inputfunktioner. [5]

Trækonstruktionsalgoritmer

Der er forskellige måder at vælge den næste funktion på:

• Algoritme ID3 , hvor valget af en funktion sker på baggrund af informationsgevinst ( eng.  Gain ), eller på baggrund af Gini-kriteriet .
• Algoritme C4.5 (forbedret version af ID3), hvor funktionsvalg er baseret på normaliseret informationsforstærkning ( Gain Ratio ) . 
• CART - algoritme og dens modifikationer — IndCART, DB-CART.
• Automatisk Chi-Square Interaction Detector (CHAID). Udfører adskillelse på flere niveauer ved beregning af træklassificering; [6]
• MARS: udvider beslutningstræer for at forbedre digital databehandling.

I praksis er træer som følge af disse algoritmer ofte for detaljerede, hvilket ved yderligere anvendelse giver en masse fejl. Dette skyldes fænomenet overfitting . For at reducere træer bruges beskæring ( engelsk  pruning ).

Fordele ved metoden

I modsætning til andre data mining-metoder har beslutningstræmetoden flere fordele:

• Let at forstå og fortolke.
• Det kræver ikke speciel dataforberedelse, såsom datanormalisering, tilføjelse af dummyvariabler og fjernelse af manglende data.
• Kan arbejde med både kategoriske og intervalvariable. (Andre metoder virker kun med data, hvor der kun er én type variabel. For eksempel kan ratio-metoden kun anvendes på nominelle variable, og den neurale netværksmetode kun på variable målt på en intervalskala.)
• Den bruger en "white box"-model, det vil sige, hvis en bestemt situation observeres i modellen, så kan den forklares ved hjælp af boolsk logik. Et eksempel på en "sort boks" kan være et kunstigt neuralt netværk , da de opnåede resultater er svære at forklare.
• Giver dig mulighed for at evaluere modellen ved hjælp af statistiske test. Dette gør det muligt at vurdere modellens pålidelighed.
• Metoden fungerer godt, selvom de oprindelige forudsætninger i modellen er blevet overtrådt.
• Giver dig mulighed for at arbejde med en stor mængde information uden særlige forberedende procedurer. Denne metode kræver ikke specielt udstyr til at arbejde med store databaser.

Ulemper ved metoden

• Problemet med at opnå et optimalt beslutningstræ er et NP-komplet problem , hvad angår nogle aspekter af optimalitet selv for simple problemer [7] [8] . Den praktiske anvendelse af beslutningstræalgoritmen er således baseret på heuristiske algoritmer, såsom den "grådige" algoritme, hvor den eneste optimale løsning vælges lokalt ved hver knude. Sådanne algoritmer kan ikke sikre optimaliteten af ​​hele træet som helhed.
• Processen med at bygge et beslutningstræ kan skabe alt for komplekse strukturer, der ikke fuldt ud repræsenterer dataene. Dette problem kaldes overfitting [9] . For at undgå det er det nødvendigt at bruge metoden til "justering af træets dybde".
• Der er begreber, som er svære at forstå ud fra modellen, fordi modellen beskriver dem på en kompleks måde. Dette fænomen kan være forårsaget af XOR-, paritets- eller multiplekserproblemer. I dette tilfælde har vi at gøre med uoverkommeligt store træer. Der er flere tilgange til at løse dette problem, for eksempel et forsøg på at ændre repræsentationen af ​​begrebet i modellen (udarbejdelse af nye domme) [10] , eller brugen af ​​algoritmer, der mere fuldstændigt beskriver og repræsenterer begrebet (f.eks. , metoden til statistiske relationer, induktiv programmeringslogik).
• For data, der inkluderer kategoriske variabler med et stort sæt af niveauer (lukninger), tildeles mere informationsvægt til de funktioner, der har flere niveauer [11] .

Trædybdekontrol

Trædybderegulering er en teknik, der giver dig mulighed for at reducere størrelsen af ​​et beslutningstræ ved at fjerne dele af træet, der har ringe vægt.

Et af de spørgsmål, der opstår i beslutningstræalgoritmen, er den optimale størrelse af det endelige træ. Et lille træ kan således ikke fange en eller anden vigtig information om prøverummet. Det er dog svært at sige, hvornår algoritmen skal stoppe, fordi det er umuligt at forudsige, hvilken knudetilsætning der vil reducere fejlen markant. Dette problem er kendt som "horisonteffekten". Den generelle træbegrænsningsstrategi er dog bevaret, det vil sige, at fjernelse af noder implementeres, hvis de ikke giver yderligere information [12] .

Trædybdejustering bør reducere størrelsen af ​​træningstræmodellen uden at reducere dens forudsigelsesnøjagtighed eller gennem krydsvalidering. Der er mange metoder til at justere dybden af ​​et træ, der adskiller sig i mål for ydeevneoptimering.

Regulatoriske metoder

Træbeskæring kan udføres fra top til bund eller fra bund til top. Fra top til bund - beskæring starter fra roden, fra bund til top - antallet af blade på træet reduceres. En af de enkleste kontrolmetoder er at reducere træbegrænsningsfejlen. Startende med blade erstattes hver node af den mest populære klasse. Hvis ændringen ikke påvirker nøjagtigheden af ​​forudsigelsen, gemmes den.

Problemeksempel

Antag, at vi er interesserede i, om vores favorit fodboldhold vinder den næste kamp. Vi ved, at dette afhænger af en række parametre; at nævne dem alle er en håbløs opgave, så vi vil begrænse os til de vigtigste:

• om modstanderen er højere i stillingen;
• om kampen spilles på hjemmebane;
• om nogen af ​​holdlederne går glip af kampen;
• regner det.

Vi har nogle statistikker om dette:

Jeg vil gerne forstå, om vores hold vinder i næste kamp.

Se også

• Random forest  - en klassificering baseret på brugen af ​​udvalg fra beslutningstræer
• Omskoling
• Maskinlæring  er en klasse af kunstig intelligens -metoder , hvis karakteristiske træk ikke er den direkte løsning af problemet, men læring i processen med at anvende løsninger på mange lignende problemer.
• Beslutningstabel

Noter

1. ↑ Quinlan, JR Induktion af beslutningstræer  //  Machine Learning. - Kluwer Academic Publishers, 1986. - Nr. 1 . - S. 81-106 . Arkiveret fra originalen den 20. januar 2022.
2. ↑ 1 2 Breiman, Leo; Friedman, JH, Olshen, RA, & Stone, CJ Klassifikations- og regressionstræer  . - Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. - ISBN 978-0-412-04841-8 .
3. ↑ Breiman, L. Bagging Predictors  //  Machine Learning. - 1996. - Nej. 24 . - S. 123-140 .
4. ↑ Friedman, JH Stokastisk gradientforøgelse  . - Stanford University, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Elementerne i statistisk læring : Data mining, inferens og forudsigelse  . — New York: Springer Verlag, 2001.
6. ↑ Kas ,  G.V. _  Serie C (Anvendt statistik). — Bd. 29 , nr. 2 . - S. 119-127 . - doi : 10.2307/2986296 . Arkiveret fra originalen den 2. april 2022.
7. ↑ Hyafil, Laurent; Rivest, R.L. Konstruktion af optimale binære beslutningstræer er NP-komplet  //  Informationsbehandlingsbreve. - 1976. - Bd. 5 , nr. 1 . - S. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Automatisk konstruktion af beslutningstræer fra data: En tværfaglig undersøgelse  //  Data Mining and Knowledge Discovery. - 1998. - Nej. 2 . - s. 345-389 . Arkiveret fra originalen den 2. april 2022.
9. ↑ Max Bramer. Principper for Data  Mining . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Induktiv logisk programmering  / Horváth, Tamás; Yamamoto, Akihiro, red. - Springer, 2003. - ISBN 978-3-540-20144-1 .
11. ↑ Deng, H., Runger, G., Tuv, E. Bias of Importance Measures for Multi-valued Attributes and Solutions // Artificial Neurale Networks and Machine Learning - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( Engelsk) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (red.). - Berlin, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Hurtig, bottom-up beslutningstræbeskæringsalgoritme

Links

• Forelæsningsnotater om beslutningstræer
• Decision trees applet giver flere eksempler på datasæt med eksempler til at lære og klassificere

Litteratur

• Levitin A. V. Kapitel 10. Algoritmers magtgrænser: Beslutningstræer // Algoritmer. Introduktion til udvikling og analyse - M .: Williams , 2006. - S. 409-417. — 576 s. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Kapitel 9. // Business Analytics: Fra data til viden (+CD): Selvstudium. 2. udg. - Sankt Petersborg. : Peter, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .