V tomto příspěvku podrobně rozumíme algoritmu ID3 rozhodovacích stromů s ukázkovou datovou sadou.
· Co je algoritmus ID3?
· Pseudokód algoritmu ID3
· Práce s numerickým příkladem
· Nevýhody algoritmu ID3
· Výhody algoritmu ID3
Co je algoritmus ID3?
Začněme s plnou formou ID3, je to zkratka pro „Iterativní dichotomizér 3“, kde dichotomizér znamená rozdělení na části. ID3 používá shora dolů chamtivý přístup k vytvoření rozhodovacího stromu. Jednoduše řečeno, shora dolů přístup znamená, že začínáme stavět strom shora a od chamtivý přístup znamená, že při každé iteraci vybereme v současnosti nejlepší vlastnost pro vytvoření uzlu.
Algoritmus ID3 začíná s původní množinou S jako kořenovým uzlem. Při každé iteraci algoritmu prochází každý nepoužitý atribut množiny S provedení:
· Vypočítejte entropii každého atributu A souboru dat S.· Rozdělte množinu S na podmnožiny pomocí atributu, u kterého je výsledná entropie po rozdělení minimalizována/ekvivalentně, informační zisk je maximální.
· Vytvořte uzel rozhodovacího stromu obsahující tento atribut.
· Proveďte totéž rekurzivně na podmnožinách pomocí zbývajících atributů.
ID3 (příklady, cílový_atribut, atributy)
Vytvořte kořenový uzel stromu
Pokud jsou všechny příklady kladné, vraťte kořen stromu s jedním uzlem s popiskem = +.
Pokud jsou všechny příklady záporné, vrátí kořen stromu s jedním uzlem s popiskem = -.
Pokud je počet prediktivních atributů prázdný, vraťte kořen stromu jednoho uzlu,
s popiskem = nejběžnější hodnota cílového atributu v příkladech.
Jinak Začněte
A ← Atribut, který nejlépe klasifikuje příklady.
Atribut stromu rozhodování pro kořen = A.
Pro každou možnou hodnotu vi z A,
Přidejte novou větev stromu pod kořen, odpovídající testu A = vi.
Nechť Příklady(vi) jsou podmnožinou příkladů, které mají hodnotu vi pro A
Pokud je Příklady(vi) prázdné
Poté pod tuto novou větev přidejte listový uzel s popiskem = nejběžnější cílová hodnota v příkladech
Jinak pod tuto novou větev přidejte podstrom ID3 (Examples(vi), Target_Attribute, Attributes — )Konec
Návrat kořene
Pojďme pochopit jeho práci na číselném příkladu:
Následující tabulka obsahuje faktory, jak hrát tenis venku v předchozích 14 dnech:
Vzorce použité v algoritmu ID3:
Poznámka: Používá se log based 2.
Entropie(S) = ∑ — p (I) . log(já)
Zisk(S, A) = Entropie(S) — ∑ [p(S|A) . Entropie (S|A)]
p označuje pravděpodobnost, A označuje atribut , S označuje entropii a I označuje informaci.
Nejprve musíme vypočítat entropii. Sloupec rozhodnutí se skládá ze 14 instancí a obsahuje dva štítky: ano a ne. Existuje 9 rozhodnutí označených ano a 5 rozhodnutí označených ne.
Entropie (rozhodnutí) = — p(Ano) . log(Ano) — p(Ne) . logp(Ne)
Entropie (Rozhodnutí) = — (9/14) . log(9/14) — (5/14) . log(5/14) = 0.940
Faktor větru při rozhodování
Zisk(rozhodnutí, vítr) = Entropie(rozhodnutí) — ∑ [ p(rozhodnutí|vítr) . Entropie(rozhodnutí|vítr) ]
Atribut větru má dvě označení: slabý a silný.
Zisk(rozhodnutí, vítr) = Entropie(rozhodnutí) — [ p(rozhodnutí|vítr=slabý) . Entropie(Rozhodnutí|Vítr=Slabý) ] — [ p(Rozhodnutí|Vítr=Silný) . Entropie(rozhodnutí|Vítr=Silný) ]
Nyní musíme vypočítat (Rozhodnutí|Vítr=Slabý) a (Rozhodnutí|Vítr=Silný).
Existuje 8 případů slabého větru. Ve kterém rozhodnutí 2 položek je ne a 6 položek ano, jak je znázorněno níže.
Entropie(Rozhodnutí|Vítr=Slabý) = -p(Ne) . logp(Ne) -p(Ano) . logp (Ano)
Entropie(Rozhodnutí|Vítr=Slabý) = -(2/8) . log(2/8) -(6/8) . log(6/8) = 0.811
Faktor silného větru:
Zde je 6 případů silného větru. Rozhodnutí je rozděleno na dvě stejné části.
Entropie(Rozhodnutí|Vítr=Silný) = — p(Ne) . logp(Ne) — p(Ano) . log2p (Ano)
Entropie(Rozhodnutí|Vítr=Silný) = — (3/6) . log(3/6) — (3/6) . log2(3/6) = 1
Nyní se můžeme vrátit zpět k rovnici Gain (rozhodnutí, vítr).
Zisk(rozhodnutí, vítr) = Entropie(rozhodnutí) — [ p(rozhodnutí|vítr=slabý) . Entropie(Rozhodnutí|Vítr=Slabý) ] — [ p(Rozhodnutí|Vítr=Silný) . Entropie(Rozhodnutí|Vítr=Silný) ] = 0.940 — [ (8/14) . 0.811 ] — [ (6/14). 1] = 0.048
Výpočty pro větrný sloupec skončily. Nyní musíme použít stejné výpočty pro další sloupce, abychom našli nejdominantnější faktor při rozhodování.
Podobně počítáme pro další atributy a jejich výsledky vypadají takto:
Zisk (rozhodnutí, výhled) = 0.246
Zisk (rozhodnutí, teplota) = 0.029
Zisk (rozhodnutí, vlhkost) = 0.151
z výše uvedených výsledků je vidět, že faktor výhledu na rozhodování vytváří nejvyšší skóre, takže to zakořeňte.
Rozhodnutí bude vždy ano, pokud by výhled byl zatažený. Zde je 5 příkladů slunečného výhledu. Rozhodnutí by bylo pravděpodobně 3/5 procenta ne, 2/5 procenta ano.
1- Zisk (výhled=slunečno|teplota) = 0.570
2- Zisk (Výhled=Slunečno|Vlhkost) = 0.970
3- Zisk (Výhled=Slunečno|Vítr) = 0.019
Nyní rozhoduje vlhkost, protože poskytuje nejvyšší skóre, pokud je výhled slunečný. Nyní bude rozhodnutí vždy žádné, pokud byla vlhkost vysoká.
Na druhou stranu, rozhodnutí bude vždy ano, pokud vlhkost byla normální. To znamená, že musíme zkontrolovat vlhkost a rozhodnout, zda byl výhled slunečný.
Podobně jako dále,
Zisk (Výhled=Déšť | Teplota) = 0.01997309402197489
Zisk (Výhled=Déšť | Vlhkost) = 0.01997309402197489
Zisk (Výhled=Déšť | Vítr) = 0.9709505944546686
Zde vítr produkuje nejvyšší skóre, pokud by výhled byl déšť. To je důvod, proč musíme zkontrolovat atribut větru na 2. úrovni, pokud by výhled byl déšť. Ukazuje se tedy, že rozhodnutí bude vždy ano, pokud bude vítr slabý a výhled déšť. Rozhodnutí bude vždy žádné, pokud byl silný vítr a výhled byl déšť.
Finální strom vypadá takto:
Výše uvedený číselný příklad vysvětluje, jak to funguje s matematikou.
Nyní některé temné stránky ID3:
· ID3 nezaručuje optimální řešení.
· ID3 se může přesadit na tréninkovou datovou sadu.
· ID3 je obtížnější použít na kontinuální datové sadě.
Výhody algoritmu ID3:
· Z trénovacích dat jsou vytvořena srozumitelná pravidla predikce.
· Postaví krátký strom v relativně krátkém čase.
· Potřebuje pouze otestovat dostatek atributů, dokud nebudou klasifikována všechna data.
· Nalezení listových uzlů umožňuje ořezat testovací data, čímž se sníží počet testů.
V tomto příspěvku jsme se dozvěděli, jak funguje algoritmus ID3, jaké jsou jeho numerické metriky a fungování, jeho nevýhody, výhody. V následujících příspěvcích sledujeme naši cestu učení a zkoumáme další algoritmy strojového učení.
Děkuji Šťastné učení.
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!
