Algoritmus Decision Tree patří do rodiny algoritmů řízeného učení. Na rozdíl od jiných řízených výukových algoritmů lze algoritmus rozhodovacího stromu použít pro řešení regresních a klasifikačních problémů.
Zavedení terminologie:
Nebudu zacházet do všech detailů terminologie za předpokladu, že v tuto chvíli víte, místo sdílení obrázku pro odkazy níže
Jak funguje rozhodovací strom:
Rozhodovací stromy používají více algoritmů k rozhodnutí rozdělit uzel na dva nebo více poduzlů. Vytváření dílčích uzlů zvyšuje homogenitu výsledných dílčích uzlů. Jinými slovy, můžeme říci, že čistota uzlu roste vzhledem k cílové proměnné. Rozhodovací strom rozdělí uzly na všech dostupných proměnných a poté vybere rozdělení, jehož výsledkem jsou nejvíce homogenní poduzly.
Výběr algoritmu je také založen na typu cílových proměnných. Podívejme se na některé algoritmy používané v rozhodovacích stromech:
ID3 → (prodloužení D3)
C4.5 → (nástupce ID3)
VOZÍK → (Klasifikační a regresní strom)
CHAID → (Automatická detekce interakce chí-kvadrát Provádí víceúrovňové rozdělení při výpočtu klasifikačních stromů)
MARS → (multivariantní adaptivní regresní splajny)
Zde vidíme pouze algoritmus ID3:
Intuice algoritmů ID3:
Algoritmus ID3 staví rozhodovací stromy pomocí přístupu hrabivého vyhledávání shora dolů v prostoru možných větví bez zpětného sledování. Chamtivý algoritmus, jak název napovídá, vždy provede volbu, která se v danou chvíli zdá být nejlepší.
Kroky algoritmů ID3:
1. Vyberte Root node(S) na základě nízké entropie a nejvyššího informačního zisku
2. Při každé iteraci algoritmu vypočítá zisk entropie a informace, přičemž vezme v úvahu, že každý uzel je nevyužitý.
3. Vyberte základnu uzlů na nejnižší entropii nebo nejvyšší i.g
4. poté rozdělí sadu S a vytvoří podmnožiny dat
5. Nepřetržité algoritmy, které se budou opakovat u každé podmnožiny a zajistí, že atributy jsou čerstvé a vytvoří rozhodovací strom
Než půjdete hlouběji do algoritmů, pochopte některé statistické termíny, které to zahrnuje:
1. Entropie:
Rozhodovací strom je sestaven shora dolů z kořenového uzlu a zahrnuje rozdělení dat do podmnožin, které obsahují instance s podobnými hodnotami (homogenní). Algoritmus ID3 používá k výpočtu homogenity vzorku entropii. pokud Entropie E(s) = 0 znamená, že je zcela homogenní nebo můžeme říci, že je to Listový uzel stromu, takže jej nelze dále dělit a ID3 používá k rozdělení algoritmu nejnižší entropii.
Vzorec:
Zde p = pravděpodobnost
Zmiňuji nějaký užitečný vztah mezi pravděpodobností a entropií (zvažte binární klasifikaci):
1. Pravděpodobnost (obě třídy) = 0.5 a entropie = 1
2. Pravděpodobnost (buď nebo obě třídy) = 0 & entropie = 0 nazývá se listový uzel a zastavení rozdělení
- Nad relací vidíme, že pokud P = 0.5 na ose x, pak se entropie stane 1, určíme, že jako vysokou pravděpodobnost, tj.> 0.5, jeho entropie začala klesající a také jsme dostali listový uzel entropií = 0
2. Zisk informací:
Informační zisk je založen na poklesu entropie po rozdělení souboru dat na atribut. Konstrukce rozhodovacího stromu je o nalezení atributu, který vrátí nejvyšší informační zisk (tj. nejvíce homogenní větve)
3. Vážený zisk entropie:
Výše je vážený průměr pro všechny uzly
1. | Sv | = součet hodnot všech uzlů
2. | S | = součet nastavených hodnot S uzlu
3. Entropie (SV) = entropie aktuálního uzlu
Příklad:
Nyní jsme pochopili celý koncept použitý v algoritmu ID3, nyní je čas implementovat pomocí příkladů Podívejme se na jeden příklad.
Z výše uvedeného příkladu můžete vidět, že existují 4 funkce a na základě odvozeného stromu je savec nebo plaz
- Najděte všechny informace o informacích o všech funkcích a vyberte kořenový uzel, který je největší mezi všemi
vzorec pro informační zisk=
Jak jste vypočítali pro I.G všechny funkce v našem příkladu pro ozubené
Jak lze vypočítat entropii H(S):
1. Získání informací o kvalitě:
Podle výše uvedených výsledků určíme, že strom vybere vlasy jako kořenový uzel a dále se rozdělí
2 .Rozděluje strom dále:
Zvažte situaci, kdy vlasy mají veškerou skutečnou hodnotu, pokud najdeme vše entropie pro skutečné hodnoty se stává 0 takže říkáme, že pro všechny vlasy a skutečné hodnoty předpovídá savce
Nyní se podívejte na strom
3. Uvažujme scénář Vlasy = Falešný:
Entropie, když » vlasy = ne vlasy «
Na základě údajů id3 níže najděte zisk informací pro všechny kromě vlasů = Ne vlasy
shora Got Informace Získat to vybrat nohy jako podřízený uzel Parent Hair rozděluje strom podle toho, jak vidíme na obrázku níže
4. Nyní zvažte » Nohy = Nohy » zde najděte informace o zisku a rozštěpech
Entropie aktuálního uzlu Legs:
Information Gain je dán
nyní zvažuje nejvyšší I.G volí ozubený jak je pravda dětského uzlu, je savec a nepravdivý jako plaz výběr
Finální strom je uveden níže:
Následujte mě na propojeném a pokud se vám líbí článek, který mě podporuje, je uvedeno níže
