Co je to rozhodovací strom?

Co je to rozhodovací strom?

A rozhodovací strom je užitečný algoritmus strojového učení používaný pro regresní i klasifikační úlohy. Název „rozhodovací strom“ pochází ze skutečnosti, že algoritmus neustále rozděluje datovou sadu na menší a menší části, dokud nejsou data rozdělena do jednotlivých instancí, které jsou poté klasifikovány. Pokud byste měli vizualizovat výsledky algoritmu, způsob rozdělení kategorií by připomínal strom a mnoho listů.

To je rychlá definice rozhodovacího stromu, ale pojďme se hlouběji ponořit do toho, jak rozhodovací stromy fungují. Když budete lépe rozumět tomu, jak rozhodovací stromy fungují, a také jejich případům použití, pomůže vám to zjistit, kdy je použít během vašich projektů strojového učení.

Formát rozhodovacího stromu

Rozhodovací strom je hodně jako vývojový diagram. Chcete-li použít vývojový diagram, začnete v počátečním bodu nebo kořenu grafu a poté na základě toho, jak splníte kritéria filtrování tohoto počátečního uzlu, se přesunete do jednoho z dalších možných uzlů. Tento proces se opakuje, dokud není dosaženo konce.

Rozhodovací stromy fungují v podstatě stejným způsobem, přičemž každý vnitřní uzel ve stromu je jakýmsi kritériem testování/filtrování. Uzly na vnější straně, koncové body stromu, jsou štítky pro daný datový bod a nazývají se „listy“. Větve, které vedou z vnitřních uzlů k dalšímu uzlu, jsou prvky nebo konjunkce prvků. Pravidla používaná ke klasifikaci datových bodů jsou cesty, které běží od kořene k listům.

Algoritmy pro rozhodovací stromy

Rozhodovací stromy fungují na algoritmickém přístupu, který rozděluje datovou sadu na jednotlivé datové body na základě různých kritérií. Tato rozdělení se provádějí s různými proměnnými nebo různými funkcemi datové sady. Pokud je například cílem určit, zda je pes nebo kočka popisován vstupními funkcemi, proměnné, na které jsou data rozdělena, mohou být věci jako „drápy“ a „štěky“.

Jaké algoritmy se tedy používají ke skutečnému rozdělení dat na větve a listy? Existují různé metody, které lze použít k rozdělení stromu, ale nejběžnější metodou rozdělení je pravděpodobně technika označovaná jako „rekurzivní binární štěpení“. Při provádění tohoto způsobu rozdělení proces začíná u kořene a počet prvků v datové sadě představuje možný počet možných rozdělení. K určení toho, kolik přesnosti bude každé možné rozdělení stát, se používá funkce a rozdělení se provádí pomocí kritérií, která obětují nejmenší přesnost. Tento proces se provádí rekurzivně a podskupiny se vytvářejí pomocí stejné obecné strategie.

K určení nákladů na rozdělení se používá nákladová funkce. Pro regresní úlohy a klasifikační úlohy se používá odlišná nákladová funkce. Cílem obou nákladových funkcí je určit, která odvětví mají nejpodobnější hodnoty odezvy, případně větve nejvíce homogenní. Zvažte, že chcete, aby testovací data určité třídy sledovala určité cesty, a to dává intuitivní smysl.

Pokud jde o funkci regresních nákladů pro rekurzivní binární rozdělení, algoritmus použitý k výpočtu nákladů je následující:

součet(y – předpověď)^2

Predikce pro konkrétní skupinu datových bodů je průměrem odezev trénovacích dat pro tuto skupinu. Všechny datové body procházejí funkcí nákladů, aby se určily náklady pro všechna možná rozdělení, a vybere se rozdělení s nejnižšími náklady.

Pokud jde o nákladovou funkci pro klasifikaci, funkce je následující:

G = součet(pk * (1 – pk))

Toto je skóre Gini a je to měření účinnosti rozdělení na základě toho, kolik instancí různých tříd je ve skupinách vyplývajících z rozdělení. Jinými slovy, kvantifikuje, jak jsou skupiny po rozdělení smíšené. Optimální rozdělení je, když všechny skupiny vzniklé rozdělením sestávají pouze ze vstupů z jedné třídy. Pokud bylo vytvořeno optimální rozdělení, hodnota „pk“ bude buď 0 nebo 1 a G se bude rovnat nule. Můžete uhodnout, že nejhorší případ rozdělení je ten, kde je zastoupení tříd v rozdělení 50-50, v případě binární klasifikace. V tomto případě by hodnota „pk“ byla 0.5 a G by také byla 0.5.

Proces dělení je ukončen, když jsou všechny datové body převedeny na listy a klasifikovány. Možná však budete chtít zastavit růst stromu brzy. Velké složité stromy jsou náchylné k nadměrnému vybavení, ale k boji proti tomu lze použít několik různých metod. Jednou z metod, jak omezit přemontování, je zadat minimální počet datových bodů, které budou použity k vytvoření listu. Další metodou kontroly nadměrného vybavení je omezení stromu na určitou maximální hloubku, která řídí, jak dlouho se může cesta táhnout od kořene k listu.

Další proces spojený s tvorbou rozhodovacích stromů je prořezávání. Prořezávání může pomoci zvýšit výkon rozhodovacího stromu odstraněním větví obsahujících prvky, které mají pro model malou prediktivní schopnost/malý význam. Tímto způsobem se snižuje složitost stromu, je méně pravděpodobné, že se přepasuje, a zvyšuje se prediktivní užitečnost modelu.

Při provádění prořezávání může proces začít buď v horní části stromu, nebo ve spodní části stromu. Nejjednodušší metodou prořezávání je však začít s listy a pokusit se vypustit uzel, který obsahuje nejběžnější třídu v tomto listu. Pokud se přesnost modelu nezhorší, když se to udělá, změna se zachová. Pro prořezávání se používají i jiné techniky, ale výše popsaná metoda – prořezávání se sníženou chybou – je pravděpodobně nejběžnější metodou prořezávání rozhodovacích stromů.

Úvahy o používání rozhodovacích stromů

Rozhodovací stromy jsou často užitečné když je třeba provést klasifikaci, ale hlavním omezením je doba výpočtu. Rozhodovací stromy mohou objasnit, které funkce ve vybraných souborech dat mají největší prediktivní schopnost. Navíc, na rozdíl od mnoha algoritmů strojového učení, kde pravidla použitá ke klasifikaci dat mohou být obtížně interpretovatelná, rozhodovací stromy mohou poskytovat interpretovatelná pravidla. Rozhodovací stromy jsou také schopny využívat kategorické i spojité proměnné, což znamená, že je potřeba méně předběžného zpracování ve srovnání s algoritmy, které zvládnou pouze jeden z těchto typů proměnných.

Rozhodovací stromy obvykle nefungují příliš dobře, když se používají k určení hodnot spojitých atributů. Dalším omezením rozhodovacích stromů je to, že při klasifikaci, pokud existuje málo příkladů školení, ale mnoho tříd, má rozhodovací strom tendenci být nepřesný.