Príklady algoritmu rozhodovacieho stromu v dolovaní dát

decision tree algorithm examples data mining

Tento podrobný výukový program vysvetľuje všetko o algoritme rozhodovacieho stromu pri dolovaní údajov. Dozviete sa príklady rozhodovacieho stromu, algoritmus a klasifikáciu:

Boli sme sa pozrieť na pár Príklady ťažby dát v našom predchádzajúcom návode v Séria školení na ťažbu dát zdarma .

Ťažba rozhodovacích stromov je typ techniky ťažby dát, ktorá sa používa na zostavenie klasifikačných modelov. Vytvára klasifikačné modely vo forme stromovej štruktúry, rovnako ako jej názov. Tento typ ťažby patrí k triednemu učeniu pod dohľadom.

Pri výučbe s dohľadom je cieľový výsledok už známy. Rozhodovacie stromy možno použiť pre kategorické aj číselné údaje. Kategorické údaje predstavujú pohlavie, rodinný stav atď., Zatiaľ čo číselné údaje predstavujú vek, teplotu atď.

implementácia hashovacieho programu v c ++

Nižšie je uvedený príklad rozhodovacieho stromu s množinou údajov.

[obrázok zdroj ]

Čo sa dozviete:

• Aké je použitie rozhodovacieho stromu?
• Klasifikačná analýza
• Regresná analýza
• Ako funguje rozhodovací strom?
• Algoritmus indukčného stromu rozhodnutia
• Indukcia rozhodovacieho stromu
• KOŠÍK
• Indukcia rozhodovacieho stromu pre strojové učenie: ID3
• Čo je chamtivé rekurzívne binárne rozdelenie?
• Ako zvoliť atribúty pre vytvorenie stromu?
  • # 1) Zisk informácií
  • # 2) Ziskový pomer
  • # 3) Giniho index
• Preťaženie rozhodovacích stromov
• Čo je to prerezávanie stromov?
• Čo je prediktívne modelovanie?
• Výhody klasifikácie rozhodovacích stromov
• Nevýhody klasifikácie rozhodovacích stromov
• Záver
• Odporúčané čítanie

Aké je použitie rozhodovacieho stromu?

Rozhodovací strom sa používa na zostavenie klasifikačných a regresných modelov. Používa sa na vytvorenie dátových modelov, ktoré budú predpovedať štítky alebo hodnoty tried pre proces rozhodovania. Modely sú zostavené z tréningových dátových súborov dodávaných do systému (dohľad nad učením).

Pomocou rozhodovacieho stromu môžeme vizualizovať rozhodnutia, ktoré uľahčujú pochopenie, a preto ide o populárnu techniku ​​ťažby údajov.

Klasifikačná analýza

Klasifikácia údajov je forma analýzy, ktorá vytvára model, ktorý popisuje dôležité premenné triedy.Napríklad, model zostavený tak, aby kategorizoval žiadosti o bankové pôžičky ako bezpečné alebo rizikové. Pri strojovom učení a rozpoznávaní vzorov sa používajú klasifikačné metódy.

Aplikácia klasifikácie zahŕňa detekciu podvodov, lekársku diagnózu, cieľový marketing atď. Výsledok problému s klasifikáciou sa považuje za „režim“ všetkých pozorovaných hodnôt koncového uzla.

Nasleduje dvojkrokový proces, ktorým je vytvorenie klasifikačného modelu.

1. V prvom kroku, tj. Učenie: Je zostavený klasifikačný model založený na údajoch o tréningu.
2. V druhom kroku, tj. Klasifikácii, sa skontroluje presnosť modelu a potom sa model použije na klasifikáciu nových údajov. Tu uvedené označenia tried majú formu samostatných hodnôt, ako napríklad „áno“ alebo „nie“, „bezpečné“ alebo „riskantné“.

Všeobecný prístup k modelom klasifikácie budov je uvedený nižšie:

[obrázok zdroj ]

Regresná analýza

Na predikciu číselných atribútov sa používa regresná analýza.

Číselné atribúty sa tiež nazývajú spojité hodnoty. Model zostavený na predpovedanie spojitých hodnôt namiesto štítkov tried sa nazýva regresný model. Výstupom regresnej analýzy je „priemer“ zo všetkých pozorovaných hodnôt uzla.

Ako funguje rozhodovací strom?

Rozhodovací strom je supervizovaný učebný algoritmus, ktorý pracuje pre diskrétne aj spojité premenné. Rozdeľuje množinu údajov na podskupiny na základe najvýznamnejšieho atribútu v množine údajov. O tom, ako rozhodovací strom identifikuje tento atribút a ako sa vykonáva toto rozdelenie, rozhodujú algoritmy.

Najvýznamnejší prediktor je označený ako koreňový uzol. Štiepením sa vytvárajú subuzly nazývané rozhodovacie uzly a uzly, ktoré sa ďalej nerozdeľujú, sú terminálne alebo listové uzly.

V rozhodovacom strome je množina údajov rozdelená na homogénne a neprekrývajúce sa oblasti. Sleduje prístup zhora nadol, pretože horná oblasť predstavuje všetky pozorovania na jednom mieste, ktoré sa rozdeľuje na dve alebo viac vetiev, ktoré sa ďalej rozdeľujú. Tento prístup sa tiež nazýva a chamtivý prístup pretože berie do úvahy iba súčasný uzol medzi prácou bez zamerania na budúce uzly.

Algoritmy rozhodovacieho stromu budú pokračovať v činnosti až do dosiahnutia kritérií zastavenia, ako je minimálny počet pozorovaní atď.

Po vytvorení rozhodovacieho stromu môže veľa uzlov predstavovať odľahlé hodnoty alebo hlučné údaje. Na odstránenie nežiaducich údajov sa používa metóda orezávania stromov. To zase zvyšuje presnosť klasifikačného modelu.

Na zistenie presnosti modelu sa používa testovacia sada pozostávajúca z testovacích n-tíc a štítkov tried. Percentuálne podiely n-tíc testovacej sady sú podľa modelu správne klasifikované, aby sa zistila presnosť modelu. Ak sa zistí, že model je presný, potom sa použije na klasifikáciu n-tíc údajov, pre ktoré nie sú známe označenia tried.

Niektoré z algoritmov rozhodovacieho stromu zahŕňajú Hunt’s Algorithm, ID3, CD4.5 a CART.

Príklad vytvorenia rozhodovacieho stromu

(Príklad je prevzatý z konceptov ťažby dát: Han a Kimber)

# 1) Krok učenia: Výcvikové dáta sa vložia do systému, ktorý sa má analyzovať klasifikačným algoritmom. V tomto príklade je štítkom triedy atribút, tj „rozhodnutie o pôžičke“. Model zostavený z týchto tréningových údajov je predstavovaný vo forme rozhodovacích pravidiel.

# 2) Klasifikácia: Testovací súbor údajov sa zavedie do modelu s cieľom skontrolovať presnosť pravidla klasifikácie. Ak model poskytuje prijateľné výsledky, použije sa na nový súbor údajov s neznámymi premennými triedy.

Algoritmus indukčného stromu rozhodnutia

Indukcia rozhodovacieho stromu

Indukcia rozhodovacieho stromu je metóda učenia rozhodovacích stromov z tréningovej sady. Výcviková sada sa skladá z atribútov a štítkov tried. Aplikácie indukcie rozhodovacích stromov zahŕňajú astronómiu, finančné analýzy, lekársku diagnostiku, výrobu a výrobu.

Rozhodovací strom je štruktúra podobná vývojovému diagramu, ktorá sa vyrába z tréningových n-tíc. Súbor údajov je rozdelený na menšie podmnožiny a je prítomný vo forme uzlov stromu. Stromová štruktúra má koreňový uzol, vnútorné uzly alebo rozhodovacie uzly, listový uzol a vetvy.

Koreňový uzol je najvrchnejší uzol. Predstavuje najlepší atribút vybraný pre klasifikáciu. Interné uzly rozhodovacích uzlov predstavujú test atribútu uzla listu množiny údajov alebo koncového uzla, ktorý predstavuje označenie klasifikácie alebo rozhodnutia. Vetvy ukazujú výsledok vykonaného testu.

Niektoré rozhodovacie stromy iba majú binárne uzly , To znamená presne dve vetvy uzla, zatiaľ čo niektoré rozhodovacie stromy sú nebinárne.

Obrázok nižšie zobrazuje rozhodovací strom pre dátovú sadu Titanic, ktorý predpovedá, či cestujúci prežije alebo nie.

[obrázok zdroj ]

KOŠÍK

Model CART, tj. Klasifikačné a regresné modely, je algoritmus rozhodovacieho stromu pre vytváranie modelov. Model rozhodovacieho stromu, kde majú cieľové hodnoty diskrétny charakter, sa nazýva klasifikačné modely.

Diskrétna hodnota je konečná alebo spočítateľne nekonečná množina hodnôt, Napríklad, vek, veľkosť atď. Modely, kde sú cieľové hodnoty reprezentované súvislými hodnotami, sú zvyčajne čísla, ktoré sa nazývajú regresné modely. Spojité premenné sú premenné s pohyblivou rádovou čiarkou. Tieto dva modely sa spolu nazývajú KOŠÍK.

CART používa Gini Index ako klasifikačnú maticu.

Indukcia rozhodovacieho stromu pre strojové učenie: ID3

Na konci 70. a začiatkom 80. rokov bol J.Ross Quinlan výskumníkom, ktorý vytvoril algoritmus rozhodovacieho stromu pre strojové učenie. Tento algoritmus je známy ako ID3, Iteratívny dichotomizér . Tento algoritmus bol rozšírením koncepčných systémov učenia opísaných E. B. Huntom, J. a Marinom.

ID3 bol neskôr známy ako C4.5. ID3 a C4.5 sa pri zostavovaní rozhodovacích stromov riadia chamtivým prístupom zhora nadol. Algoritmus začína tréningovým údajovým súborom s menovkami tried, ktoré sú pri zostavovaní stromu rozdelené na menšie podmnožiny.

# 1) Spočiatku existujú tri parametre, t.j. zoznam atribútov, metóda výberu atribútov a dátová oblasť . Zoznam atribútov popisuje atribúty n-tic tréningovej sady.

#dva) Metóda výberu atribútov popisuje metódu výberu najlepšieho atribútu na rozlišovanie medzi n-ticami. Metódy používané na výber atribútov môžu byť buď Information Gain alebo Gini Index.

# 3) O štruktúre stromu (binárneho alebo nebinárneho) rozhoduje metóda výberu atribútov.

# 4) Pri konštrukcii rozhodovacieho stromu sa začína ako jeden uzol predstavujúci n-tice.

# 5) Ak n-tice v koreňovom uzle predstavujú štítky rôznych tried, potom zavolá metódu výberu atribútov na rozdelenie alebo rozdelenie n-tíc. Tento krok povedie k vytvoreniu pobočiek a rozhodovacích uzlov.

# 6) Metóda rozdelenia určí, ktorý atribút by sa mal zvoliť na rozdelenie n-tíc údajov. Podľa výsledku testu tiež určuje vetvy, ktoré sa majú z uzla vypestovať. Hlavným motívom kritérií rozdelenia je, že oddiel v každej vetve rozhodovacieho stromu by mal predstavovať rovnaký štítok triedy.

Príklad atribútu rozdelenia je uvedený nižšie:

a. Vyššie uvedené porcie majú diskrétnu hodnotu.

b. Vyššie uvedené porcie slúžia na priebežné oceňovanie.

# 7) Vyššie uvedené kroky rozdelenia sa postupujú rekurzívne, aby sa vytvoril rozhodovací strom pre n-tice výcvikových súborov údajov.

# 8) Porciovanie sa zastaví, iba ak sú vytvorené všetky oddiely alebo ak zostávajúce n-tice nie je možné ďalej rozdeliť.

# 9) Zložitosť algoritmu popisuje n * | D | * denník | D | kde n je počet atribútov v množine výcvikových údajov D a | D | je počet n-tíc.

Čo je chamtivé rekurzívne binárne rozdelenie?

Pri metóde binárneho rozdelenia sa n-tice rozdelia a vypočíta sa každá funkcia rozdelenia nákladov. Je vybraté najnižšie rozdelenie nákladov. Metóda rozdelenia je binárna, ktorá je vytvorená ako 2 vetvy. Má rekurzívnu povahu, pretože rovnaká metóda (výpočet nákladov) sa používa na rozdelenie ostatných n-tíc množiny údajov.

Tento algoritmus sa nazýva chamtivý, pretože sa zameriava iba na aktuálny uzol. Zameriava sa na zníženie jeho nákladov, zatiaľ čo ostatné uzly sú ignorované.

Ako zvoliť atribúty pre vytvorenie stromu?

Opatrenia na výber atribútov sa tiež nazývajú pravidlá rozdelenia, aby sa rozhodlo, ako sa budú n-tice rozdeliť. Kritériá rozdelenia sa používajú na najlepšie rozdelenie množiny údajov. Tieto opatrenia poskytujú poradie atribútov na rozdelenie tréningových n-tíc.

Najobľúbenejšími metódami výberu atribútu sú zisk informácií, Giniho index.

# 1) Zisk informácií

Táto metóda je hlavnou metódou, ktorá sa používa na vytváranie rozhodovacích stromov. Znižuje to informácie potrebné na klasifikáciu n-tic. Znižuje počet testov, ktoré sú potrebné na klasifikáciu danej n-tice. Vyberie sa atribút s najvyšším ziskom informácií.

Pôvodné informácie potrebné na klasifikáciu n-tice v množine údajov D sú dané:

Kde p je pravdepodobnosť, že n-tica patrí do triedy C. Informácie sú kódované v bitoch, preto sa použije log do základne 2. E (s) predstavuje priemerné množstvo informácií potrebných na zistenie štítku triedy dátového súboru D. Tento zisk informácií sa tiež nazýva Entropia .

Informácie potrebné na presnú klasifikáciu po porcii sú dané vzorcom:

Kde P (c) je hmotnosť oddielu. Táto informácia predstavuje informácie potrebné na klasifikáciu množiny údajov D pri rozdelení na X.

Zisk informácií je rozdiel medzi pôvodnou a očakávanou informáciou, ktorá sa vyžaduje na klasifikáciu n-tice množiny údajov D.

Zisk je redukcia informácií, ktorá sa vyžaduje pri znalosti hodnoty X. Atribút s najvyšším ziskom informácií je vybraný ako „najlepší“.

# 2) Ziskový pomer

Získanie informácií môže niekedy viesť k rozdeleniu zbytočných údajov pre klasifikáciu. Pomer zosilnenia však rozdeľuje súbor tréningových údajov na oddiely a zohľadňuje počet n-tíc výsledku vzhľadom na celkové n-tice. Atribút s pomerom maximálneho zisku sa používa ako atribút rozdelenia.

# 3) Giniho index

Gini index sa počíta iba pre binárne premenné. Meria nečistotu v tréningových n-ticiach datasetu D, as

P je pravdepodobnosť, že n-tica patrí do triedy C. Giniho index, ktorý sa počíta pre binárne rozdelené množiny údajov D atribútom A, je daný:

Kde n je n-tý oddiel množiny údajov D.

Zníženie nečistoty je dané rozdielom Giniho indexu pôvodného súboru údajov D a Giniho indexu po rozdelení podľa atribútu A.

Ako najlepší atribút pre rozdelenie je zvolené maximálne zníženie nečistoty alebo maximálny Gini index.

Preťaženie rozhodovacích stromov

K preplneniu dôjde, keď sa rozhodovací strom snaží byť čo najdokonalejší zväčšením hĺbky testov, a tým znižuje chybu. Výsledkom sú veľmi zložité stromy a nadmerná výbava.

Nadmerné vybavenie redukuje prediktívnu povahu rozhodovacieho stromu. Prístupy, ako sa vyhnúť nadmernému vybaveniu stromov, zahŕňajú predrez a porez.

Čo je to prerezávanie stromov?

Prerezávanie je metóda odstraňovania nepoužívaných konárov z rozhodovacieho stromu. Niektoré vetvy rozhodovacieho stromu môžu predstavovať odľahlé hodnoty alebo hlučné údaje.

Orez stromu je metóda na zníženie nežiaducich konárov stromu. To zníži zložitosť stromu a pomôže pri efektívnej prediktívnej analýze. Znižuje to nadmerné vybavenie, pretože odstraňuje nedôležité konáre zo stromov.

Existujú dva spôsoby orezania stromu:

# 1) Predbežná príprava : V tomto prístupe je výstavba rozhodovacieho stromu zastavená skôr. Znamená to, že je rozhodnuté vetvy ďalej nerozdeľovať. Posledný zostrojený uzol sa stane listovým uzlom a tento listový uzol môže mať najbežnejšiu triedu medzi n-ticami.

Otázky a odpovede na pohovor s vývojárom salesforce

Miery na výber atribútov sa používajú na zistenie váhy rozdelenia. Na určenie, ktoré rozdelenia sa považujú za užitočné, sú predpísané prahové hodnoty. Ak má rozdelenie uzla za následok rozdelenie poklesom pod prahovú hodnotu, proces sa zastaví.

# 2) Postpruning : Táto metóda odstráni krajné konáre z úplne dospelého stromu. Nežiaduce vetvy sú odstránené a nahradené listovým uzlom označujúcim najbežnejší štítok triedy. Táto technika vyžaduje viac výpočtov ako predbežná príprava, je však spoľahlivejšia.

Orezané stromy sú presnejšie a kompaktnejšie v porovnaní s neorezanými stromami, ale majú nevýhodu v replikácii a opakovaní.

Opakovanie sa vyskytuje, keď sa rovnaký atribút testuje znova a znova pozdĺž vetvy stromu. Replikácia nastane, keď sú v strome duplicitné podstromy. Tieto problémy je možné vyriešiť viacrozmernými rozdeleniami.

Obrázok nižšie zobrazuje nestrihaný a orezaný strom.

Príklad algoritmu rozhodovacieho stromu

Príklad Zdroj

Vytvorenie rozhodovacieho stromu

Zoberme si príklad súboru údajov o počasí za posledných 10 dní s atribútmi výhľad, teplota, vietor a vlhkosť. Výsledná premenná bude hrať kriket alebo nie. Na zostavenie rozhodovacieho stromu použijeme algoritmus ID3.

Krok 1: Prvým krokom bude vytvorenie koreňového uzla.

Krok 2: Ak sú všetky výsledky áno, potom sa vráti listový uzol „áno“, inak sa vráti listový uzol „nie“.

Krok 3: Zistite entropiu všetkých pozorovaní a entropiu pomocou atribútu „x“, ktorý je E (S) a E (S, x).

java 8 nových funkcií s príkladmi

Krok 4: Zistite informačný zisk a vyberte atribút s vysokým informačným ziskom.

Krok 5: Vyššie uvedené kroky opakujte, kým nebudú pokryté všetky atribúty.

Výpočet entropie:

Áno nie

9 5

Ak je entropia nula, znamená to, že všetci členovia patria do rovnakej triedy, a ak je entropia jedna, znamená to, že polovica n-tíc patrí do jednej triedy a jedna z nich patrí do inej triedy. 0,94 znamená spravodlivé rozdelenie.

Nájdite atribút prírastku informácie, ktorý poskytuje maximálny prírastok informácie.

Napríklad „Vietor“ má dve hodnoty: Silný a Slabý, preto x = {Silný, Slabý}.

Zistite H (x), P (x) pre x = slabé a x = silné. H (S) sa už počíta vyššie.

Slabé = 8

Silný = 8

Pre „slabý“ vietor, 6 z nich hovorí „Áno“, aby hralo kriket, a 2 z nich „Nie“. Takže entropia bude:

Pre „silný“ vietor 3 odpovedalo „Nie“ na hranie kriketu a 3 „Áno“.

To ukazuje dokonalú náhodnosť, pretože polovica položiek patrí do jednej triedy a zvyšná polovica patrí iným.

Vypočítajte informačný zisk,

Podobne je možné získať informácie pre ďalšie atribúty:

Atribút výhľad má najvyšší informačný zisk 0,246, teda je vybraný ako root.

Zamračené má 3 hodnoty: slnečno, zamračené a dážď. Zatiahnuté hraním kriketu je vždy „Áno“. Takže to končí listovým uzlom, „áno“. Pre ostatné hodnoty „slnečno“ a „dážď“.

Tabuľka pre Outlook ako „Sunny“ bude:

Entropia pre „Outlook“ „Sunny“ je:

Zisk informácií pre atribúty týkajúce sa spoločnosti Sunny je:

Zisk informácií pre vlhkosť je najvyšší, preto sa vyberie ako ďalší uzol. Podobne sa entropia počíta pre dážď. Vietor poskytuje najvyšší informačný zisk .

Rozhodovací strom bude vyzerať takto:

Čo je prediktívne modelovanie?

Klasifikačné modely možno použiť na predikciu výsledkov neznámej množiny atribútov.

Keď sa do modelu zavedie množina údajov s neznámymi menovkami tried, automaticky jej priradí menovku triedy. Táto metóda aplikácie pravdepodobnosti na predpovedanie výsledkov sa nazýva prediktívne modelovanie.

Výhody klasifikácie rozhodovacích stromov

Nižšie sú uvedené rôzne výhody klasifikácie rozhodovacích stromov:

1. Klasifikácia rozhodovacieho stromu nevyžaduje žiadne znalosti domény, a preto je vhodná pre proces zisťovania znalostí.
2. Zastúpenie údajov vo forme stromu je ľuďom ľahko pochopiteľné a je intuitívne.
3. Môže spracovávať viacrozmerné údaje.
4. Je to rýchly proces s veľkou presnosťou.

Nevýhody klasifikácie rozhodovacích stromov

Ďalej sú uvedené rôzne nevýhody klasifikácie rozhodovacích stromov:

1. Niekedy sa rozhodovacie stromy stávajú veľmi zložitými a hovorí sa im preplnené stromy.
2. Algoritmus rozhodovacieho stromu nemusí byť optimálnym riešením.
3. Rozhodovacie stromy môžu vrátiť zaujaté riešenie, ak mu dominuje nejaký štítok triedy.

Záver

Rozhodovacie stromy sú techniky získavania údajov na účely klasifikácie a regresnej analýzy.

Táto technika sa dnes rozprestiera v mnohých oblastiach, ako je lekárska diagnostika, cieľový marketing atď. Tieto stromy sú zostavené podľa algoritmu ako ID3, CART. Tieto algoritmy nachádzajú rôzne spôsoby rozdelenia údajov na oddiely.

Je to najznámejšia technika učenia pod dohľadom, ktorá sa používa pri strojovom učení a analýze vzorov. Rozhodovacie stromy predpovedajú hodnoty cieľovej premennej vytváraním modelov učením sa z tréningovej sady poskytnutej systému.

Dúfame, že ste sa z tohto informačného tutoriálu dozvedeli všetko o ťažbe rozhodovacích stromov !!

Výukový program PREV | NEXT Tutorial

Odporúčané čítanie

• Príklady dolovania dát: Najčastejšie aplikácie dolovania dát 2021
• Techniky dolovania dát: Algoritmus, metódy a najlepšie nástroje na dolovanie dát
• Ťažba dát: Proces, techniky a hlavné problémy v analýze dát
• Dátová štruktúra stromu B a stromu B + v C ++
• Štruktúra dát binárneho stromu v C ++
• Proces ťažby dát: zúčastnené modely, kroky procesu a výzvy
• Dátová štruktúra stromu a haldy AVL v C ++
• Data Mining vs. Machine Learning vs. Artificial Intelligence vs. Deep Learning