Beslutsträd

Ett beslutsträd (även kallat ett klassificeringsträd eller regressionsträd ) är ett beslutsstödsverktyg som används i maskininlärning , dataanalys och statistik . Strukturen av ett träd är "löv" och "grenar". På kanterna ("grenar") av beslutsträdet skrivs de funktioner som den objektiva funktionen beror på, värdena för den objektiva funktionen skrivs i "löven" och i de återstående noderna är de funktioner som fallen skiljer sig åt. För att klassificera ett nytt fall måste man gå ner i trädet till ett löv och returnera motsvarande värde.

Sådana beslutsträd används i stor utsträckning inom datautvinning. Målet är att skapa en modell som förutsäger värdet av målvariabeln baserat på flera indatavariabler.

Varje blad representerar värdet på målvariabeln när den ändras från roten längs trädkanterna till bladet. Varje intern nod mappas till en av ingångsvariablerna.

Trädet kan också "läras" genom att dela upp de ursprungliga uppsättningarna av variabler i delmängder baserat på kontroll av funktionsvärden. Denna åtgärd upprepas på var och en av de resulterande delmängderna. Rekursionen slutar när en delmängd i en nod har samma målvariabelvärden, så den lägger inget värde till förutsägelserna. Top-down-processen, beslutsträdsinduktion (TDIDT) [1] , är ett exempel på en absorberande girig algoritm, och är den i särklass vanligaste beslutsträdstrategin för data, men det är inte den enda möjliga strategin.

Inom datautvinning kan beslutsträd användas som matematiska och beräkningstekniker för att hjälpa till att beskriva, klassificera och generalisera en uppsättning data, som kan skrivas enligt följande:

Den beroende variabeln Y är den målvariabel som ska analyseras, klassificeras och sammanfattas. Vektorn består av indatavariablerna , , etc., som används för att slutföra denna uppgift.

Grundläggande definitioner

Beslutsträdsanalys använder ett visuellt och analytiskt beslutsstödsverktyg för att beräkna förväntade värden (eller förväntade fördelar) av konkurrerande alternativ.

Beslutsträdet består av tre typer av noder:

• Beslutsnoder - vanligtvis representerade av kvadrater
• Sannolikhetsnoder - representerade som en cirkel
• Stängningsnoder - representerade som en triangel

I figuren ovan ska beslutsträdet läsas från vänster till höger. Beslutsträdet kan inte innehålla cykliska element, det vill säga varje nytt blad kan därefter bara delas, det finns inga konvergerande vägar. Sålunda, när vi konstruerar ett träd manuellt, kan vi stöta på problemet med dess dimension, därför kan vi som regel erhålla ett beslutsträd med hjälp av specialiserad programvara. Vanligtvis presenteras ett beslutsträd i form av en schematisk ritning, vilket gör det lättare att förstå och analysera.

Trädtypologi

Beslutsträd som används vid datautvinning är av två huvudtyper:

• Ett träd att klassificera när det förutsagda resultatet är den klass som data tillhör;
• Träd för regression när det förutsagda resultatet kan betraktas som ett reellt tal (till exempel priset på ett hus eller längden på en patients vistelse på ett sjukhus).

Termerna som nämns ovan introducerades först av Breiman et al. [2] De listade typerna har vissa likheter (rekursiva konstruktionsalgoritmer), såväl som vissa skillnader, såsom kriterierna för att välja en partition vid varje nod. [2]

Vissa metoder låter dig bygga mer än ett beslutsträd (ensembler av beslutsträd):

1. Påsar över beslutsträd, den tidigaste metoden . Bygger flera beslutsträd, interpolerar upprepade gånger data med ersättning ( bootstrap ), och ger som ett konsensussvar trädens röst (deras genomsnittliga förutsägelse); [3]
2. Random Forest- klassificeraren är baserad på packning , men utöver den väljer den slumpmässigt en undergrupp av funktioner vid varje nod för att göra träden mer oberoende;
3. Trädförstärkning kan användas för både regressions- och klassificeringsproblem. [4] En implementering av trädförstärkning, XGBoost- algoritmen , har upprepade gånger använts av vinnare av dataanalystävlingar.
4. "Forest rotation" - träd där varje beslutsträd analyseras genom den första tillämpningen av principal component analysis (PCA) på slumpmässiga delmängder av indatafunktioner. [5]

Algoritmer för trädkonstruktion

Det finns olika sätt att välja nästa funktion:

• Algoritm ID3 , där valet av en funktion sker på basis av informationsvinst ( eng.  Gain ), eller på basis av Gini-kriteriet .
• Algoritm C4.5 (förbättrad version av ID3), där funktionsval baseras på normaliserad informationsförstärkning ( Gain Ratio ) . 
• CART - algoritm och dess modifieringar — IndCART, DB-CART.
• Automatisk Chi-Square Interaction Detector (CHAID). Utför separation på flera nivåer vid beräkning av trädklassificering; [6]
• MARS: utökar beslutsträd för att förbättra digital databehandling.

I praktiken, som ett resultat av dessa algoritmer, är träd ofta för detaljerade, vilket, när de tillämpas ytterligare, ger många fel. Detta beror på fenomenet övermontering . För att minska träd används beskärning ( engelska  beskärning ).

Fördelar med metoden

Till skillnad från andra datautvinningsmetoder har beslutsträdsmetoden flera fördelar:

• Lätt att förstå och tolka.
• Det kräver ingen speciell dataförberedelse, såsom datanormalisering, lägga till dummyvariabler och ta bort saknade data.
• Kunna arbeta med både kategoriska och intervallvariabler. (Andra metoder fungerar endast med data där det bara finns en typ av variabel. Till exempel kan förhållandemetoden endast tillämpas på nominella variabler och den neurala nätverksmetoden endast på variabler som mäts på en intervallskala.)
• Den använder en "white box"-modell, det vill säga om en viss situation observeras i modellen, kan den förklaras med boolesk logik. Ett exempel på en "svart låda" kan vara ett artificiellt neuralt nätverk , eftersom de erhållna resultaten är svåra att förklara.
• Låter dig utvärdera modellen med hjälp av statistiska tester. Detta gör det möjligt att bedöma modellens tillförlitlighet.
• Metoden fungerar bra även om de ursprungliga antaganden som ingår i modellen har brutits.
• Gör att du kan arbeta med en stor mängd information utan särskilda förberedande procedurer. Denna metod kräver ingen speciell utrustning för att arbeta med stora databaser.

Nackdelar med metoden

• Problemet med att erhålla ett optimalt beslutsträd är ett NP-komplett problem , vad gäller vissa aspekter av optimalitet även för enkla problem [7] [8] . Sålunda är den praktiska tillämpningen av beslutsträdsalgoritmen baserad på heuristiska algoritmer, såsom den "giriga" algoritmen, där den enda optimala lösningen väljs lokalt vid varje nod. Sådana algoritmer kan inte säkerställa optimaliteten för hela trädet som helhet.
• Processen att bygga ett beslutsträd kan skapa alltför komplexa strukturer som inte helt representerar data. Detta problem kallas övermontering [9] . För att undvika det är det nödvändigt att använda metoden för att "justera trädets djup".
• Det finns begrepp som är svåra att förstå utifrån modellen, eftersom modellen beskriver dem på ett komplext sätt. Detta fenomen kan orsakas av XOR-, paritets- eller multiplexerproblem. I det här fallet har vi att göra med oöverkomligt stora träd. Det finns flera tillvägagångssätt för att lösa detta problem, till exempel ett försök att ändra representationen av begreppet i modellen (att göra upp nya bedömningar) [10] , eller användningen av algoritmer som mer fullständigt beskriver och representerar begreppet (till exempel , metoden för statistiska relationer, induktiv programmeringslogik).
• För data som inkluderar kategoriska variabler med en stor uppsättning nivåer (stängningar), tilldelas mer informationsvikt de funktioner som har fler nivåer [11] .

Träddjupskontroll

Träddjupsstrypning är en teknik som gör att du kan minska storleken på ett beslutsträd genom att ta bort delar av trädet som har liten vikt.

En av frågorna som uppstår i beslutsträdsalgoritmen är den optimala storleken på det slutliga trädet. Ett litet träd får alltså inte fånga en eller annan viktig information om provutrymmet. Det är dock svårt att säga när algoritmen ska sluta, eftersom det är omöjligt att förutsäga vilken nodtillägg som kommer att minska felet avsevärt. Detta problem är känt som "horisonteffekten". Den allmänna trädbegränsningsstrategin bevaras dock, det vill säga borttagningen av noder implementeras om de inte ger ytterligare information [12] .

Träddjupsjustering bör minska storleken på träningsträdmodellen utan att minska dess prediktionsnoggrannhet eller genom korsvalidering. Det finns många metoder för att justera djupet på ett träd som skiljer sig åt i måttet på prestandaoptimering.

Regleringsmetoder

Trädbeskärning kan göras från topp till botten eller från botten till toppen. Från topp till botten - beskärning börjar från roten, från botten till topp - antalet löv på trädet minskas. En av de enklaste kontrollmetoderna är att minska trädbegränsningsfelet. Börjar med löv, varje nod ersätts av den mest populära klassen. Om ändringen inte påverkar förutsägelsens noggrannhet, sparas den.

Problemexempel

Anta att vi är intresserade av om vårt favoritfotbollslag vinner nästa match. Vi vet att detta beror på ett antal parametrar; att lista dem alla är en hopplös uppgift, så vi kommer att begränsa oss till de viktigaste:

• om motståndaren är högre i ställningen;
• om matchen spelas hemma;
• om någon av lagledarna missar matchen;
• regnar det.

Vi har lite statistik om detta:

Jag skulle vilja förstå om vårt lag kommer att vinna i nästa match.

Se även

• Random forest  - en klassificerare baserad på användningen av kommittéer från beslutsträd
• Omskolning
• Maskininlärning  är en klass av metoder för artificiell intelligens , vars karakteristiska drag inte är den direkta lösningen av problemet, utan lärande i processen att tillämpa lösningar på många liknande problem.
• Beslutstabell

Anteckningar

1. ↑ Quinlan, JR Induktion av beslutsträd  //  Maskininlärning. - Kluwer Academic Publishers, 1986. - Nej . 1 . - S. 81-106 . Arkiverad från originalet den 20 januari 2022.
2. ↑ 1 2 Breiman, Leo; Friedman, JH, Olshen, RA, & Stone, CJ Klassificerings- och regressionsträd  . - 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 gradientförstärkning  . — Stanford University, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Delarna av statistisk inlärning : Data mining, inferens och förutsägelse  . — New York: Springer Verlag, 2001.
6. ↑ Kas ,  G.V. _  Serie C (tillämpad statistik). — Vol. 29 , nr. 2 . - S. 119-127 . - doi : 10.2307/2986296 . Arkiverad från originalet den 2 april 2022.
7. ↑ Hyafil, Laurent; Rivest, R.L. Att konstruera optimala binära beslutsträd är NP-komplett  //  Informationsbehandlingsbrev. - 1976. - Vol. 5 , nej. 1 . - S. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Automatisk konstruktion av beslutsträd från data: En multidisciplinär undersökning  //  Data Mining and Knowledge Discovery. - 1998. - Nej . 2 . - s. 345-389 . Arkiverad från originalet den 2 april 2022.
9. ↑ Max Bramer. Principer för  datautvinning . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Induktiv logikprogrammering  / 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 // Artificiella neurala nätverk och maskininlärning - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( Engelska) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (eds). - Berlin, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Snabb, nedifrån och upp-beslutsträdbeskärningsalgoritm

Länkar

• Föreläsningsanteckningar om beslutsträd
• Decision trees applet tillhandahåller flera exempeldatauppsättningar med exempel att lära sig och klassificera

Litteratur

• Levitin A. V. Kapitel 10. Algoritmers kraftgränser: beslutsträd // Algoritmer. Introduktion till utveckling och analys - M .: Williams , 2006. - S. 409-417. — 576 sid. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Kapitel 9. // Business Analytics: From Data to Knowledge (+CD): Handledning. 2:a uppl. - St Petersburg. : Peter, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .