decision tree algorithm examples data mining
Ovaj produbljeni vodič objašnjava sve o algoritmu stabla odlučivanja u rudarstvu podataka. Naučit ćete o primjerima stabla odlučivanja, algoritmu i klasifikaciji:
Pogledali smo nekoliko Primjeri rudarenja podataka u našem prethodnom vodiču u Besplatna serija treninga za rudarenje podataka .
Rudarstvo stabla odluka vrsta je tehnike rudarenja podataka koja se koristi za izgradnju klasifikacijskih modela. Gradi modele klasifikacije u obliku strukture nalik stablu, baš kao i njezino ime. Ova vrsta rudarstva pripada nadgledanom razrednom učenju.
U učenju pod nadzorom, ciljni rezultat je već poznat. Stabla odlučivanja mogu se koristiti i za kategoričke i za numeričke podatke. Kategorički podaci predstavljaju spol, bračno stanje itd., Dok numerički podaci predstavljaju dob, temperaturu itd.
kako izgleda mrežni sigurnosni ključ
Primjer stabla odluka sa skupom podataka prikazan je u nastavku.
[slika izvor ]
Što ćete naučiti:
- Koja je korist od stabla odlučivanja?
- Analiza klasifikacije
- Regresijska analiza
- Kako djeluje stablo odluka?
- Algoritam indukcije stabla odlučivanja
- Indukcija stabla odlučivanja
- KOŠARICA
- Indukcija stabla odluka za strojno učenje: ID3
- Što je pohlepno rekurzivno binarno cijepanje?
- Kako odabrati atribute za stvaranje stabla?
- Prekomjerno uklapanje u stabla odlučivanja
- Što je obrezivanje drveća?
- Što je prediktivno modeliranje?
- Prednosti klasifikacije stabla odlučivanja
- Nedostaci klasifikacije stabla odlučivanja
- Zaključak
- Preporučena literatura
Koja je korist od stabla odlučivanja?
Stablo odluke koristi se za izgradnju modela klasifikacije i regresije. Koristi se za stvaranje podatkovnih modela koji će predvidjeti oznake klasa ili vrijednosti za postupak donošenja odluka. Modeli su izgrađeni od skupa podataka o treningu koji se unose u sustav (nadzirano učenje).
Koristeći stablo odluka, možemo vizualizirati odluke koje olakšavaju razumijevanje, pa je to popularna tehnika rudarenja podataka.
Analiza klasifikacije
Klasifikacija podataka oblik je analize koji gradi model koji opisuje važne varijable klase.Na primjer, model izgrađen za kategorizaciju zahtjeva za bankovne zajmove kao sigurne ili rizične. Metode klasifikacije koriste se u strojnom učenju i prepoznavanju uzoraka.
Primjena klasifikacije uključuje otkrivanje prijevara, medicinsku dijagnozu, ciljni marketing itd. Rezultat problema s klasifikacijom uzima se kao „Način“ svih promatranih vrijednosti terminalnog čvora.
Slijedi se postupak u dva koraka za izgradnju modela klasifikacije.
- U prvom koraku, tj. Učenju: Izgrađen je klasifikacijski model zasnovan na podacima o treningu.
- U drugom koraku, tj. Klasifikaciji, provjerava se točnost modela, a zatim se model koristi za klasifikaciju novih podataka. Oznake klasa koje su ovdje predstavljene u obliku su zasebnih vrijednosti poput 'da' ili 'ne', 'sigurno' ili 'rizično'.
Opći pristup za klasifikacijske modele zgrada dan je u nastavku:
[slika izvor ]
Regresijska analiza
Regresijska analiza koristi se za predviđanje numeričkih atributa.
Numerički atributi nazivaju se i kontinuiranim vrijednostima. Model izgrađen za predviđanje kontinuiranih vrijednosti umjesto oznaka klase naziva se regresijski model. Rezultat regresijske analize je 'sredina' svih promatranih vrijednosti čvora.
Kako djeluje stablo odluka?
Stablo odluke nadzirani je algoritam učenja koji radi i za diskretne i za kontinuirane varijable. Skup podataka dijeli na podskupine na temelju najznačajnijeg atributa u skupu podataka. Kako stablo odluke identificira ovaj atribut i kako se vrši ovo dijeljenje, odlučuju algoritmi.
Najznačajniji prediktor određen je kao korijenski čvor, razdvajanje se vrši kako bi se stvorili podčvorovi koji se nazivaju čvorovi odluke, a čvorovi koji se ne dijele dalje su terminalni ili lisni čvorovi.
U stablu odluka skup podataka podijeljen je na homogena i područja koja se ne preklapaju. Slijedi pristup od vrha prema dolje, jer gornja regija prikazuje sva opažanja na jednom mjestu koje se dijeli na dvije ili više grana koje se dalje dijele. Ovaj pristup se također naziva a pohlepni pristup jer uzima u obzir samo trenutni čvor između obrađenih bez fokusiranja na buduće čvorove.
Algoritmi stabla odluka nastavit će se izvoditi sve dok se ne postignu kriteriji zaustavljanja poput minimalnog broja promatranja itd.
Jednom kada se izgradi stablo odluke, mnogi čvorovi mogu predstavljati odstupanja ili bučne podatke. Za uklanjanje neželjenih podataka primjenjuje se metoda obrezivanja stabla. To, pak, poboljšava točnost klasifikacijskog modela.
Da bi se pronašla točnost modela, koristi se ispitni set koji se sastoji od ispitnih korpica i oznaka klasa. Procenti korpica ispitnih skupova model je pravilno klasificirao kako bi se utvrdila točnost modela. Ako se utvrdi da je model točan, tada se koristi za klasifikaciju skupova podataka za koje oznake klasa nisu poznate.
Neki od algoritama stabla odlučivanja uključuju Huntov algoritam, ID3, CD4.5 i CART.
Primjer izrade stabla odluka
(Primjer je preuzet iz koncepata rudarenja podataka: Han i Kimber)
# 1) Korak učenja: Podaci o treningu unose se u sustav koji se analizira algoritmom klasifikacije. U ovom primjeru oznaka klase je atribut tj. 'Odluka o zajmu'. Model izgrađen na temelju ovih podataka o treningu predstavljen je u obliku pravila odlučivanja.
# 2) Klasifikacija: Skup podataka za testiranje dovodi se u model kako bi se provjerila točnost pravila klasifikacije. Ako model daje prihvatljive rezultate, primjenjuje se na novi skup podataka s nepoznatim varijablama klase.
Algoritam indukcije stabla odlučivanja
Indukcija stabla odlučivanja
Indukcija stabla odlučivanja metoda je učenja stabala odlučivanja iz seta treninga. Set obuke sastoji se od atributa i oznaka razreda. Primjene indukcije stabla odlučivanja uključuju astronomiju, financijsku analizu, medicinsku dijagnozu, proizvodnju i proizvodnju.
Stablo odluke je struktura stabla nalik dijagramu toka koja je izrađena od korpica postavljenih u trening. Skup podataka podijeljen je na manje podskupove i prisutan je u obliku čvorova stabla. Struktura stabla ima korijenski čvor, unutarnje čvorove ili čvorove odlučivanja, čvor lišća i grane.
Korijenski čvor je najviši čvor. Predstavlja najbolji atribut odabran za klasifikaciju. Unutarnji čvorovi čvorova odluke predstavljaju test atributa čvora čvora ili terminalnog čvora skupa koji predstavlja klasifikaciju ili oznaku odluke. Grane pokazuju ishod provedenog testa.
Neka stabla odluke imaju samo binarni čvorovi , to znači točno dvije grane čvora, dok su neka stabla odlučivanja nebinarna.
Slika dolje prikazuje stablo odluke za set podataka Titanic da predvidi hoće li putnik preživjeti ili ne.
[slika izvor ]
KOŠARICA
CART model tj. Klasifikacijski i regresijski modeli algoritam je stabla odlučivanja za izgradnju modela. Model stabla odluke u kojem ciljne vrijednosti imaju diskretnu prirodu naziva se klasifikacijski model.
Diskretna vrijednost je konačan ili brojivo beskonačan skup vrijednosti, Na primjer, dob, veličina itd. Modeli u kojima su ciljne vrijednosti predstavljene kontinuiranim vrijednostima obično su brojevi koji se nazivaju regresijski modeli. Neprekidne varijable su varijable s pomičnom zarezom. Ova dva modela zajedno nazivaju se CART.
CART koristi Gini indeks kao matricu klasifikacije.
Indukcija stabla odluka za strojno učenje: ID3
Krajem 1970-ih i početkom 1980-ih, J.Ross Quinlan bio je istraživač koji je izgradio algoritam stabla odlučivanja za strojno učenje. Ovaj algoritam poznat je pod nazivom ID3, iterativni dihotomizator . Ovaj algoritam bio je proširenje koncepta sustava učenja koji su opisali E.B Hunt, J i Marin.
ID3 je kasnije postao poznat kao C4.5. ID3 i C4.5 slijede pohlepni pristup od vrha prema dolje za izradu stabala odluka. Algoritam započinje s nizom podataka o obuci s oznakama klase koje su podijeljene u manje podskupove tijekom izrade stabla.
# 1) U početku postoje tri parametra tj. popis atributa, metoda odabira atributa i particija podataka . Popis atributa opisuje atribute korpica skupa treninga.
#dva) Metoda odabira atributa opisuje metodu za odabir najboljeg atributa za diskriminaciju između nabora. Metode koje se koriste za odabir atributa mogu biti Porast informacija ili Gini indeks.
# 3) O strukturi stabla (binarnom ili nebinarnom) odlučuje se metodom odabira atributa.
# 4) Prilikom izrade stabla odluke, ono započinje kao jedan čvor koji predstavlja korijene.
# 5) Ako korijeni korijenskog čvora predstavljaju različite oznake klasa, tada poziva metodu odabira atributa za dijeljenje ili particioniranje korpica. Korak će dovesti do stvaranja grana i čvorova odlučivanja.
# 6) Metoda razdvajanja odredit će koji atribut treba odabrati za particioniranje korpica podataka. Također određuje grane koje će se uzgajati iz čvora prema ishodu testa. Glavni motiv kriterija podjele je da particija na svakoj grani stabla odluke predstavlja istu oznaku klase.
Primjer atributa dijeljenja prikazan je u nastavku:
a. Gornji dio je diskretno vrijedan.
b. Gornji dio je za kontinuiranu vrijednost.
# 7) Gornji koraci particioniranja slijede se rekurzivno kako bi se oblikovalo stablo odluke za korpe skupa podataka o treningu.
# 8) Dijeljenje se zaustavlja samo kada su napravljene ili sve particije ili kada se preostale korpe ne mogu dalje particionirati.
# 9) Složenost algoritma opisuje n * | D | * zapisnik | D | gdje je n broj atributa u skupu podataka D i | D | je broj korijena.
Što je pohlepno rekurzivno binarno cijepanje?
U binarnoj metodi dijeljenja, nabori se dijele i izračunava se svaka funkcija troška podjele. Odabran je najniži trošak. Metoda cijepanja je binarna koja je oblikovana kao 2 grane. Rekurzivne je naravi jer se ista metoda (izračunavanje troškova) koristi za razdvajanje ostalih korpica skupa podataka.
Ovaj algoritam naziva se pohlepnim jer se fokusira samo na trenutni čvor. Fokusira se na smanjenje troškova, dok se ostali čvorovi ignoriraju.
Kako odabrati atribute za stvaranje stabla?
Mjere odabira atributa nazivaju se i pravilima razdvajanja kako bi se odlučilo kako će se korice podijeliti. Kriteriji podjele koriste se za najbolje dijeljenje skupa podataka. Ove mjere daju rang prema atributima za pregrađivanje treninga.
Najpopularnije metode odabira atributa su dobivanje informacija, Ginijev indeks.
# 1) Dobivanje informacija
Ova metoda je glavna metoda koja se koristi za izgradnju stabala odlučivanja. Smanjuje podatke potrebne za klasifikaciju korijena. Smanjuje broj testova potrebnih za klasifikaciju dane korpe. Odabran je atribut s najvećim prikupljanjem informacija.
Izvorne informacije potrebne za klasifikaciju nabora u skupu podataka D daju:
Gdje je p vjerojatnost da korijen pripada klasi C. Podaci se kodiraju u bitovima, pa se koristi zapis na bazu 2. E (s) predstavlja prosječnu količinu informacija potrebnu za otkrivanje oznake klase skupa podataka D. Također se naziva i dobivanje informacija Entropija .
Podaci potrebni za točnu klasifikaciju nakon porcioniranja daju se formulom:
Gdje je P (c) težina pregrade. Ove informacije predstavljaju informacije potrebne za klasifikaciju skupa podataka D na dijeljenje od strane X.
Dobivanje informacija je razlika između izvornih i očekivanih informacija koje su potrebne za klasifikaciju nizova skupa podataka D.
Dobitak je smanjenje podataka koje je potrebno poznavanjem vrijednosti X. Atribut s najvećim prirastom informacija odabran je kao 'najbolji'.
# 2) Omjer dobitka
Dobivanje informacija ponekad može rezultirati porcijama beskorisnim za klasifikaciju. Međutim, omjer dobitka dijeli skup podataka o treningu na particije i uzima u obzir broj korpica ishoda s obzirom na ukupne korpe. Atribut s omjerom maksimalnog dobitka koristi se kao atribut razdvajanja.
# 3) Gini indeks
Gini indeks izračunava se samo za binarne varijable. Mjeri nečistoće u vježbenim skupinama skupa podataka D, kao
koje vr slušalice rade s ps4
P je vjerojatnost da torta pripada klasi C. Ginijev indeks koji se izračunava za binarni podijeljeni skup podataka D atributom A daje:
Gdje je n n-ta particija skupa podataka D.
Smanjenje nečistoće daje se razlikom Ginijevog indeksa izvornog skupa podataka D i Ginijevog indeksa nakon podjele atributom A.
Maksimalno smanjenje nečistoće ili maksimalni Ginijev indeks odabrani su kao najbolji atribut za cijepanje.
Prekomjerno uklapanje u stabla odlučivanja
Prekomjerno prilagođavanje događa se kada stablo odluke pokušava biti što savršenije povećanjem dubine testova i na taj način smanjuje pogrešku. To rezultira vrlo složenim stablima i dovodi do prekomjerne opreme.
Prekomjerna opremljenost smanjuje prediktivnu prirodu stabla odlučivanja. Pristupi za izbjegavanje prekomjerne opremljenosti stabala uključuju predrezivanje i nakon obrezivanja.
Što je obrezivanje drveća?
Obrezivanje je metoda uklanjanja neiskorištenih grana sa stabla odlučivanja. Neke grane stabla odluke mogu predstavljati odstupanja ili bučne podatke.
Rezidba stabla je metoda za smanjenje neželjenih grana stabla. To će smanjiti složenost stabla i pomoći u učinkovitoj prediktivnoj analizi. Smanjuje prekomjernu opremu jer uklanja nevažne grane sa drveća.
Postoje dva načina obrezivanja stabla:
# 1) Priprema : U ovom pristupu, izgradnja stabla odluka zaustavlja se rano. To znači da je odlučeno da se grane ne dijele dalje. Posljednji izgrađeni čvor postaje lisni čvor i ovaj čvor može sadržavati najčešću klasu među korpama.
Mjere odabira atributa koriste se za utvrđivanje pondera razdvajanja. Vrijednosti praga propisane su kako bi se odlučilo koji se dijelovi smatraju korisnim. Ako dijeljenje čvora rezultira cijepanjem padom ispod praga, tada se postupak zaustavlja.
# 2) Postpruning : Ovom metodom uklanjaju se odvojene grane s potpuno uzgojenog stabla. Neželjene grane uklanjaju se i zamjenjuju lisnatim čvorom koji označava najčešće oznake klase. Ova tehnika zahtijeva više proračuna nego pripremanje, no pouzdanija je.
Orezana stabla preciznija su i kompaktnija u usporedbi s neobrezanim stablima, ali imaju nedostatak replikacije i ponavljanja.
Ponavljanje se događa kada se isti atribut uvijek iznova testira duž grane stabla. Replikacija događa se kada su duplicirani podstabla prisutni unutar stabla. Ta se pitanja mogu riješiti viševarijantnim podjelama.
Ispod je slika neobrezano i orezano stablo.
Primjer algoritma stabla odlučivanja
Primjer Izvor
Konstruiranje stabla odluke
Uzmimo primjer posljednjih 10 dana podataka o vremenskim prilikama s atributima izgled, temperatura, vjetar i vlaga. Varijabla ishoda igrat će kriket ili ne. Za izradu stabla odluke koristit ćemo se algoritmom ID3.
Dan | Outlook | Temperatura | Vlažnost | Vjetar | Igrajte kriket |
---|---|---|---|---|---|
7 | Oblačan | Super | Normalan | Jaka | Da |
1 | Sunčano | Vruće | Visoko | Slab | Nemoj |
dva | Sunčano | Vruće | Visoko | Jaka | Nemoj |
3 | Oblačan | Vruće | Visoko | Slab | Da |
4 | Kiša | Blaga | Visoko | Slab | Da |
5 | Kiša | Super | Normalan | Slab | Da |
6 | Kiša | Super | Normalan | Jaka | Nemoj |
8 | Sunčano | Blaga | Visoko | Slab | Nemoj |
9 | Sunčano | Super | Normalan | Slab | Da |
10 | Kiša | Blaga | Normalan | Slab | Da |
jedanaest | Sunčano | Blaga | Normalan | Jaka | Da |
12 | Oblačan | Blaga | Visoko | Jaka | Da |
13 | Oblačan | Vruće | Normalan | Slab | Da |
14 | Kiša | Blaga | Visoko | Jaka | Nemoj |
Korak 1: Prvi korak bit će stvaranje korijenskog čvora.
Korak 2: Ako su svi rezultati potvrdni, vratit će se čvor 'da', u suprotnom će se vratiti čvor 'ne'.
Korak 3: Otkrijte Entropiju svih opažanja i entropiju s atributom 'x' koji je E (S) i E (S, x).
Korak 4: Saznajte informacijsku dobit i odaberite atribut s visokom informacijskom dobiti.
Korak 5: Ponavljajte gornje korake sve dok nisu pokriveni svi atributi.
Proračun entropije:
da ne
9 5
Ako je entropija nula, to znači da svi članovi pripadaju istoj klasi, a ako je entropija jedna, to znači da polovica korpica pripada jednoj klasi, a jedan od njih pripada drugoj klasi. 0,94 znači poštena raspodjela.
Pronađite atribut dobivanja informacija koji daje maksimalan dobitak informacija.
Na primjer 'Vjetar', potrebne su dvije vrijednosti: Snažan i Slab, dakle, x = {Snažan, Slab}.
Doznajte H (x), P (x) za x = slab i x = jak. H (S) je već izračunat gore.
Slabo = 8
Jaka = 8
Za 'slab' vjetar, njih 6 kaže 'Da' za igranje kriketa, a njih 2 kažu 'Ne'. Dakle, entropija će biti:
Za 'jak' vjetar, 3 su rekla 'Ne' za igranje kriketa, a 3 su rekla 'Da'.
To pokazuje savršenu slučajnost jer polovica predmeta pripada jednoj klasi, a preostala polovica pripada drugima.
Izračunajte informacijsku dobit,
Slično dobivanju informacija za druge atribute je:
Izgled atributa ima najveći informacijski dobitak od 0,246, pa je odabran kao korijen.
Oblačno ima 3 vrijednosti: Sunčano, Oblačno i Kiša. Naoblačenje s kriketom za igru uvijek je 'Da'. Tako završava čvorom lista, 'da'. Za ostale vrijednosti 'Sunčano' i 'Kiša'.
Tabela za Outlook kao 'Sunčano' bit će:
Temperatura | Vlažnost | Vjetar | Golf |
---|---|---|---|
Vruće | Visoko | Slab | Nemoj |
Vruće | Visoko | Jaka | Nemoj |
Blaga | Visoko | Slab | Nemoj |
Super | Normalan | Slab | Da |
Blaga | Normalan | Jaka | Da |
Entropija za 'Outlook' 'Sunny' je:
Dobitak informacija za atribute u odnosu na Sunny je:
Dobitak informacija o vlažnosti zraka je najveći, stoga je odabran kao sljedeći čvor. Slično tome, entropija se izračunava za kišu. Vjetar daje najveći informativni dobitak .
Stablo odluke moglo bi izgledati dolje:
Što je prediktivno modeliranje?
Klasifikacijski modeli mogu se koristiti za predviđanje ishoda nepoznatog skupa atributa.
Kada se u model unese skup podataka s nepoznatim oznakama klase, tada će mu automatski dodijeliti oznaku klase. Ova metoda primjene vjerojatnosti za predviđanje ishoda naziva se prediktivno modeliranje.
Prednosti klasifikacije stabla odlučivanja
U nastavku su navedene razne zasluge klasifikacije stabla odlučivanja:
- Klasifikacija stabla odluka ne zahtijeva nikakvo znanje iz domene, stoga je prikladna za postupak otkrivanja znanja.
- Prikazivanje podataka u obliku stabla ljudima je lako razumljivo i intuitivno je.
- Može rukovati višedimenzionalnim podacima.
- To je brz postupak s velikom točnošću.
Nedostaci klasifikacije stabla odlučivanja
Dolje su dati različiti nedostaci klasifikacije stabla odlučivanja:
u unixu dopušta dozvola za pristup w (pisanje)
- Stabla odlučivanja ponekad postaju vrlo složena i ona se nazivaju prenamještenim stablima.
- Algoritam stabla odlučivanja možda nije optimalno rješenje.
- Stabla odluka mogu vratiti pristrano rješenje ako neka oznaka klase dominira njime.
Zaključak
Stabla odlučivanja su tehnike rudarenja podataka za klasifikaciju i regresijsku analizu.
Ova se tehnika danas prostire na mnogim područjima poput medicinske dijagnoze, ciljanog marketinga itd. Ova stabla izrađuju se slijedeći algoritam kao što je ID3, CART. Ti algoritmi pronalaze različite načine za razdvajanje podataka na particije.
To je najpoznatija nadzirana tehnika učenja koja se koristi u strojnom učenju i analizi uzoraka. Stabla odlučivanja predviđaju vrijednosti ciljne varijable gradeći modele učeći se iz seta obuke koji se pruža sustavu.
Nadamo se da ste iz ovog informativnog vodiča naučili sve o rudarstvu na stablu odluka !!
Preporučena literatura
- Primjeri rudarenja podataka: Najčešća primjena rudarenja podataka 2021
- Tehnike rudarstva podataka: algoritam, metode i najvažniji alati za miniranje podataka
- Rudarstvo podataka: proces, tehnike i glavni problemi u analizi podataka
- Struktura podataka stabla B i stabla B + u jeziku C ++
- Struktura podataka binarnog stabla u C ++
- Proces rudarenja podataka: uključeni modeli, koraci i izazovi
- Struktura podataka AVL stabla i hrpe u C ++
- Data Mining vs Machine Learning vs Artificial Intelligence vs Deep Learning