Eksempler på beslutningstræalgoritme i datamining

decision tree algorithm examples data mining

Denne dybdegående vejledning forklarer alt om beslutningstræalgoritme i datamining. Du lærer om eksempler på beslutningstræer, algoritme og klassificering:

Vi kiggede på et par Eksempler på dataudvinding i vores tidligere tutorial i Gratis Data Mining Training Series .

Decision Tree Mining er en type data miningsteknik, der bruges til at opbygge klassificeringsmodeller. Det bygger klassificeringsmodeller i form af en trælignende struktur, ligesom navnet. Denne type minedrift hører til overvåget klasselæring.

I overvåget læring er målresultatet allerede kendt. Beslutningstræer kan bruges til både kategoriske og numeriske data. De kategoriske data repræsenterer køn, civilstand osv., Mens de numeriske data repræsenterer alder, temperatur osv.

rekursiv flettsortering c ++

Et eksempel på et beslutningstræ med datasættet er vist nedenfor.

(billede kilde )

Hvad du vil lære:

• Hvad er brugen af ​​et beslutningstræ?
• Klassificeringsanalyse
• Regressions analyse
• Hvordan fungerer et beslutningstræ?
• Beslutningstræ induktionsalgoritme
• Beslutningstræ induktion
• VOGN
• Beslutningstræinduktion til maskinindlæring: ID3
• Hvad er grådig rekursiv binær opdeling?
• Hvordan vælges attributter til oprettelse af et træ?
  • # 1) Informationsgevinst
  • # 2) Gain Ratio
  • # 3) Gini-indeks
• Overmontering i beslutningstræer
• Hvad er træbeskæring?
• Hvad er forudsigelig modellering?
• Fordele ved beslutningstræsklassificering
• Ulemper ved beslutningstræsklassificering
• Konklusion
• Anbefalet læsning

Hvad er brugen af ​​et beslutningstræ?

Decision Tree bruges til at oprette klassificerings- og regressionsmodeller. Det bruges til at oprette datamodeller, der forudsiger klassemærker eller værdier til beslutningsprocessen. Modellerne er bygget fra det træningsdatasæt, der tilføres systemet (overvåget læring).

Ved hjælp af et beslutningstræ kan vi visualisere de beslutninger, der gør det let at forstå, og det er således en populær dataminingsteknik.

Klassificeringsanalyse

Dataklassificering er en form for analyse, der bygger en model, der beskriver vigtige klassevariabler.For eksempel, en model bygget til at kategorisere ansøgninger om banklån som sikre eller risikable. Klassificeringsmetoder bruges i maskinindlæring og genkendelse af mønstre.

Anvendelse af klassifikation inkluderer afsløring af svig, medicinsk diagnose, målmarkedsføring osv. Outputet af klassificeringsproblemet betragtes som 'Mode' for alle observerede værdier i terminalnoden.

En to-trins proces følges for at opbygge en klassificeringsmodel.

1. I det første trin dvs. læring: En klassificeringsmodel baseret på træningsdata er bygget.
2. I det andet trin, dvs. klassificering, kontrolleres nøjagtigheden af ​​modellen, og derefter bruges modellen til at klassificere nye data. Klassemærkaterne præsenteret her er i form af diskrete værdier som “ja” eller “nej”, “sikkert” eller “risikabelt”.

Den generelle tilgang til bygningsklassificeringsmodeller er angivet nedenfor:

(billede kilde )

Regressions analyse

Regressionsanalyse bruges til forudsigelse af numeriske attributter.

Numeriske attributter kaldes også kontinuerlige værdier. En model bygget til at forudsige de kontinuerlige værdier i stedet for klassemærker kaldes regressionsmodellen. Output af regressionsanalyse er 'middelværdien' af alle observerede værdier for knudepunktet.

Hvordan fungerer et beslutningstræ?

Et beslutningstræ er en overvåget læringsalgoritme, der fungerer for både diskrete og kontinuerlige variabler. Det opdeler datasættet i undergrupper på basis af den mest betydningsfulde attribut i datasættet. Hvordan beslutningstræet identificerer denne attribut, og hvordan denne opdeling sker, bestemmes af algoritmerne.

Den mest betydningsfulde forudsigelse er udpeget som rodknudepunktet, opdeling foretages for at danne undernoder kaldet beslutningsnoder, og de noder, der ikke opdeles yderligere, er terminal- eller bladnoder.

I beslutningstræet er datasættet opdelt i homogene og ikke-overlappende regioner. Det følger en top-down-tilgang, da topregionen præsenterer alle observationer på et enkelt sted, der opdeles i to eller flere grene, der yderligere splittes. Denne tilgang kaldes også a grådig tilgang da det kun betragter den aktuelle knude mellem den bearbejdede uden at fokusere på de fremtidige knudepunkter.

Beslutningstræalgoritmerne vil fortsætte med at køre, indtil et stopkriterium såsom minimumsantal observationer osv. Er nået.

Når et beslutningstræ er bygget, kan mange noder repræsentere afvigende eller støjende data. Træbeskæringsmetode anvendes til at fjerne uønskede data. Dette forbedrer igen klassifikationsmodelens nøjagtighed.

For at finde nøjagtigheden af ​​modellen anvendes et testsæt bestående af testtubler og klassemærker. Procentdelene af testsæt-tuplerne klassificeres korrekt af modellen for at identificere nøjagtigheden af ​​modellen. Hvis modellen viser sig at være nøjagtig, bruges den til at klassificere datatupplerne, som klassemærkerne ikke er kendt for.

Nogle af beslutningstræalgoritmerne inkluderer Hunt's Algorithm, ID3, CD4.5 og CART.

Eksempel på oprettelse af et beslutningstræ

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

# 1) Læringstrin: Træningsdataene føres ind i systemet, der skal analyseres af en klassificeringsalgoritme. I dette eksempel er klassemærket attributten dvs. 'lånebeslutning'. Modellen bygget ud fra disse træningsdata er repræsenteret i form af beslutningsregler.

# 2) Klassificering: Testdatasæt tilføres modellen for at kontrollere nøjagtigheden af ​​klassificeringsreglen. Hvis modellen giver acceptable resultater, anvendes den til et nyt datasæt med ukendte klassevariabler.

Beslutningstræ induktionsalgoritme

Beslutningstræ induktion

Beslutningstræinduktion er metoden til at lære beslutningstræerne fra træningssættet. Træningssættet består af attributter og klassemærker. Anvendelser af beslutningstræinduktion inkluderer astronomi, økonomisk analyse, medicinsk diagnose, fremstilling og produktion.

Et beslutningstræ er en flowchart-trælignende struktur, der er lavet af træningssæt-tupler. Datasættet er opdelt i mindre delmængder og er til stede i form af knudepunkter i et træ. Træstrukturen har en rodknude, interne knudepunkter eller beslutningsknudepunkter, bladknude og grene.

Rodknuden er den øverste knude. Det repræsenterer den bedste attribut, der er valgt til klassificering. Interne knudepunkter i beslutningsknudepunkterne repræsenterer en test af en attribut for datasætbladknudepunktet eller terminalknudepunktet, der repræsenterer klassificeringen eller beslutningsetiketten. Grenene viser resultatet af den udførte test.

Nogle beslutningstræer har kun binære noder , det betyder nøjagtigt to grene af en node, mens nogle beslutningstræer er ikke-binære.

Billedet nedenfor viser beslutningstræet for Titanic-datasættet for at forudsige, om passageren vil overleve eller ej.

(billede kilde )

VOGN

CART-model, dvs. klassificerings- og regressionsmodeller, er en beslutningstræalgoritme til opbygning af modeller. Beslutningstræmodel, hvor målværdierne har en diskret karakter, kaldes klassificeringsmodeller.

En diskret værdi er et endeligt eller utalligt uendeligt sæt værdier, For eksempel, alder, størrelse osv. Modellerne, hvor målværdierne er repræsenteret ved kontinuerlige værdier, er normalt tal, der kaldes regressionsmodeller. Kontinuerlige variabler er variabler med flydende punkt. Disse to modeller kaldes sammen CART.

CART bruger Gini Index som klassifikationsmatrix.

Beslutningstræinduktion til maskinindlæring: ID3

I slutningen af ​​1970'erne og begyndelsen af ​​1980'erne var J.Ross Quinlan en forsker, der byggede en beslutningstræalgoritme til maskinlæring. Denne algoritme er kendt som ID3, Iterativ dikotomiser . Denne algoritme var en udvidelse af konceptet læringssystemer beskrevet af E.B Hunt, J og Marin.

ID3 blev senere kendt som C4.5. ID3 og C4.5 følger en grådig top-down-tilgang til konstruktion af beslutningstræer. Algoritmen starter med et træningsdatasæt med klassemærker, der deles i mindre delmængder, når træet konstrueres.

# 1) Oprindeligt er der tre parametre, dvs. attributliste, attributudvælgelsesmetode og datapartition . Attributlisten beskriver attributterne til træningssættet tuples.

#to) Metoden til udvælgelse af attribut beskriver metoden til udvælgelse af den bedste attribut til diskrimination blandt tupler. Metoderne til valg af attribut kan enten være Information Gain eller Gini Index.

# 3) Træets struktur (binær eller ikke-binær) bestemmes ved hjælp af attributvalgsmetoden.

# 4) Når der konstrueres et beslutningstræ, starter det som en enkelt node, der repræsenterer tuplerne.

# 5) Hvis rodknudepunkterne repræsenterer forskellige klassemærker, kalder den en attributudvælgelsesmetode til at opdele eller opdele tuplerne. Trinet vil føre til dannelse af grene og beslutningsknudepunkter.

# 6) Opdelingsmetoden bestemmer, hvilken attribut der skal vælges for at opdele datatupperne. Det bestemmer også de grene, der skal dyrkes fra noden i henhold til testresultatet. Hovedmotivet for opdelingskriterierne er, at partitionen ved hver gren af ​​beslutningstræet skal repræsentere det samme klassemærke.

Et eksempel på opdelingsattribut er vist nedenfor:

en. Portionen ovenfor er diskret værdsat.

b. Delingen ovenfor er til kontinuerlig værdi.

# 7) Ovenstående partitioneringstrin følges rekursivt for at danne et beslutningstræ for træningsdatasættet tuples.

# 8) Portioneringen stopper kun, når enten alle skillevægge er lavet, eller når de resterende tupler ikke kan opdeles yderligere.

# 9) Kompleksiteten af ​​algoritmen er beskrevet af n * | D | * log | D | hvor n er antallet af attributter i træningsdatasættet D og | D | er antallet af tupler.

Hvad er grådig rekursiv binær opdeling?

I metoden med binær opdeling deles tuplerne, og hver splitomkostningsfunktion beregnes. Den laveste omkostningsopdeling er valgt. Opdelingsmetoden er binær, som er dannet som 2 grene. Det er rekursivt, da den samme metode (beregning af omkostningerne) bruges til at opdele de andre tupler i datasættet.

Denne algoritme kaldes så grådig, da den kun fokuserer på den aktuelle node. Det fokuserer på at sænke omkostningerne, mens de andre noder ignoreres.

Hvordan vælges attributter til oprettelse af et træ?

Mål for attributudvælgelse kaldes også opdelingsregler for at bestemme, hvordan tuplerne skal opdeles. Opdelingskriterierne bruges til bedst at opdele datasættet. Disse foranstaltninger giver en rangordning af attributterne til opdeling af uddannelsestuberne.

De mest populære metoder til valg af attribut er informationsgevinst, Gini-indeks.

# 1) Informationsgevinst

Denne metode er den vigtigste metode, der bruges til at bygge beslutningstræer. Det reducerer de oplysninger, der kræves for at klassificere tuplerne. Det reducerer antallet af tests, der er nødvendige for at klassificere den givne tuple. Attributten med den højeste informationsgevinst er valgt.

De originale oplysninger, der er nødvendige for klassificering af en tuple i datasæt D, gives af:

Hvor p er sandsynligheden for, at tuplen tilhører klasse C. Oplysningerne er kodet i bits, derfor bruges log til basen 2. E (s) repræsenterer den gennemsnitlige mængde information, der kræves for at finde ud af klassemærket for datasættet D. Denne informationsgevinst kaldes også Entropi .

De nødvendige oplysninger til nøjagtig klassificering efter portionering er givet med formlen:

Hvor P (c) er vægten af ​​skillevæggen. Disse oplysninger repræsenterer de oplysninger, der er nødvendige for at klassificere datasættet D ved deling med X.

Informationsgevinst er forskellen mellem den oprindelige og forventede information, der kræves for at klassificere tuplerne i datasættet D.

Gain er reduktionen af ​​information, der kræves ved at kende værdien af ​​X. Attributten med den højeste informationsgevinst vælges som 'bedst'.

# 2) Gain Ratio

Informationsgevinst kan undertiden resultere i portionering ubrugelig til klassificering. Forstærkningsforholdet opdeler imidlertid træningsdatasættet i partitioner og overvejer antallet af tupler af resultatet i forhold til de samlede tupler. Attributten med det maksimale forstærkningsforhold bruges som en opdelingsattribut.

# 3) Gini-indeks

Gini-indeks beregnes kun for binære variabler. Det måler urenheden i træningspropper af datasæt D, som

P er sandsynligheden for, at tuple tilhører klasse C. Gini-indekset, der beregnes for binært splitdatasæt D ved attribut A, er givet ved:

Hvor n er den nte partition af datasættet D.

Reduktionen i urenhed er givet ved forskellen i Gini-indekset i det originale datasæt D og Gini-indekset efter partition med attribut A.

Den maksimale reduktion i urenhed eller maksimalt Gini-indeks er valgt som den bedste attribut til opdeling.

Overmontering i beslutningstræer

Overmontering sker, når et beslutningstræ forsøger at være så perfekt som muligt ved at øge dybden af ​​testene og derved reducere fejlen. Dette resulterer i meget komplekse træer og fører til overmontering.

Overmontering reducerer beslutningstræets forudsigelige karakter. Fremgangsmåderne for at undgå overmontering af træerne inkluderer beskæring og efterbeskæring.

Hvad er træbeskæring?

Beskæring er metoden til at fjerne de ubrugte grene fra beslutningstræet. Nogle grene af beslutningstræet kan repræsentere afvigende eller støjende data.

Træbeskæring er metoden til at reducere de uønskede grene af træet. Dette vil reducere træets kompleksitet og hjælpe med effektiv forudsigelig analyse. Det reducerer overmontering, da det fjerner de uvigtige grene fra træerne.

Der er to måder at beskære træet på:

# 1) Forbeskæring : I denne tilgang stoppes opførelsen af ​​beslutningstræet tidligt. Det betyder, at det besluttes ikke at opdele filialerne yderligere. Den sidst konstruerede knude bliver bladknude, og denne bladknude kan indeholde den hyppigste klasse blandt tuplerne.

Mål for attributudvælgelse bruges til at finde ud af opdelingen. Tærskelværdier foreskrives for at bestemme, hvilke opdelinger der betragtes som nyttige. Hvis delingen af ​​noden resulterer i opdeling ved at falde under tærsklen, stoppes processen.

# 2) Efterbeskæring : Denne metode fjerner de yderste grene fra et fuldt vokset træ. De uønskede grene fjernes og erstattes af en bladknude, der angiver den hyppigste klassemærkning. Denne teknik kræver mere beregning end forbeskæring, men den er mere pålidelig.

De beskårne træer er mere præcise og kompakte sammenlignet med ikke-beskårne træer, men de har en ulempe ved replikering og gentagelse.

Gentagelse sker, når den samme attribut testes igen og igen langs en gren af ​​et træ. Replikation opstår, når de duplikerede undertræer findes i træet. Disse problemer kan løses ved multivariate opdelinger.

app, der lader dig spionere på andre telefoner

Billedet nedenfor viser et ubeskåret og beskåret træ.

Eksempel på beslutningstræalgoritme

Eksempel Kilde

Konstruktion af et beslutningstræ

Lad os tage et eksempel på de sidste 10 dages vejrdatasæt med attributter udsigter, temperatur, vind og fugtighed. Resultatvariablen spiller cricket eller ej. Vi bruger ID3-algoritmen til at opbygge beslutningstræet.

Trin 1: Det første trin vil være at oprette en rodnode.

Trin 2: Hvis alle resultater er ja, returneres bladknudepunktet 'ja', ellers returneres bladknudepunktet 'nej'.

hvordan man udskriver en matrix i omvendt rækkefølge java

Trin 3: Find ud af Entropien af ​​alle observationer og entropi med attributten 'x', der er E (S) og E (S, x).

Trin 4: Find ud af informationsgevinsten, og vælg attributten med høj informationsgevinst.

Trin 5: Gentag ovenstående trin, indtil alle attributter er dækket.

Beregning af entropi:

Ja Nej

9 5

Hvis entropi er nul, betyder det, at alle medlemmer tilhører den samme klasse, og hvis entropi er en, betyder det, at halvdelen af ​​tuplerne tilhører en klasse, og en af ​​dem tilhører en anden klasse. 0,94 betyder retfærdig fordeling.

Find attributten informationsgevinst, der giver maksimal informationsgevinst.

For eksempel 'Vind', det tager to værdier: Stærk og svag, derfor x = {Stærk, svag}.

Find ud af H (x), P (x) for x = svag og x = stærk. H (S) er allerede beregnet ovenfor.

Svag = 8

Stærk = 8

For 'svag' vind siger 6 af dem 'Ja' for at spille cricket, og 2 af dem siger 'Nej'. Så entropi vil være:

For “stærk” vind sagde 3 “Nej” for at spille cricket og 3 sagde “Ja”.

Dette viser perfekt tilfældighed, da halvdelen tilhører en klasse, og den resterende halvdel tilhører andre.

Beregn informationsgevinsten,

Tilsvarende er informationsgevinsten for andre attributter:

Attribut outlook har højeste informationsgevinst på 0,246, så det vælges som rod.

Overskyet har 3 værdier: Solrig, Overskyet og Regn. Overskyet med play cricket er altid ”Ja”. Så det ender med en bladknude, “ja”. For de andre værdier “Sunny” og “Rain”.

Tabel til Outlook som 'Sunny' vil være:

Entropi for 'Outlook' 'Sunny' er:

Informationsgevinst for attributter med hensyn til Sunny er:

Informationsgevinsten for fugtighed er højest, derfor vælges den som den næste knude. Tilsvarende beregnes Entropy for regn. Vind giver den højeste informationsgevinst .

Beslutningstræet ser ud nedenfor:

Hvad er forudsigelig modellering?

Klassifikationsmodellerne kan bruges til at forudsige resultaterne af et ukendt sæt attributter.

Når et datasæt med ukendte klassemærker indføres i modellen, tildeles det automatisk klassemærket til det. Denne metode til anvendelse af sandsynlighed for at forudsige resultater kaldes forudsigelig modellering.

Fordele ved beslutningstræsklassificering

Nedenfor er de forskellige fordele ved klassificering af beslutningstræer:

1. Beslutningstræklassificering kræver ikke nogen domæne-viden, derfor er den passende til vidensopdagelsesprocessen.
2. Repræsentationen af ​​data i form af træet forstås let af mennesker, og det er intuitivt.
3. Det kan håndtere flerdimensionelle data.
4. Det er en hurtig proces med stor nøjagtighed.

Ulemper ved beslutningstræsklassificering

Nedenfor er de forskellige ulemper ved klassificering af beslutningstræ:

1. Nogle gange bliver beslutningstræer meget komplekse, og disse kaldes overmonterede træer.
2. Beslutningstræalgoritmen er muligvis ikke en optimal løsning.
3. Beslutningstræerne kan muligvis returnere en partisk løsning, hvis en eller anden klassemærke dominerer den.

Konklusion

Beslutningstræer er dataminingsteknikker til klassificering og regressionsanalyse.

Denne teknik spænder nu over mange områder som medicinsk diagnose, målmarkedsføring osv. Disse træer er konstrueret ved at følge en algoritme som ID3, CART. Disse algoritmer finder forskellige måder at opdele dataene i partitioner.

Det er den mest kendte overvågede læringsteknik, der bruges i maskinlæring og mønsteranalyse. Beslutningstræerne forudsiger værdierne for målvariablen ved at opbygge modeller gennem læring fra det træningssæt, der leveres til systemet.

Vi håber, du har lært alt om Decision Tree Mining fra denne informative tutorial !!

PREV-vejledning | NÆSTE vejledning

Anbefalet læsning

• Eksempler på data minedrift: De mest almindelige anvendelser af Data Mining 2021
• Data Mining Techniques: Algoritme, Metoder & Top Data Mining Tools
• Data Mining: Process, teknikker og større problemer i dataanalyse
• B-træ- og B + -tredatastruktur i C ++
• Datastruktur for binært træ i C ++
• Data Mining Process: Modeller, Process Steps & Challenges Involved
• AVL-træ- og bunndatastruktur i C ++
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning