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!
V oblasti strojového učení slouží rozhodovací stromy jako výkonné nástroje pro řešení klasifikačních a regresních problémů. Rozhodovací stromy jsou jednoduché, ale účinné modely, které napodobují způsob, jakým se lidé rozhodují tím, že rozdělují složité problémy na řadu menších, lépe zvládnutelných dílčích problémů. Jsou jako struktura stromu vzhůru nohama.
Jeden populární algoritmus používaný ke konstrukci rozhodovacích stromů je algoritmus ID3. V tomto článku se ponoříme do rozhodovacích stromů a prozkoumáme algoritmus ID3, vysvětlíme jeho vnitřní fungování a poskytneme intuitivní příklady pro snadné pochopení.
Co jsou rozhodovací stromy?
Rozhodovací strom je hierarchická struktura, která připomíná vývojový diagram, skládající se z uzlů a větví. Každý vnitřní uzel představuje rozhodnutí na základě funkce, zatímco každý listový uzel představuje označení třídy nebo číselnou hodnotu v případě regrese. Cesta od kořenového uzlu k listovému uzlu představuje rozhodovací proces.
Algoritmus ID3:
Algoritmus Iterative Dichotomiser 3 (ID3) je indukční algoritmus rozhodovacího stromu, který konstruuje rozhodovací stromy pomocí přístupu shora dolů. Hlavním cílem ID3 je najít v každém kroku ty nejinformativnější atributy, aby se vytvořily oddíly, které přinášejí nejvyšší informační zisk nebo snížení nečistot.
Pojďme si algoritmus ID3 rozdělit na proces krok za krokem:
Krok 1: Vezměte celou datovou sadu jako vstup.
Krok 2: Vypočítejte entropii cílové proměnné a také atributy prediktoru.
Entropie(D) = ∑ — p(I) . log2p(I)
- Entropie (D) představuje entropii datové sady D.
- p(I) is the proportion of instances in D that belong to class I.
- Symbol Σ označuje součet všech možných označení třídy.
The entropy value ranges from 0 to 1. A value of 0 indicates that the dataset is perfectly pure (all instances belong to the same class), while a value of 1 indicates maximum impurity (instances are evenly distributed across different classes).
Krok 3: Vyberte nejlepší atribut
- Vypočítejte zisk informací pro každý atribut v datové sadě.
- Atribut s nejvyšším informačním ziskem se stává kořenovým uzlem rozhodovacího stromu.
Krok 4: Opakujte stejný postup na každé větvi, dokud není dokončen koncový uzel (listový uzel) každé větve, jak je znázorněno na obrázku výše.
Podívejme se na jednoduchý příklad pro ilustraci algoritmu ID3. Představte si, že máme datovou sadu e-mailů označenou jako „spam“ nebo „není spam“ na základě určitých atributů. Atributy zahrnují „odesílatel“, „předmět“ a „obsahuje_klíčové slovo“.
Na základě algoritmu ID3 vypočítáme informační zisk pro každý atribut:
- Zisk informací pro „odesílatele“: 0.2
- Informační zisk pro „předmět“: 0.3
- Informační zisk pro „contains_keyword“: 0.8
Protože „contains_keyword“ má nejvyšší informační zisk, stává se kořenovým uzlem našeho rozhodovacího stromu. Vytváříme podřízené uzly pro jejich možné hodnoty: „ano“ a „ne“.
Pro větev „ano“ vypočítáme informační zisk pro zbývající atributy:
- Zisk informací pro „odesílatele“: 0.1
- Informační zisk pro „předmět“: 0.2
Jako atribut s nejvyšším informačním ziskem vybereme „předmět“ a pro jeho možné hodnoty vytvoříme podřízené uzly.
Tento proces opakujeme, dokud nezůstanou čisté podmnožiny nebo žádné atributy, které bychom měli vzít v úvahu. Výsledný rozhodovací strom by poskytoval jasnou cestu pro klasifikaci e-mailů jako spam nebo nikoli na základě poskytnutých atributů.
Závěr:
Rozhodovací stromy, konstruované pomocí algoritmu ID3, nabízejí interpretovatelný a intuitivní přístup k řešení klasifikačních problémů. Tato stromová struktura neustále roste a vyvíjí se, protože algoritmus ID3 rekurzivně vybírá nejinformativnější atributy a podle toho vytváří větve. Rozdělením složitých rozhodovacích procesů do jednodušších kroků poskytují rozhodovací stromy transparentní a srozumitelný rámec pro rozhodování a vytváření dobrých modelů.
