Primeri algoritma drevesa odločanja v rudarjenju podatkov

decision tree algorithm examples data mining

Ta poglobljena vadnica pojasnjuje vse o algoritmu drevesa odločanja pri rudarjenju podatkov. Spoznali boste primere dreves odločanja, algoritem in razvrstitev:

Ogledali smo si nekaj Primeri podatkovnega rudarjenja v naši prejšnji vadnici v Brezplačna serija za rudarjenje podatkov .

Kopanje dreves odločitev je vrsta tehnike rudarjenja podatkov, ki se uporablja za izdelavo modelov klasifikacije. Tako kot njegovo ime gradi klasifikacijske modele v obliki drevesne strukture. Ta vrsta rudarjenja spada v nadzorovano učno učenje.

Pri nadzorovanem učenju je ciljni rezultat že znan. Drevesa odločitev lahko uporabimo za kategorične in numerične podatke. Kategorični podatki predstavljajo spol, zakonsko stanje itd., Numerični podatki pa starost, temperaturo itd.

aplikacije za pretvorbo videoposnetkov YouTube v mp3

Primer drevesa odločitev z naborom podatkov je prikazan spodaj.

(slika vir )

Kaj se boste naučili:

• Kakšna je uporaba drevesa odločitev?
• Analiza klasifikacije
• Regresijska analiza
• Kako deluje drevo odločitev?
• Indukcijski algoritem drevesa odločitev
• Indukcija drevesa odločitev
• VOZIČEK
• Indukcija drevesa odločitev za strojno učenje: ID3
• Kaj je pohlepno rekurzivno binarno cepljenje?
• Kako izbrati atribute za ustvarjanje drevesa?
  • # 1) Pridobivanje informacij
  • # 2) Razmerje dobička
  • # 3) Ginijev indeks
• Prekomerno opremljanje v drevesih odločanja
• Kaj je obrezovanje dreves?
• Kaj je napovedno modeliranje?
• Prednosti klasifikacije dreves odločanja
• Slabosti klasifikacije dreves odločanja
• Zaključek
• Priporočeno branje

Kakšna je uporaba drevesa odločitev?

Drevo odločitev se uporablja za izdelavo klasifikacijskih in regresijskih modelov. Uporablja se za ustvarjanje podatkovnih modelov, ki bodo predvidevali oznake razredov ali vrednosti za postopek odločanja. Modeli so zgrajeni iz nabora podatkov o usposabljanju, ki se vnaša v sistem (nadzorovano učenje).

Z uporabo drevesa odločitev lahko vizualiziramo odločitve, ki jih je enostavno razumeti, zato je to priljubljena tehnika rudarjenja podatkov.

Analiza klasifikacije

Klasifikacija podatkov je oblika analize, ki gradi model, ki opisuje pomembne spremenljivke razreda.Na primer, model, zasnovan za kategorizacijo zahtevkov za bančna posojila kot varnih ali tveganih. Metode klasifikacije se uporabljajo pri strojnem učenju in prepoznavanju vzorcev.

Uporaba klasifikacije vključuje odkrivanje goljufij, medicinsko diagnozo, ciljno trženje itd. Rezultat problema s klasifikacijo je vzet kot 'Način' vseh opaženih vrednosti terminalnega vozlišča.

Sledi dvostopenjski postopek za izdelavo klasifikacijskega modela.

1. V prvem koraku, to je učenje: Izdelan je klasifikacijski model, ki temelji na podatkih o usposabljanju.
2. V drugem koraku, to je klasifikacija, se preveri natančnost modela in nato model uporabi za razvrščanje novih podatkov. Oznake razredov, predstavljene tukaj, so v obliki ločenih vrednosti, kot so 'da' ali 'ne', 'varno' ali 'tvegano'.

Splošni pristop za klasifikacijske modele zgradb je podan spodaj:

(slika vir )

Regresijska analiza

Regresijska analiza se uporablja za napovedovanje numeričnih lastnosti.

Numerične atribute imenujemo tudi neprekinjene vrednosti. Model, zgrajen za napovedovanje zveznih vrednosti namesto oznak razredov, se imenuje regresijski model. Rezultat regresijske analize je 'srednja vrednost' vseh opaženih vrednosti vozlišča.

Kako deluje drevo odločitev?

Drevo odločitev je nadzorovan učni algoritem, ki deluje tako za diskretne kot za neprekinjene spremenljivke. Nabor podatkov razdeli na podnabore na podlagi najpomembnejšega atributa v naboru podatkov. Kako drevo odločitev prepozna ta atribut in kako se to razdeli, določajo algoritmi.

Najpomembnejši napovedovalec je označen kot korensko vozlišče, razdelitev se izvede, da se tvorijo podvozla, imenovana odločitvena vozlišča, vozlišča, ki se ne delijo naprej, pa so terminalna ali listna vozlišča.

V drevesu odločitev je nabor podatkov razdeljen na homogena in neprekrivajoča se območja. Sledi pristopu od zgoraj navzdol, saj zgornja regija predstavlja vsa opažanja na enem samem mestu, ki se razdeli na dve ali več vej, ki se še razdelijo. Ta pristop se imenuje tudi a pohlepni pristop saj upošteva samo trenutno vozlišče med obdelanimi, ne da bi se osredotočil na prihodnja vozlišča.

Algoritmi drevesa odločitev se bodo še naprej izvajali, dokler ne bodo dosežena merila zaustavitve, kot je najmanjše število opazovanj itd.

Ko je neko drevo odločitev zgrajeno, lahko številna vozlišča predstavljajo odstopanja ali hrupne podatke. Za odstranjevanje neželenih podatkov se uporablja metoda obrezovanja dreves. To pa izboljša natančnost klasifikacijskega modela.

Za natančnost modela se uporablja testni sklop, sestavljen iz testnih sklopov in oznak razredov. Odstotek nabora testnih sklopov je model pravilno razvrščen, da se ugotovi natančnost modela. Če se ugotovi, da je model natančen, se uporablja za razvrščanje podatkovnih sklopov, za katere oznake razredov niso znane.

Nekateri algoritmi drevesa odločitev vključujejo Huntov algoritem, ID3, CD4.5 in CART.

Primer izdelave drevesa odločitev

(Primer je vzet iz konceptov rudarjenja podatkov: Han in Kimber)

# 1) Učni korak: Podatki o vadbi se vnesejo v sistem, ki ga analizira klasifikacijski algoritem. V tem primeru je oznaka razreda atribut, tj. 'Odločitev o posojilu'. Model, ki temelji na teh podatkih o usposabljanju, je predstavljen v obliki pravil odločanja.

# 2) Razvrstitev: Testni nabor podatkov se doda modelu, da preveri natančnost pravila razvrščanja. Če model daje sprejemljive rezultate, se uporabi za nov nabor podatkov z neznanimi spremenljivkami razreda.

Indukcijski algoritem drevesa odločitev

Indukcija drevesa odločitev

Indukcija odločitvenega drevesa je metoda učenja dreves odločanja iz vadbenega sklopa. Komplet za usposabljanje je sestavljen iz atributov in oznak predavanj. Aplikacije indukcije dreves odločanja vključujejo astronomijo, finančno analizo, medicinsko diagnozo, proizvodnjo in proizvodnjo.

Drevo odločanja je drevesni strukturi, podobni diagramu poteka, ki je narejena iz nastavljenih nabora. Nabor podatkov je razdeljen na manjše podnabore in je prisoten v obliki vozlišč drevesa. Drevesna struktura ima korensko vozlišče, notranja vozlišča ali vozlišča odločanja, listno vozlišče in veje.

Koreninsko vozlišče je najvišje vozlišče. Predstavlja najboljši atribut, izbran za razvrstitev. Notranja vozlišča odločitvenih vozlišč predstavljajo preizkus atributa listnega vozlišča ali terminalnega vozlišča nabora podatkov, ki predstavlja oznako klasifikacije ali odločitve. Podružnice prikazujejo rezultat opravljenega testa.

Nekatera drevesa odločitev imajo le binarna vozlišča , to pomeni natančno dve veji vozlišča, medtem ko so nekatera drevesa odločitev nebinarna.

Spodnja slika prikazuje drevo odločitev za nabor podatkov Titanic, da napove, ali bo potnik preživel ali ne.

(slika vir )

VOZIČEK

Model CART, tj. Klasifikacijski in regresijski modeli, je algoritem drevesa odločanja za gradnjo modelov. Model odločitvenega drevesa, pri katerem imajo ciljne vrednosti diskretno naravo, se imenuje klasifikacijski model.

Diskretna vrednost je končna ali štetje neskončna množica vrednosti, Na primer, starost, velikost itd. Modeli, pri katerih so ciljne vrednosti predstavljene z neprekinjenimi vrednostmi, so običajno številke, ki se imenujejo regresijski modeli. Neprekinjene spremenljivke so spremenljivke s plavajočo vejico. Ta dva modela skupaj imenujemo CART.

CART uporablja Ginijev indeks kot matrico klasifikacije.

Indukcija drevesa odločitev za strojno učenje: ID3

V poznih sedemdesetih in zgodnjih osemdesetih je bil J.Ross Quinlan raziskovalec, ki je zgradil algoritem drevesa odločitev za strojno učenje. Ta algoritem je znan kot ID3, ponovitveni dihotomizator . Ta algoritem je bil razširitev konceptnih učnih sistemov, ki so jih opisali E.B Hunt, J in Marin.

ID3 je pozneje postal znan kot C4.5. ID3 in C4.5 sledita pohlepnemu pristopu od zgoraj navzdol pri gradnji dreves odločanja. Algoritem se začne z naborom podatkov o usposabljanju z oznakami razredov, ki so razdeljene v manjše podmnožice, ko je drevo izdelano.

# 1) Sprva obstajajo trije parametri, tj. seznam atributov, metoda izbire atributov in podatkovna particija . Seznam atributov opisuje atribute nabora vadbenih nizov.

#two) Metoda izbire atributov opisuje metodo za izbiro najboljšega atributa za diskriminacijo med torti. Metodi, ki se uporabljajo za izbiro atributov, so lahko pridobitev informacij ali indeks Gini.

# 3) Strukturo drevesa (binarno ali nebinarno) določa metoda izbire atributov.

# 4) Pri gradnji drevesa odločitev se začne kot eno vozlišče, ki predstavlja korice.

# 5) Če nabori korenskega vozlišča predstavljajo različne oznake razredov, potem pokliče metodo izbire atributov, da razdeli ali razdeli nabore. Korak bo privedel do oblikovanja podružnic in odločitvenih vozlišč.

# 6) Metoda delitve bo določila, kateri atribut je treba izbrati za razdelitev podatkovnih naborov. Določa tudi veje, ki jih je treba gojiti iz vozlišča glede na izid testa. Glavni motiv meril za delitev je, da mora particija na vsaki veji odločitvenega drevesa predstavljati isto oznako razreda.

Primer atributa delitve je prikazan spodaj:

vprašanja in odgovori s kuharskim orodjem

a. Zgornji del je diskretno ovrednoten.

b. Zgornji del je namenjen neprekinjeni vrednosti.

# 7) Zgornjim korakom razdeljevanja se sledi rekurzivno, da se oblikuje drevo odločitev za nabora nabora podatkov o vadbi.

# 8) Ločevanje se ustavi šele, ko so narejene vse particije ali če preostalih naborov ni mogoče nadalje razdeliti.

# 9) Zapletenost algoritma opisuje n * | D | * dnevnik | D | kjer je n število atributov v naboru podatkov D in | D | je število nabora.

Kaj je pohlepno rekurzivno binarno cepljenje?

Pri binarni metodi delitve se nabori razdelijo in izračuna se vsaka funkcija stroškov delitve. Izbrana je najnižja delitev stroškov. Metoda delitve je binarna, ki je oblikovana kot 2 veji. Po naravi je rekurzivna, saj se ista metoda (izračun stroškov) uporablja za razdelitev ostalih sklopov nabora podatkov.

Ta algoritem se imenuje tako požrešen, saj se osredotoča samo na trenutno vozlišče. Osredotoča se na znižanje stroškov, druga vozlišča pa se prezrejo.

Kako izbrati atribute za ustvarjanje drevesa?

Ukrepi za izbiro lastnosti se imenujejo tudi pravila razdeljevanja, da se odloči, kako se bodo cepi razdelili. Merila za razdelitev se uporabljajo za najboljšo razdelitev nabora podatkov. Ti ukrepi zagotavljajo razvrstitev atributov za razdelitev vadbenih kompletov.

Najbolj priljubljene metode izbire atributa so pridobivanje informacij, Ginijev indeks.

# 1) Pridobivanje informacij

Ta metoda je glavna metoda, ki se uporablja za gradnjo dreves odločanja. Zmanjšuje informacije, ki so potrebne za razvrstitev nabora. Zmanjšuje število testov, ki so potrebni za razvrstitev danega korita. Izbran je atribut z največjim pridobivanjem informacij.

Izvirne informacije, potrebne za razvrstitev korita v naboru podatkov D, so podane z:

Kjer je p verjetnost, da nabor spada v razred C. Podatki so kodirani v bitih, zato se uporablja dnevnik v bazo 2. E (s) predstavlja povprečno količino informacij, ki je potrebna za ugotavljanje oznake razreda nabora podatkov D. Prav tako se imenuje ta dobiček Entropija .

Podatki, potrebni za natančno razvrstitev po razdelitvi, so podani po formuli:

Kjer je P (c) teža predelne stene. Te informacije predstavljajo informacije, potrebne za razvrstitev nabora podatkov D na delitev s strani X.

Pridobivanje informacij je razlika med izvirnimi in pričakovanimi informacijami, ki so potrebne za razvrstitev sklopov nabora podatkov D.

Pridobivanje je zmanjšanje informacij, ki ga zahteva poznavanje vrednosti X. Atribut z največjim pridobivanjem informacij je izbran kot 'najboljši'.

# 2) Razmerje dobička

Pridobivanje informacij lahko včasih povzroči, da se razvrščanje za razvrščanje ne uporabi. Vendar razmerje dobička razdeli nabor podatkov o vadbi na particije in upošteva število nabora rezultatov glede na skupno število nabora. Atribut z razmerjem največjega dobička se uporablja kot atribut razdelitve.

# 3) Ginijev indeks

Ginijev indeks se izračuna samo za binarne spremenljivke. Meri nečistočo v vadbenih sklopih nabora podatkov D, as

P je verjetnost, da torta spada v razred C. Ginijev indeks, ki se izračuna za binarni deljeni nabor podatkov D z atributom A, je podan z:

Kjer je n n-ta particija nabora podatkov D.

Zmanjšanje nečistoče je določeno z razliko Ginijevega indeksa prvotnega nabora podatkov D in Ginijevega indeksa po razdelitvi po atributu A.

Kot najboljši atribut za cepitev je izbrano največje zmanjšanje nečistoče ali največji Ginijev indeks.

Prekomerno opremljanje v drevesih odločanja

Prekomerno opremljanje se zgodi, ko poskuša drevo odločitve biti čim bolj popolno s povečanjem globine testov in s tem zmanjša napako. Posledica tega so zelo zapletena drevesa in vodi do prekomerne opremljenosti.

Prekomerno opremljanje zmanjša napovedno naravo drevesa odločanja. Pristopi za preprečevanje prekomerne opremljenosti dreves vključujejo predrezo in obrezovanje.

Kaj je obrezovanje dreves?

Obrezovanje je metoda odstranjevanja neuporabljenih vej z odločitvenega drevesa. Nekatere veje drevesa odločitev lahko predstavljajo odstopanja ali hrupne podatke.

Obrezovanje dreves je metoda za zmanjšanje neželenih vej drevesa. To bo zmanjšalo zapletenost drevesa in pomagalo pri učinkoviti napovedni analizi. Zmanjša prekomerno opremljanje, saj z dreves odstrani nepomembne veje.

Obstajata dva načina obrezovanja drevesa:

# 1) Priprava : Pri tem pristopu se gradnja drevesa odločitev ustavi predčasno. To pomeni, da je odločeno, da vej ne bomo več delili. Zadnje zgrajeno vozlišče postane listno vozlišče in to listno vozlišče ima lahko najpogostejši razred med naborami.

Ukrepi za izbiro lastnosti se uporabljajo za ugotavljanje uteži razdelitve. Mejne vrednosti so predpisane za odločitev, kateri deli se štejejo za koristne. Če ima del vozlišča delitev s padcem pod prag, se postopek ustavi.

# 2) naknadno obrezovanje : Ta metoda odstrani veje iz popolnoma zraslega drevesa. Neželene veje odstranimo in nadomestimo z listnim vozliščem, ki označuje najpogostejšo oznako razreda. Ta tehnika zahteva več računanja kot predhodna obrezovanje, vendar je bolj zanesljiva.

Obrezana drevesa so bolj natančna in kompaktna v primerjavi z neobrezanimi drevesi, vendar imajo pomanjkljivost razmnoževanja in ponavljanja.

Ponovitev se zgodi, ko se isti atribut vedno znova preizkuša vzdolž veje drevesa. Replikacija se pojavi, ko so v drevesu prisotni podvojeni poddelovi. Ta vprašanja je mogoče rešiti z multivariatnimi razdelitvami.

Spodnja slika prikazuje neobrezano in obrezano drevo.

Primer algoritma drevesa odločanja

Primer Vir

Izdelava drevesa odločitev

Vzemimo si primer nabora podatkov o vremenu za zadnjih 10 dni z atributi obeti, temperatura, veter in vlaga. Spremenljivka rezultata bo igrala kriket ali ne. Za izdelavo drevesa odločitev bomo uporabili algoritem ID3.

Korak 1: Prvi korak bo ustvarjanje korenskega vozlišča.

2. korak: Če so vsi rezultati pritrdilni, se vrne listno vozlišče 'da', sicer pa vozlišče 'ne'.

3. korak: Poiščite Entropijo vseh opazovanj in entropijo z atributom 'x', ki je E (S) in E (S, x).

4. korak: Poiščite informacijski dobiček in izberite atribut z visokim informacijskim dobičkom.

5. korak: Zgornje korake ponavljajte, dokler niso zajeti vsi atributi.

Izračun entropije:

Da ne

9 5

Če je entropija nič, to pomeni, da vsi člani pripadajo istemu razredu, če pa je entropija ena, to pomeni, da polovica nabora pripada enemu razredu, eden pa drugemu razredu. 0,94 pomeni pravično razdelitev.

Poiščite atribut pridobivanja informacij, ki omogoča največji dobiček informacij.

Na primer »Veter« ima dve vrednosti: močan in šibek, torej x = {močan, šibek}.

Poiščite H (x), P (x) za x = šibko in x = močno. H (S) je že izračunan zgoraj.

Šibko = 8

Močna = 8

kako odpreti datoteko bin windows 10

Za 'šibek' veter jih 6 reče 'Da' za igranje kriketa, 2 pa 'Ne'. Entropija bo torej:

Za 'močan' veter je 3 reklo 'Ne' za igranje kriketa, 3 pa 'Da'.

To kaže na popolno naključnost, saj polovica predmetov pripada enemu razredu, preostala polovica pa drugim.

Izračunajte pridobitev informacij,

Podobno je pridobivanje informacij za druge atribute:

Atribut outlook ima najvišja pridobitev informacij 0,246, zato je izbran kot koren.

Oblačno ima 3 vrednosti: sončno, oblačno in deževno. Oblačno z igranjem kriketa je vedno 'Da'. Tako se konča z listnim vozliščem, 'da'. Za ostale vrednosti 'Sončno' in 'Dež'.

Tabela za Outlook kot »sončno« bo:

Entropija za 'Outlook' 'Sunny' je:

Pridobitev informacij za atribute glede na Sunny je:

Pridobivanje informacij o vlažnosti je največje, zato je izbrano kot naslednje vozlišče. Podobno se izračuna entropija za dež. Veter daje največ informacij .

Drevo odločitev bi izgledalo spodaj:

Kaj je napovedno modeliranje?

Klasifikacijski modeli se lahko uporabljajo za napovedovanje rezultatov neznanega nabora lastnosti.

Ko je v model vstavljen nabor podatkov z neznanimi oznakami razredov, mu bo samodejno dodelil oznako razreda. Ta metoda uporabe verjetnosti za napovedovanje rezultatov se imenuje napovedno modeliranje.

Prednosti klasifikacije dreves odločanja

Spodaj so navedene različne prednosti razvrščanja dreves odločanja:

1. Klasifikacija dreves odločitev ne zahteva nobenega znanja domene, zato je primerna za postopek odkrivanja znanja.
2. Predstavitev podatkov v obliki drevesa je človeku lahko razumljiva in je intuitivna.
3. Lahko obdeluje večdimenzionalne podatke.
4. To je hiter postopek z veliko natančnostjo.

Slabosti klasifikacije dreves odločanja

Spodaj so navedeni različni znaki razvrščanja dreves odločanja:

1. Včasih postanejo drevesa odločanja zelo zapletena in jih imenujemo preveč opremljena drevesa.
2. Algoritem drevesa odločitev morda ni optimalna rešitev.
3. Drevesa odločitev lahko vrnejo pristransko rešitev, če nad njo prevladuje neka oznaka razreda.

Zaključek

Odločitvena drevesa so tehnike rudarjenja podatkov za klasifikacijo in regresijsko analizo.

Ta tehnika se zdaj razteza na številnih področjih, kot so medicinska diagnoza, ciljno trženje itd. Ta drevesa so zgrajena po algoritmu, kot je ID3, CART. Ti algoritmi najdejo različne načine za razdelitev podatkov na particije.

To je najbolj znana tehnika nadzorovanega učenja, ki se uporablja pri strojnem učenju in analizi vzorcev. Drevesa odločitev napovejo vrednosti ciljne spremenljivke z gradnjo modelov z učenjem iz sklopa vadb, ki je na voljo sistemu.

Upamo, da ste vse o rudarjenju dreves odločitev izvedeli iz te informativne vadnice !!

PREV Vadnica | NASLEDNJA Vadnica

Priporočeno branje

• Primeri rudarjenja podatkov: najpogostejše uporabe podatkovnega rudarjenja 2021
• Tehnike rudarjenja podatkov: algoritem, metode in najboljša orodja za rudarjenje podatkov
• Podatkovno rudarjenje: postopek, tehnike in glavna vprašanja pri analizi podatkov
• Struktura podatkov o drevesu B in drevesu B + v jeziku C ++
• Struktura podatkov binarnega drevesa v jeziku C ++
• Proces rudarjenja podatkov: vključeni modeli, koraki in izzivi
• Struktura podatkov drevesa in kopice AVL v jeziku C ++
• Data Mining Vs Machine Learning Vs Umetna inteligenca Vs Poglobljeno učenje