Beslutsträdalgoritmsexempel i Data Mining

decision tree algorithm examples data mining

Denna fördjupade handledning förklarar allt om beslutsträdets algoritm i datautvinning. Du lär dig om exempel på beslutsträd, algoritm och klassificering:

Vi tittade på ett par Exempel på datautvinning i vår tidigare handledning i Utbildningsserie för kostnadsfri gruvdrift .

Decision Tree Mining är en typ av data miningsteknik som används för att bygga klassificeringsmodeller. Det bygger klassificeringsmodeller i form av en trädliknande struktur, precis som dess namn. Denna typ av gruvdrift tillhör övervakad klassinlärning.

I övervakat lärande är målresultatet redan känt. Beslutsträd kan användas för både kategoriska och numeriska data. De kategoriska uppgifterna representerar kön, civilstånd etc. medan de numeriska uppgifterna representerar ålder, temperatur, etc.

bästa mp3-musiknedladdaren för Android

Ett exempel på ett beslutsträd med datasetet visas nedan.

(bild källa )

Vad du kommer att lära dig:

• Vad är användningen av ett beslutsträd?
• Klassificeringsanalys
• Regressionsanalys
• Hur fungerar ett beslutsträd?
• Beslutsträdinduktionsalgoritm
• Beslutsträdinduktion
• VAGN
• Beslutsträdinduktion för maskininlärning: ID3
• Vad är girig rekursiv binär splittring?
• Hur väljer man attribut för att skapa ett träd?
  • # 1) Informationsvinster
  • # 2) Vinstförhållande
  • # 3) Gini-index
• Övermontering i beslutsträd
• Vad är trädbeskärning?
• Vad är förutsägbar modellering?
• Fördelar med klassificering av beslutsträd
• Nackdelar med klassificering av beslutsträd
• Slutsats
• Rekommenderad läsning

Vad är användningen av ett beslutsträd?

Beslutsträd används för att bygga klassificerings- och regressionsmodeller. Den används för att skapa datamodeller som förutsäger klassetiketter eller värden för beslutsprocessen. Modellerna är byggda från träningsdatasetet som matas till systemet (övervakat lärande).

Med hjälp av ett beslutsträd kan vi visualisera de beslut som gör det lätt att förstå och därför är det en populär data miningsteknik.

Klassificeringsanalys

Dataklassificering är en analysform som bygger en modell som beskriver viktiga klassvariabler.Till exempel, en modell byggd för att kategorisera banklånansökningar som säkra eller riskabla. Klassificeringsmetoder används i maskininlärning och mönsterigenkänning.

Tillämpning av klassificering inkluderar upptäckt av bedrägerier, medicinsk diagnos, målmarknadsföring, etc. Resultatet av klassificeringsproblemet betraktas som 'Mode' för alla observerade värden i terminalnoden.

En tvåstegsprocess följs för att bygga en klassificeringsmodell.

1. I det första steget, dvs. lärande: En klassificeringsmodell baserad på träningsdata byggs.
2. I det andra steget, dvs. klassificering, kontrolleras modellens noggrannhet och sedan används modellen för att klassificera nya data. Klassetiketterna som presenteras här har formen av diskreta värden som ”ja” eller ”nej”, “säkert” eller “riskabelt”.

Den allmänna metoden för byggnadsklassificeringsmodeller ges nedan:

(bild källa )

Regressionsanalys

Regressionsanalys används för förutsägelse av numeriska attribut.

Numeriska attribut kallas också kontinuerliga värden. En modell byggd för att förutsäga de kontinuerliga värdena istället för klassetiketter kallas regressionsmodellen. Resultatet av regressionsanalysen är 'medelvärdet' för alla observerade värden för noden.

Hur fungerar ett beslutsträd?

Ett beslutsträd är en övervakad inlärningsalgoritm som fungerar för både diskreta och kontinuerliga variabler. Den delar datauppsättningen i delmängder på grundval av det viktigaste attributet i datauppsättningen. Hur beslutsträdet identifierar detta attribut och hur delningen sker bestäms av algoritmerna.

Den mest betydande prediktorn betecknas som rotnoden, delning görs för att bilda undernoder som kallas beslutsnoder, och de noder som inte delas vidare är terminal- eller bladnoder.

I beslutsträdet är datauppsättningen uppdelad i homogena och icke-överlappande regioner. Det följer en uppifrån och ner-strategi när toppregionen presenterar alla observationer på en enda plats som delas upp i två eller flera grenar som splittras ytterligare. Detta tillvägagångssätt kallas också a giriga tillvägagångssätt eftersom det bara tar hänsyn till den aktuella noden mellan de arbetade utan att fokusera på framtida noder.

Beslutsträdalgoritmerna kommer att fortsätta att köras tills ett stoppkriterium såsom det minsta antalet observationer etc. har uppnåtts.

När ett beslutsträd har byggts kan många noder representera outliers eller bullriga data. Trädbeskärningsmetod används för att ta bort oönskade data. Detta förbättrar i sin tur noggrannheten i klassificeringsmodellen.

För att hitta modellens noggrannhet används en testuppsättning bestående av testpinnar och klassetiketter. Procentandelen av testuppsättningarna klassificeras korrekt av modellen för att identifiera modellens noggrannhet. Om modellen visar sig vara korrekt används den för att klassificera datatuplerna för vilka klassetiketterna inte är kända.

Några av beslutsträdalgoritmerna inkluderar Hunt's Algorithm, ID3, CD4.5 och CART.

Exempel på att skapa ett beslutsträd

(Exempel är hämtat från Data Mining Concepts: Han och Kimber)

# 1) Inlärningssteg: Träningsdata matas in i systemet för analys av en klassificeringsalgoritm. I det här exemplet är klassetiketten attributet dvs ”lånebeslut”. Modellen som bygger på denna träningsdata representeras i form av beslutsregler.

# 2) Klassificering: Testdataset matas till modellen för att kontrollera noggrannheten i klassificeringsregeln. Om modellen ger acceptabla resultat tillämpas den på en ny dataset med okända klassvariabler.

Beslutsträdinduktionsalgoritm

Beslutsträdinduktion

Beslutsträdinduktion är metoden för att lära sig beslutsträd från träningssatsen. Träningssatsen består av attribut och klassetiketter. Tillämpningar av beslutsträdinduktion inkluderar astronomi, ekonomisk analys, medicinsk diagnos, tillverkning och produktion.

Ett beslutsträd är en flödesschema trädliknande struktur som är gjord av träningsuppsättningar. Datauppsättningen är uppdelad i mindre delmängder och finns i form av ett träds noder. Trädstrukturen har en rotnod, interna noder eller beslutsnoder, bladnod och grenar.

Rotnoden är den översta noden. Det representerar det bästa attributet som valts för klassificering. Interna noder i beslutsnoderna representerar ett test av ett attribut för datasetbladnoden eller terminalnoden som representerar klassificeringen eller beslutetiketten. Grenarna visar resultatet av det utförda testet.

Vissa beslutsträd har bara binära noder , det betyder exakt två grenar av en nod, medan vissa beslutsträd är icke-binära.

Bilden nedan visar beslutsträdet för Titanic-datasetet för att förutsäga om passageraren kommer att överleva eller inte.

(bild källa )

VAGN

CART-modellen, dvs. klassificerings- och regressionsmodeller, är en beslutsträdalgoritm för att bygga modeller. Beslutsträdsmodell där målvärdena har en diskret karaktär kallas klassificeringsmodeller.

Ett diskret värde är en ändlig eller oändlig mängd värden, Till exempel, ålder, storlek etc. Modellerna där målvärdena representeras av kontinuerliga värden är vanligtvis siffror som kallas regressionsmodeller. Kontinuerliga variabler är variabla variabelpunkter. Dessa två modeller kallas tillsammans CART.

CART använder Gini Index som klassificeringsmatris.

Beslutsträdinduktion för maskininlärning: ID3

I slutet av 1970-talet och början av 1980-talet var J.Ross Quinlan en forskare som byggde en algoritm för beslutsträd för maskininlärning. Denna algoritm är känd som ID3, Iterativ dikotomiser . Denna algoritm var en förlängning av konceptinlärningssystemen som beskrivs av E.B Hunt, J och Marin.

ID3 blev senare känt som C4.5. ID3 och C4.5 följer en girig top-down-metod för att konstruera beslutsträd. Algoritmen börjar med en träningsdataset med klassetiketter som delas in i mindre delmängder när trädet konstrueras.

# 1) Ursprungligen finns det tre parametrar, dvs. attributlista, attributvalmetod och datapartition . Attributlistan beskriver attributen för utbildningsuppsättningarna.

#två) Attributvalsmetoden beskriver metoden för att välja det bästa attributet för diskriminering bland tuplar. Metoderna för attributval kan antingen vara Information Gain eller Gini Index.

# 3) Trädets struktur (binär eller icke-binär) bestäms av attributvalmetoden.

# 4) När du konstruerar ett beslutsträd, börjar det som en enda nod som representerar tuparna.

# 5) Om rotnodstubbarna representerar olika klassetiketter kallar den en attributvalsmetod för att dela eller partitionera tapparna. Steget kommer att leda till bildandet av filialer och beslutsnoder.

# 6) Delningsmetoden kommer att avgöra vilket attribut som ska väljas för att partitionera datatuplerna. Det bestämmer också grenarna som ska odlas från noden enligt testresultatet. Huvudmotivet för delningskriterierna är att partitionen vid varje gren av beslutsträdet ska representera samma klassmärkning.

Ett exempel på delningsattribut visas nedan:

a. Delningen ovan är diskret värderad.

b. Delningen ovan är för kontinuerligt värderad.

# 7) Ovanstående delningssteg följs rekursivt för att bilda ett beslutsträd för träningsdatasetet tuples.

# 8) Portionen stoppas endast när antingen alla partitioner är gjorda eller när de återstående tuplarna inte kan delas vidare.

# 9) Komplexiteten hos algoritmen beskrivs av n * | D | * logg | D | där n är antalet attribut i träningsdataset D och | D | är antalet tuplar.

Vad är girig rekursiv binär splittring?

I den binära delningsmetoden delas tuplarna och varje splitkostnadsfunktion beräknas. Den lägsta kostnadsdelningen har valts. Delningsmetoden är binär som bildas som två grenar. Det är rekursivt till sin natur eftersom samma metod (beräkning av kostnaden) används för att dela upp de andra tapparna i datasetet.

Denna algoritm kallas lika girig eftersom den bara fokuserar på den aktuella noden. Det fokuserar på att sänka sina kostnader, medan de andra noder ignoreras.

Hur väljer man attribut för att skapa ett träd?

Åtgärdsvalsåtgärder kallas också delningsregler för att bestämma hur tuplarna ska delas. Delningskriterierna används för att bäst partitionera datasetet. Dessa åtgärder ger en rangordning av attributen för uppdelning av träningstopparna.

De mest populära metoderna för att välja attribut är informationsvinster, Gini-index.

# 1) Informationsvinster

Denna metod är den huvudsakliga metoden som används för att bygga beslutsträd. Det minskar den information som krävs för att klassificera tuplarna. Det minskar antalet tester som behövs för att klassificera den angivna tupeln. Attributet med den högsta informationsförstärkningen väljs.

Den ursprungliga informationen som behövs för klassificering av en tupel i dataset D ges av:

Där p är sannolikheten för att tupeln tillhör klass C. Informationen kodas i bitar, därför används logg till bas 2. E (s) representerar den genomsnittliga mängd information som krävs för att ta reda på klassetiketten för dataset D. Denna informationsförstärkning kallas också Entropi .

Den information som krävs för exakt klassificering efter portionering ges med formeln:

Där P (c) är partitionens vikt. Denna information representerar den information som behövs för att klassificera dataset D vid delning med X.

Informationsvinsten är skillnaden mellan den ursprungliga och förväntade informationen som krävs för att klassificera tapparna i dataset D.

Förstärkning är minskningen av information som krävs genom att känna till värdet på X. Attributet med den högsta informationsförstärkningen väljs som “bäst”.

# 2) Vinstförhållande

Informationsvinster kan ibland resultera i portionering värdelös för klassificering. Förstärkningsförhållandet delar emellertid utbildningsuppsättningen i partitioner och tar hänsyn till antalet tappar av resultatet i förhållande till de totala tapparna. Attributet med maximalt förstärkningsförhållande används som ett delningsattribut.

# 3) Gini-index

Gini Index beräknas endast för binära variabler. Det mäter orenheten i träningstubbar för dataset D, som

P är sannolikheten för att tuple tillhör klass C. Gini-indexet som beräknas för binär delad dataset D med attribut A ges av:

Där n är den n: e partitionen av dataset D.

Minskningen av orenhet ges av skillnaden i Gini-index för den ursprungliga datasetet D och Gini-index efter partition med attribut A.

Den maximala minskningen av orenhet eller max Gini-index väljs som det bästa attributet för delning.

Övermontering i beslutsträd

Överanpassning händer när ett beslutsträd försöker vara så perfekt som möjligt genom att öka testdjupet och därmed minska felet. Detta resulterar i mycket komplexa träd och leder till övermontering.

Överanpassning minskar beslutsträdets prediktiva karaktär. Tillvägagångssätten för att undvika överpassning av träden inkluderar för beskärning och efter beskärning.

Vad är trädbeskärning?

Beskärning är metoden för att ta bort de oanvända grenarna från beslutsträdet. Vissa grenar av beslutsträdet kan representera outliers eller bullriga data.

Trädbeskärning är metoden för att minska trädets oönskade grenar. Detta minskar trädets komplexitet och hjälper till med effektiv prediktiv analys. Det minskar överanpassningen eftersom det tar bort de oviktiga grenarna från träden.

topp 10 webbutvecklingsföretag i Indien

Det finns två sätt att beskära trädet:

# 1) Förskärning : I detta tillvägagångssätt stoppas konstruktionen av beslutsträdet tidigt. Det betyder att man beslutar att inte ytterligare dela upp filialerna. Den senast konstruerade noden blir bladnoden och denna bladnod kan innehålla den vanligaste klassen bland tuparna.

Attributvalsmåtten används för att ta reda på vikten för delningen. Tröskelvärden föreskrivs för att bestämma vilka delningar som anses vara användbara. Om delningen av noden resulterar i delning genom att falla under tröskeln stoppas processen.

# 2) Efterbeskärning : Den här metoden tar bort grenarna från ett fullvuxet träd. De oönskade grenarna tas bort och ersätts av en bladnod som anger den vanligaste klassetiketten. Denna teknik kräver mer beräkning än förbeskärning, men den är mer tillförlitlig.

De beskurna träden är mer exakta och kompakta jämfört med oklippta träd men de har en nackdel med replikering och upprepning.

Upprepning inträffar när samma attribut testas om och om igen längs en gren av ett träd. Replikering inträffar när de dubbla undertråden finns i trädet. Dessa problem kan lösas med multivariata splittringar.

Bilden nedan visar ett oskuret och beskuret träd.

Exempel på beslutsträdalgoritm

Exempel Källa

Konstruera ett beslutsträd

Låt oss ta ett exempel på de senaste 10 dagars väderdataset med attribut outlook, temperatur, vind och fuktighet. Resultatvariabeln kommer att spela cricket eller inte. Vi använder ID3-algoritmen för att bygga beslutsträdet.

Steg 1: Det första steget blir att skapa en rotnod.

Steg 2: Om alla resultat är ja, kommer bladnoden 'ja' att returneras, annars kommer bladnoden 'nej' att returneras.

Steg 3: Ta reda på Entropi av alla observationer och entropi med attributet 'x' som är E (S) och E (S, x).

Steg 4: Ta reda på informationsförstärkningen och välj attributet med hög informationsförstärkning.

Steg 5: Upprepa stegen ovan tills alla attribut täcks.

Beräkning av entropi:

Ja Nej

9 5

Om entropi är noll betyder det att alla medlemmar tillhör samma klass och om entropi är en betyder det att hälften av tuplarna tillhör en klass och en av dem tillhör en annan klass. 0,94 betyder rättvis fördelning.

Hitta attributet informationsvinster som ger maximal informationsvinster.

Till exempel 'Vind', det tar två värden: stark och svag, därför x = {stark, svag}.

Ta reda på H (x), P (x) för x = svag och x = stark. H (S) är redan beräknat ovan.

Svag = 8

Stark = 8

För 'svag' vind säger 6 av dem 'Ja' för att spela cricket och 2 av dem säger 'Nej'. Så entropi kommer att vara:

För 'stark' vind sa 3 'Nej' för att spela cricket och 3 sa 'Ja'.

Detta visar perfekt slumpmässighet eftersom halva objekt tillhör en klass och den återstående hälften tillhör andra.

Beräkna informationsvinsten,

På samma sätt är informationsvinsten för andra attribut:

Attribututsikterna har högsta informationsvinsten av 0,246, så den väljs som rot.

Mulet har 3 värden: Soligt, Mulet och regn. Mulet med cricket är alltid ”Ja”. Så det slutar med en bladnod, 'ja'. För de andra värdena 'Soligt' och 'Regn'.

Tabell för Outlook som 'Sunny' kommer att vara:

Entropi för 'Outlook' 'Sunny' är:

Informationsvinsten för attribut med avseende på Sunny är:

Informationsförstärkningen för fuktighet är högst, därför väljs den som nästa nod. På samma sätt beräknas Entropy för regn. Vind ger den högsta informationsvinsten .

Beslutsträdet skulle se ut nedan:

Vad är förutsägbar modellering?

Klassificeringsmodellerna kan användas för att förutsäga resultatet av en okänd uppsättning attribut.

När en dataset med okända klassetiketter matas in i modellen tilldelas den automatiskt klassetiketten till den. Denna metod för att tillämpa sannolikhet för att förutsäga resultat kallas prediktiv modellering.

hur man öppnar jar-filer på Windows

Fördelar med klassificering av beslutsträd

Nedan listas de olika fördelarna med klassificering av beslutsträd:

1. Beslutsträdklassificering kräver ingen domänkunskap, därför är den lämplig för kunskapsprocessen.
2. Representationen av data i form av trädet är lätt att förstå av människor och det är intuitivt.
3. Den kan hantera flerdimensionell data.
4. Det är en snabb process med stor noggrannhet.

Nackdelar med klassificering av beslutsträd

Nedan följer de olika nedgångarna i klassificeringen av beslutsträd:

1. Ibland blir beslutsträd mycket komplexa och dessa kallas överanpassade träd.
2. Beslutsträdets algoritm kanske inte är en optimal lösning.
3. Beslutsträden kan returnera en partisk lösning om någon klassmärkning dominerar den.

Slutsats

Beslutsträd är tekniker för datamining för klassificering och regressionsanalys.

Denna teknik sträcker sig nu över många områden som medicinsk diagnos, målmarknadsföring etc. Dessa träd konstrueras genom att följa en algoritm som ID3, CART. Dessa algoritmer hittar olika sätt att dela upp data i partitioner.

Det är den mest kända övervakade inlärningstekniken som används i maskininlärning och mönsteranalys. Beslutsträdarna förutsäger värdena på målvariabeln genom att bygga modeller genom att lära sig av den träningssats som systemet tillhandahåller.

Vi hoppas att du har lärt dig allt om beslutsträdbrytning från denna informativa handledning !!

PREV-handledning | NÄSTA självstudie

Rekommenderad läsning

• Exempel på datautvinning: De vanligaste tillämpningarna av datautvinning 2021
• Data Mining Techniques: Algorithm, Methods & Top Data Mining Tools
• Data Mining: Process, Techniques & Major Issues In Data Analysis
• B Tree och B + Tree Datastruktur i C ++
• Datastruktur för binärt träd i C ++
• Data Mining Process: Modeller, involverade processsteg och utmaningar
• AVL-träd- och högdatastruktur i C ++
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning