Beslutningstres algoritmeeksempler i datautvinning

decision tree algorithm examples data mining

Denne grundige veiledningen forklarer alt om beslutningstresalgoritme i datautvinning. Du vil lære om eksempler på beslutningstreet, algoritme og klassifisering:

Vi så på et par Eksempler på datautvinning i vår forrige opplæring i Gratis Data Mining Training Series .

Decision Tree Mining er en type data miningsteknikk som brukes til å bygge klassifiseringsmodeller. Den bygger klassifiseringsmodeller i form av en trelignende struktur, akkurat som navnet. Denne typen gruvedrift tilhører overvåket klasselæring.

I veiledet læring er målresultatet allerede kjent. Beslutningstrær kan brukes til både kategoriske og numeriske data. De kategoriske dataene representerer kjønn, sivilstand osv. Mens de numeriske dataene representerer alder, temperatur osv.

beste ide for python på mac

Et eksempel på et beslutningstreet med datasettet er vist nedenfor.

(bilde kilde )

Hva du vil lære:

• Hva er bruken av et beslutningstreet?
• Klassifiseringsanalyse
• Regresjonsanalyse
• Hvordan fungerer et beslutningstreet?
• Beslutningstreet induksjonsalgoritme
• Beslutningstreet induksjon
• Vogn
• Beslutningstreinduksjon for maskinlæring: ID3
• Hva er grådig rekursiv binær splitting?
• Hvordan velge attributter for å lage et tre?
  • # 1) Informasjonsgevinst
  • # 2) Gevinstforhold
  • # 3) Gini-indeks
• Overmontering i beslutningstrær
• Hva er treskjæring?
• Hva er prediktiv modellering?
• Fordeler med beslutningstreet klassifisering
• Ulemper ved beslutningstreet klassifisering
• Konklusjon
• Anbefalt lesing

Hva er bruken av et beslutningstreet?

Decision Tree brukes til å bygge klassifiserings- og regresjonsmodeller. Den brukes til å lage datamodeller som vil forutsi klassetiketter eller verdier for beslutningsprosessen. Modellene er bygget fra opplæringsdatasettet som blir matet til systemet (veiledet læring).

Ved hjelp av et beslutningstreet kan vi visualisere beslutningene som gjør det enkelt å forstå, og det er dermed en populær data miningsteknikk.

Klassifiseringsanalyse

Dataklassifisering er en form for analyse som bygger en modell som beskriver viktige klassevariabler.For eksempel, en modell bygget for å kategorisere søknader om banklån som trygge eller risikofylte. Klassifiseringsmetoder brukes i maskinlæring og mønstergjenkjenning.

Anvendelse av klassifisering inkluderer oppdagelse av svindel, medisinsk diagnose, målmarkedsføring, etc. Utdataene fra klassifiseringsproblemet blir sett på som 'Mode' for alle observerte verdier i terminalnoden.

En to-trinns prosess følges for å bygge en klassifiseringsmodell.

1. I det første trinnet, dvs. læring: Det bygges en klassifiseringsmodell basert på treningsdata.
2. I det andre trinnet, dvs. klassifisering, blir nøyaktigheten til modellen sjekket, og deretter brukes modellen til å klassifisere nye data. Klassemerkene som presenteres her er i form av diskrete verdier som “ja” eller “nei”, “trygt” eller “risikabelt”.

Den generelle tilnærmingen for klassifiseringsmodeller for bygninger er gitt nedenfor:

(bilde kilde )

Regresjonsanalyse

Regresjonsanalyse brukes for å forutsi numeriske attributter.

Numeriske attributter kalles også kontinuerlige verdier. En modell bygget for å forutsi kontinuerlige verdier i stedet for klassetiketter kalles regresjonsmodellen. Resultatet av regresjonsanalyse er 'gjennomsnittet' av alle observerte verdier i noden.

Hvordan fungerer et beslutningstreet?

Et beslutningstre er en overvåket læringsalgoritme som fungerer for både diskrete og kontinuerlige variabler. Det deler datasettet i delmengder på grunnlag av det viktigste attributtet i datasettet. Hvordan beslutningstreet identifiserer dette attributtet og hvordan denne splittingen gjøres, bestemmes av algoritmene.

Den mest betydningsfulle prediktoren er betegnet som rotnoden, splitting gjøres for å danne undernoder kalt beslutningsnoder, og nodene som ikke deler seg videre er terminal- eller bladnoder.

I beslutningstreet er datasettet delt inn i homogene og ikke-overlappende regioner. Det følger en top-down-tilnærming da toppregionen presenterer alle observasjonene på et enkelt sted som deler seg i to eller flere grener som splittes ytterligere. Denne tilnærmingen kalles også a grådig tilnærming da det bare tar hensyn til den nåværende noden mellom de jobbet uten å fokusere på fremtidige noder.

Beslutningstresalgoritmene vil fortsette å kjøre til et stoppkriterium som minimum antall observasjoner etc. er nådd.

Når et beslutningstreet er bygget, kan mange noder representere outliers eller støyende data. Treskjæringsmetode brukes for å fjerne uønskede data. Dette forbedrer i sin tur nøyaktigheten til klassifiseringsmodellen.

For å finne nøyaktigheten til modellen, brukes et testsett som består av testplater og klassetiketter. Prosentandelen av testsett-tuplene er korrekt klassifisert av modellen for å identifisere nøyaktigheten til modellen. Hvis modellen blir funnet å være nøyaktig, brukes den til å klassifisere datatuplene som klassemerkene ikke er kjent for.

Noen av beslutningstreetalgoritmene inkluderer Hunt's Algorithm, ID3, CD4.5 og CART.

Eksempel på å lage et beslutningstreet

(Eksempel er hentet fra Data Mining Concepts: Han og Kimber)

# 1) Læringstrinn: Treningsdataene mates inn i systemet som skal analyseres av en klassifiseringsalgoritme. I dette eksemplet er klassemerket attributtet, dvs. 'lånebeslutning'. Modellen som er bygd fra disse opplæringsdataene er representert i form av beslutningsregler.

# 2) Klassifisering: Testdatasett blir matet til modellen for å kontrollere nøyaktigheten av klassifiseringsregelen. Hvis modellen gir akseptable resultater, blir den brukt på et nytt datasett med ukjente klassevariabler.

Beslutningstreet induksjonsalgoritme

Beslutningstreet induksjon

Induksjon av beslutningstreet er metoden for å lære beslutningstrærne fra treningssettet. Treningssettet består av attributter og klassetiketter. Anvendelser av beslutningstreet induksjon inkluderer astronomi, økonomisk analyse, medisinsk diagnose, produksjon og produksjon.

Et beslutningstre er et flytdiagram-trelignende struktur som er laget av treningssett-tupler. Datasettet er delt inn i mindre delmengder og er til stede i form av noder i et tre. Trestrukturen har en rotnode, interne noder eller beslutningsnoder, bladnode og grener.

Rotnoden er den øverste noden. Det representerer det beste attributtet valgt for klassifisering. Interne noder til beslutningsnodene representerer en test av et attributt til datasettbladnoden eller terminalnoden som representerer klassifiseringen eller beslutningsetiketten. Grenene viser resultatet av den utførte testen.

Noen beslutningstrær har bare binære noder , det betyr nøyaktig to grener av en node, mens noen beslutningstrær er ikke-binære.

Bildet nedenfor viser beslutningstreet for Titanic-datasettet for å forutsi om passasjeren vil overleve eller ikke.

(bilde kilde )

Vogn

CART-modellen, dvs. klassifiserings- og regresjonsmodeller, er en beslutningstreetalgoritme for å bygge modeller. Beslutningstremodell der målverdiene har en diskret natur kalles klassifiseringsmodeller.

En diskret verdi er et endelig eller utallig uendelig sett med verdier, For eksempel, alder, størrelse osv. Modellene der målverdiene er representert av kontinuerlige verdier er vanligvis tall som kalles regresjonsmodeller. Kontinuerlige variabler er variabler med flytende punkt. Disse to modellene sammen kalles CART.

CART bruker Gini Index som klassifiseringsmatrise.

Beslutningstreinduksjon for maskinlæring: ID3

På slutten av 1970-tallet og tidlig på 1980-tallet var J.Ross Quinlan en forsker som bygde en beslutningstreetalgoritme for maskinlæring. Denne algoritmen er kjent som ID3, Iterativ dikotomiser . Denne algoritmen var en utvidelse av konseptet læringssystemer beskrevet av E.B Hunt, J og Marin.

ID3 ble senere kjent som C4.5. ID3 og C4.5 følger en grådig top-down-tilnærming for å konstruere beslutningstrær. Algoritmen starter med et treningsdatasett med klassetiketter som deles inn i mindre delmengder når treet konstrueres.

#1) I utgangspunktet er det tre parametere, dvs. attributtliste, attributtvalgmetode og datapartisjon . Attributtlisten beskriver attributtene til treningssettet tuples.

#to) Attributtvalgmetoden beskriver metoden for å velge det beste attributtet for diskriminering blant tupler. Metodene som brukes for attributtvalg kan enten være Information Gain eller Gini Index.

# 3) Strukturen til treet (binært eller ikke-binært) avgjøres ved hjelp av attributtvalgmetoden.

# 4) Når du konstruerer et beslutningstreet, starter det som en enkelt node som representerer tuplene.

# 5) Hvis rotnoden tuples representerer forskjellige klassetiketter, kaller den en attributtvalgmetode for å dele eller partisjonere tuplene. Trinnet vil føre til dannelse av grener og beslutningsknuter.

# 6) Oppdelingsmetoden vil avgjøre hvilket attributt som skal velges for å partisjonere datatuplene. Det bestemmer også grenene som skal dyrkes fra noden i henhold til testresultatet. Hovedmotivet til delingskriteriene er at partisjonen ved hver gren av beslutningstreet skal representere samme klassemerke.

Et eksempel på delingsattributt er vist nedenfor:

en. Delingen over er diskret verdsatt.

b. Delingen over er for kontinuerlig verdi.

# 7) De ovennevnte partisjoneringstrinnene følges rekursivt for å danne et beslutningstreet for treningssettet tuples.

# 8) Delingen stopper bare når enten alle partisjonene er laget, eller når de gjenværende tuplene ikke kan deles videre.

# 9) Kompleksiteten til algoritmen er beskrevet av n * | D | * logg | D | hvor n er antall attributter i treningsdatasettet D og | D | er antall tupler.

Hva er grådig rekursiv binær splitting?

I den binære delingsmetoden deles tuplene, og hver delte kostnadsfunksjon beregnes. Den laveste kostnadsdelingen er valgt. Oppdelingsmetoden er binær som dannes som to grener. Det er rekursivt i sin natur, da den samme metoden (beregning av kostnaden) brukes til å dele de andre tuplene i datasettet.

Denne algoritmen kalles så grådig da den kun fokuserer på den nåværende noden. Den fokuserer på å senke kostnadene, mens de andre nodene blir ignorert.

Hvordan velge attributter for å lage et tre?

Attributtvalgstiltak kalles også splitteregler for å bestemme hvordan tuplene skal splittes. Oppdelingskriteriene brukes til å best partisjonere datasettet. Disse tiltakene gir en rangering av attributtene for oppdeling av opplæringstuplene.

De mest populære metodene for å velge attributt er informasjonsgevinst, Gini-indeks.

# 1) Informasjonsgevinst

Denne metoden er hovedmetoden som brukes til å bygge beslutningstrær. Det reduserer informasjonen som kreves for å klassifisere tuplene. Det reduserer antall tester som er nødvendige for å klassifisere den gitte tupelen. Attributtet med høyest informasjonsgevinst er valgt.

Den opprinnelige informasjonen som trengs for klassifisering av en tuple i datasett D, er gitt av:

Hvor p er sannsynligheten for at tupelen tilhører klasse C. Informasjonen er kodet i biter, derfor brukes logg til base 2. E (s) representerer den gjennomsnittlige mengden informasjon som kreves for å finne ut klassetiketten til datasettet D. Denne informasjonsgevinsten kalles også Entropi .

Informasjonen som kreves for nøyaktig klassifisering etter porsjonering, er gitt med formelen:

Hvor P (c) er vekten av partisjonen. Denne informasjonen representerer informasjonen som trengs for å klassifisere datasettet D ved porsjonering med X.

Informasjonsgevinst er forskjellen mellom den opprinnelige og forventede informasjonen som kreves for å klassifisere tuplene i datasettet D.

Gevinst er reduksjon av informasjon som kreves ved å kjenne verdien til X. Attributtet med høyest informasjonsgevinst blir valgt som 'best'.

# 2) Gevinstforhold

Informasjonsgevinst kan noen ganger resultere i porsjonering ubrukelig for klassifisering. Forsterkningsforholdet deler imidlertid treningsdatasettet i partisjoner og vurderer antall tupler av utfallet i forhold til de totale tuplene. Attributtet med maks gevinstforhold brukes som en splittende attributt.

# 3) Gini-indeks

Gini-indeksen beregnes kun for binære variabler. Den måler urenheten i treningstuppene til datasettet D, som

P er sannsynligheten for at tuple tilhører klasse C. Gini-indeksen som beregnes for binært delt datasett D av attributt A er gitt av:

Hvor n er den niende partisjonen av datasettet D.

Reduksjonen av urenhet er gitt av forskjellen i Gini-indeksen til det originale datasettet D og Gini-indeksen etter partisjon av attributt A.

Maksimal reduksjon i urenhet eller maks Gini-indeks er valgt som det beste attributtet for splitting.

Overmontering i beslutningstrær

Overmontering skjer når et beslutningstre prøver å være så perfekt som mulig ved å øke dybden på testene og derved redusere feilen. Dette resulterer i svært komplekse trær og fører til overmontering.

mest populære verktøy for analyse av store data

Overmontering reduserer den prediktive naturen til beslutningstreet. Tilnærmingene for å unngå overmontering av trærne inkluderer beskjæring og etterskjæring.

Hva er treskjæring?

Beskjæring er metoden for å fjerne ubrukte grener fra beslutningstreet. Noen grener av beslutningstreet kan representere avvik eller støyende data.

Treskjæring er metoden for å redusere uønskede grener av treet. Dette vil redusere treets kompleksitet og hjelpe til med effektiv prediktiv analyse. Det reduserer overmontering da det fjerner viktige greiner fra trærne.

Det er to måter å beskjære treet på:

# 1) Forhåndsbeskjæring : I denne tilnærmingen stoppes konstruksjonen av beslutningstreet tidlig. Det betyr at det er besluttet å ikke dele partisjonene ytterligere. Den siste noden som ble konstruert blir bladnoden, og denne bladnoden kan ha den hyppigste klassen blant tuplene.

Målene for attributtvalg brukes til å finne ut vektingen av splittelsen. Terskelverdier er foreskrevet for å bestemme hvilke splittelser som anses som nyttige. Hvis delingen av noden resulterer i splitting ved å falle under terskelen, stoppes prosessen.

# 2) Etterbeskjæring : Denne metoden fjerner yttergrenene fra et fullvokst tre. De uønskede grenene fjernes og erstattes av en bladnode som angir den hyppigste klassemerket. Denne teknikken krever mer beregning enn forhåndsbeskæring, men den er mer pålitelig.

De beskjærte trærne er mer presise og kompakte sammenlignet med ubeskjærte trær, men de har en ulempe med replikasjon og repetisjon.

Gjentakelse skjer når det samme attributtet testes igjen og igjen langs en gren av et tre. Replikering oppstår når duplikat undertrær er tilstede i treet. Disse problemene kan løses ved flere variasjoner.

Bildet nedenfor viser et ubeskåret og beskåret tre.

Eksempel på beslutningstreetalgoritme

Eksempel Kilde

Konstruksjon av et beslutningstreet

La oss ta et eksempel på det siste ti dagers værdatasettet med attributter utsikter, temperatur, vind og fuktighet. Utfallsvariabelen vil spille cricket eller ikke. Vi vil bruke ID3-algoritmen til å bygge beslutningstreet.

Trinn 1: Det første trinnet vil være å opprette en rotnode.

Steg 2: Hvis alle resultatene er ja, vil bladnoden “ja” returneres, ellers vil bladnoden “nei” bli returnert.

Steg 3: Finn ut Entropy av alle observasjoner og entropi med attributtet “x” som er E (S) og E (S, x).

Trinn 4: Finn ut informasjonsgevinsten og velg attributtet med høy informasjonsgevinst.

Trinn 5: Gjenta trinnene ovenfor til alle attributtene er dekket.

Beregning av entropi:

Ja Nei

9 5

Hvis entropi er null, betyr det at alle medlemmene tilhører samme klasse, og hvis entropi er en, betyr det at halvparten av tuplene tilhører en klasse og en av dem tilhører en annen klasse. 0,94 betyr rettferdig fordeling.

Finn informasjonsgevinstattributtet som gir maksimal informasjonsgevinst.

For eksempel 'Vind', det tar to verdier: Sterk og Svak, derfor x = {Sterk, Svak}.

Finn ut H (x), P (x) for x = svak og x = sterk. H (S) er allerede beregnet ovenfor.

Svak = 8

Sterk = 8

For “svak” vind sier 6 av dem “Ja” for å spille cricket og to av dem sier “Nei”. Så entropi vil være:

For “sterk” vind sa 3 “Nei” for å spille cricket og 3 sa “Ja”.

Dette viser perfekt tilfeldighet ettersom halve gjenstander tilhører en klasse og den gjenværende halvparten tilhører andre.

Beregn informasjonsgevinsten,

Tilsvarende er informasjonsgevinsten for andre attributter:

Attributtutsiktene har høyest informasjonsgevinst på 0,246, og dermed blir den valgt som rot.

Overskyet har 3 verdier: Sol, Overskyet og Regn. Overskyet med lek cricket er alltid “Ja”. Så det ender opp med en bladnode, “ja”. For de andre verdiene “Sunny” og “Rain”.

Tabell for Outlook som 'Sunny' vil være:

Entropi for “Outlook” “Sunny” er:

Informasjonsgevinst for attributter med hensyn til Sunny er:

beste gratis optimalisereren for Windows 10

Informasjonsgevinsten for fuktighet er høyest, derfor blir den valgt som neste node. På samme måte beregnes Entropy for Rain. Vind gir høyest informasjonsgevinst .

Beslutningstreet vil se ut som nedenfor:

Hva er prediktiv modellering?

Klassifiseringsmodellene kan brukes til å forutsi resultatene av et ukjent sett med attributter.

Når et datasett med ukjente klassetiketter mates inn i modellen, tildeles det automatisk klassetiketten til det. Denne metoden for å anvende sannsynlighet for å forutsi resultater kalles prediktiv modellering.

Fordeler med beslutningstreet klassifisering

Nedenfor er de forskjellige fordelene ved klassifisering av beslutningstreet:

1. Beslutningstreklassifisering krever ingen domenekunnskap, derfor er det hensiktsmessig for kunnskapsoppdagelsesprosessen.
2. Representasjonen av data i form av treet er lett forståelig for mennesker, og det er intuitivt.
3. Den kan håndtere flerdimensjonale data.
4. Det er en rask prosess med stor nøyaktighet.

Ulemper ved beslutningstreet klassifisering

Nedenfor er de forskjellige ulempene ved Decision Tree Classification:

1. Noen ganger blir beslutningstrær veldig komplekse, og disse kalles overmonterte trær.
2. Beslutningstreetalgoritmen er kanskje ikke en optimal løsning.
3. Beslutningstrærne kan gi en partisk løsning hvis noen klassemerker dominerer den.

Konklusjon

Beslutningstrær er teknikker for datautvinning for klassifisering og regresjonsanalyse.

Denne teknikken spenner nå over mange områder som medisinsk diagnose, målmarkedsføring, etc. Disse trærne er konstruert ved å følge en algoritme som ID3, CART. Disse algoritmene finner forskjellige måter å dele dataene i partisjoner.

Det er den mest kjente overvåket læringsteknikken som brukes i maskinlæring og mønsteranalyse. Beslutningstrærne forutsier verdiene til målvariabelen ved å bygge modeller gjennom å lære av opplæringssettet som er gitt til systemet.

Vi håper du har lært alt om Decision Tree Mining fra denne informative opplæringen !!

PREV Opplæring | NESTE veiledning

Anbefalt lesing

• Data Mining Eksempler: De vanligste applikasjonene av Data Mining 2021
• Data Mining Techniques: Algorithm, Methods & Top Data Mining Tools
• Data Mining: Prosess, teknikker og store problemer i dataanalyse
• B Tree og B + Tree Datastruktur i C ++
• Datastruktur for binært tre i C ++
• Data Mining Process: Modeller, prosessstrinn og utfordringer involvert
• AVL Tree and Heap Datastruktur i C ++
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning