V tomto blogu podrobně rozumíme algoritmu Decision Tree ID3 s ukázkovou datovou sadou.
Rozhodovací strom je kontrolovaný algoritmus strojového učení používaný pro regresi i klasifikaci problému. Používá stromovou reprezentaci k řešení problému, ve kterém každý uzel představuje atribut, každý odkaz představuje rozhodovací pravidlo a každý list představuje výsledek (kategorická nebo spojitá hodnota).
Kořenový uzel— Je to nejvyšší uzel ve stromu, který představuje kompletní datovou sadu. Můžeme také říci, že je výchozím bodem rozhodovacího procesu.
Rozhodnutí/Interní uzel- Rozhodovací uzly nejsou ničím jiným než výsledkem rozdělení dat do více datových segmentů a hlavním cílem je mít podřízené uzly s maximální homogenitou nebo čistotou (znamená všechny stejného druhu).
Listový/koncový uzel— Tento uzel představuje datovou sekci s nejvyšší homogenitou (znamená všechny stejného druhu).
Entropie– Používá se pro kontrolu nečistot nebo nejistot přítomných v datech. Entropie se používá k hodnocení kvality splitu. Když je entropie nulová, vzorek je zcela homogenní, což znamená, že každá instance patří do stejné třídy a entropie je jedna, když je vzorek rovnoměrně rozdělen mezi různé třídy.
Informační zisk— Informační zisk udává, kolik informací nám konkrétní rys/proměnná poskytuje o konečném výsledku.
Vzorec získávání informací –
(Jedná se o nejoblíbenější algoritmy používané ke konstrukci stromů.)
ID3 je zkratka pro Iterative Dichotomizer3 a je pojmenován tak, protože algoritmus iterativně (opakovaně) dichotomizuje (rozděluje) prvky do dvou nebo více skupin v každém kroku. ID3 je algoritmus vynalezený Rossem Quinlanem, který se používá ke generování rozhodovacího stromu z datové sady nejoblíbenější algoritmy používané ke konstrukci stromů.
ID3 je základním algoritmem pro vytváření rozhodovacího stromu. Využívá chamtivé vyhledávání shora dolů v prostoru všech možných větví bez zpětného sledování. Tento algoritmus využívá informační zisk a entropii ke konstrukci klasifikačního rozhodovacího stromu.
Hlavní charakteristiky algoritmu ID3 jsou uvedeny níže:
- ID3 může překrýt trénovací data (abyste se vyhnuli přeplnění, měly by být upřednostňovány menší rozhodovací stromy před většími).
- Tento algoritmus obvykle vytváří malé stromy, ale ne vždy vytváří nejmenší možný strom.
- ID3 se hůře používá na spojitá data (pokud jsou hodnoty kteréhokoli daného atributu spojité, pak existuje mnohem více míst pro rozdělení dat tohoto atributu a hledání nejlepší hodnoty pro rozdělení může být časově náročné).
Výhody
- Nenákladné na stavbu
- Extrémně rychlý při klasifikaci neznámých záznamů Snadno interpretovatelné pro malé stromy.
- Odolné vůči hluku (zejména při použití metod, jak se vyhnout nadměrné montáži).
- Dokáže snadno zpracovat nadbytečné nebo irelevantní atributy (pokud se atributy vzájemně neovlivňují).
Nevýhody
- Prostor možných rozhodovacích stromů je exponenciálně velký. Chamtivé přístupy často nedokážou najít ten nejlepší strom.
- Nebere v úvahu interakce mezi atributy.
- Každá rozhodovací hranice zahrnuje pouze jeden atribut.
Kroky k vytvoření rozhodovacího stromu
a) Vezměte celou datovou sadu jako vstup.
b) Vypočítejte entropii cílové proměnné a také atributy prediktoru
c) Vypočítejte informační zisk všech atributů.
d) Jako kořenový uzel vyberte atribut s nejvyšším informačním ziskem
e) Opakujte stejný postup na každé větvi, dokud není dokončen rozhodovací uzel každé větve.
Předpokládejte, zda se zápas bude hrát nebo ne podle počasí. Zde vidíme tabulku –
Nejprve spočítáme entropii pro atribut „Decision“, což je cílová proměnná, a také vypočítáme entropii pro nezávislé atributy jako „Výhled“, „Temp“. , “Vlhkost”, “Vítr” .
Opakujte stejný postup na každé větvi, dokud není dokončen rozhodovací uzel každé větve.
Outlook=slunečno a teplota=teplo.
Výhled=slunečno a teplota=mírné
Outlook=slunečno a teplota=chladno
Zde bude rozhodnutí vždy ano, pokud by výhled byl zatažený. Není tedy třeba počítat entropii a informační zisk.
Zde můžeme vidět, že informační zisk je vysoký pro (Outlook=Rain | Wind), takže to bude rozhodovací uzel po Rain.
Konstrukce stromu rozhodování je u konce. Zde jsme se dozvěděli, jak je pomocí tohoto algoritmu vytvořen rozhodovací strom v backendu.
Podrobně jsme se zabývali procesem algoritmu ID3 a viděli jsme, jak snadné bylo vytvořit rozhodovací strom pomocí tohoto algoritmu s použitím pouze dvou metrik, tj. Entropie a Informačního zisku.
Doufám, že se vám to líbilo, chlapi!
