Rozhodovací stromy mají zvláštní místo mezi mými oblíbenými algoritmy strojového učení, a když se ponoříme do tohoto článku, zjistíte, proč si v této oblasti získaly takovou popularitu.
V oblasti strojového učení se rozhodovací stromy často označují jako „neparametrické modely“. Toto označení označuje jejich flexibilitu, protože rozhodovací stromy nezvyšují počet parametrů, protože do modelu jsou přidávány další funkce (pokud jsou správně konstruovány). Rozhodovací stromy mají navíc schopnost poskytovat jak kategorické předpovědi, jako je určování typu rostliny, tak numerické předpovědi, jako je odhadování ceny domu.
Než se pustím do skutečného tématu, zeptám se vás:
Ale co skutečně odlišuje rozhodovací stromy a dělá je vysoce uznávanými v komunitě strojového učení?
Odpověď spočívá v jejich schopnosti napodobovat myšlení na lidské úrovni, takže je lze snadno pochopit a interpretovat. Rozhodovací stromy nám umožňují pochopit základní logiku dat, což umožňuje zjednodušenou interpretaci výsledků. Tato jedinečná vlastnost nám umožňuje odhalit složité vzorce v datech a podporuje hlubší pochopení rozhodovacího procesu.
Nerad používám vymyšlený termín vytvořený předchozími generacemi, ale stejně se zde stále vyžívám v principech strojového učení.
Jak tedy lépe porozumět rozhodovacím stromům v jednodušších pojmech? Co takhle postavit si jeden pro sebe? Možná jim pak budeme moci lépe porozumět. (Doufám, že ano!)
Než se však ponoříme do vytváření rozhodovacího stromu, seznamme se s několika pojmy:
Kořenový uzel: Toto je výchozí bod stromu. V běžném rozhodovacím stromu vyhodnocuje proměnnou, která nejlépe rozděluje data.
Rozhodovací uzel/zprostředkující uzel: Jsou to uzly, kde se vyhodnocují proměnné, ale nejsou to konečné uzly, kde se provádějí předpovědi.
Listové uzly: To jsou uzly, kde se vytvářejí předpovědi. Když datový bod dosáhne koncového uzlu, proces rozdělení se zastaví.
prořezávání: To se týká odstranění uzlů, aby se zabránilo nadměrnému vybavení.
Rozhodovací stromy jsou konstruovány pomocí dvou hlavních prvků: uzlů a větví. V každém uzlu je vyhodnocena jedna z vlastností našich dat, aby bylo možné rozdělit pozorování během trénovacího procesu nebo určit cestu, kterou by měl konkrétní datový bod sledovat při vytváření predikce.
Pro ilustraci si uveďme jednoduchý příklad rozhodovacího stromu. Předpokládejme, že chceme určit, zda hrát tenis podle počasí. Pokud je zataženo, hraje se tenis. Pokud je slunečno, kontrolujeme vlhkost. Pokud je vlhkost vysoká, tenis se nehraje. Jak již bylo zmíněno dříve, základní logika rozhodovacích stromů je jednoduchá, a to je skutečně odlišuje.
Během konstrukce rozhodovacích stromů jsou rekurzivně vyhodnocovány různé funkce a v každém uzlu je vybrána vlastnost, která nejlépe rozděluje data.
Nyní, když máte obecnou představu o tom, co jsou rozhodovací stromy, můžete mít několik otázek:
— Kterou funkci bychom měli zvolit jako první?
— Jaké by mělo být pořadí dělení?
— Jak určíme počet podřízených uzlů?
— Jak můžeme porovnat dva rysy, abychom určili, který z nich je lepší pro rozdělení?
— Jak určíme kritéria rozdělení?
Než odpovím na tyto otázky, dovolte mi představit vám následující témata.
Entropie řídí, jak rozhodovací strom rozhoduje, kam rozdělit data. To je měření nečistota nebo náhodnost v datových bodech.
Entropie je počítáno mezi 0 a 1. Projekt menší hodnota entropie tím lépe.
Vezměme si příklad červených, modrých a zelených kuliček v krabicích. Krabice se 6 modrými koulemi bude mít velmi nízkou (nulovou) entropii, zatímco krabice se 2 modrými, 2 zelenými a 2 červenými koulemi by měla relativně vysokou entropii.
Vzorec pro výpočet informační entropie pro datovou sadu s třídami C:
kde pᵢ je pravděpodobnost náhodného výběru prvku třídy i (tj. podíl datové sady tvořené třídou i).
Vezměme si příklad, abychom to lépe pochopili. Zvažte datovou sadu s 1 modrou, 2 zelenými a 3 červenými kuličkami, pak:
Původní vzorec byl rozšířen, aby ukázal tři třídy v datové sadě
Víme, pb = 1/6 (modré), protože 1/6 datové sady je modrá. Podobně, pg = 2/6 (zelené) a pr = 3/6 (červené). Tím pádem,
Entropie pro 1 modrou, 2 zelené a 3 červené koule
Zatímco u datové sady sestávající pouze z modrých kuliček by entropie byla:
Entropie pouze pro modré koule = nula, entropie je nulová, když máte třídu stejných proměnných.
Informační zisk je metrika, která nám pomáhá určit, který atribut v dané sadě vektorů trénovacích funkcí je nejužitečnější pro rozlišení mezi cílovými třídami. Používáme jej k rozhodování o pořadí atributů v uzlech Rozhodovacího stromu.
Vzorec pro získávání informací
Informační zisk = Entropie rodiče — Průměrná entropie dětí
Tento vzorec pro získávání informací je docela intuitivní. Díváme se na rozdíl mezi entropií rodiče a dětí.
Vysoké snížení entropie je dobré, protože jsme schopni lépe rozlišovat mezi cílovými třídami. To jednoduše znamená, že vybereme funkci, která má nejvyšší informační zisk.
Gini Index je alternativním kritériem používaným pro rozdělení datové sady na základě jejích vlastností. Ačkoli se pro tento účel běžně používá entropie, Giniho index poskytuje jednodušší metodu výpočtu. Výpočet entropie zahrnuje logaritmické operace, které mohou být časově náročné a složité. Oproti tomu Gini Index nabízí přímočarý výpočet.
Knihovna Scikit-Learn využívá Gini Index k určení optimální funkce pro rozdělení rozhodovacího stromu. Pomocí indexu Gini je Scikit-Learn schopen efektivně identifikovat nejlepší funkce pro rozhodování během procesu výstavby stromu.
kde pj označuje pravděpodobnost náhodného výběru prvku třídy j (tj. podíl datové sady tvořené třídou j).
Poměr zisku informací je kritérium používané k vyhodnocení potenciálu funkce efektivně rozdělit data.
Poměr informačního zisku se vypočítá vydělením informačního zisku rozdělením informací (SI) funkce. Informace o rozdělení představuje potenciální informace generované rozdělením datové sady na základě konkrétní funkce.
Vypočítá se pomocí vzorce:
kde se sumace provádí přes všechny možné hodnoty prvku. Konečně, poměr informačního zisku je dán:
Poměr zisku informací (funkce) = IG (funkce) / SI (funkce)
Konečně jsme tady, po batůžkách za naším pátráním, protože naše cesta se chýlila ke konci. Nyní jsme připraveni uvolnit sílu algoritmů, které konstruují rozhodovací strom.
Než se budeme starat o algoritmy, pojďme vybrat úlohu, prostředí a předběžné zpracování datové sady. V tomto článku prozkoumáme implementaci algoritmů ID3, CART, C4.5, Random Forest a Gradient Boosting v Pythonu.
Než se ponoříme do implementace algoritmů rozhodovacího stromu, je nezbytné vybrat vhodnou datovou sadu, která bude sloužit jako základ pro naši analýzu. Výběr datové sady hraje zásadní roli v přesnosti a relevanci výsledného rozhodovacího stromu.
Při výběru datové sady zvažte následující faktory:
1. Úkol a cíl: Určete konkrétní úkol nebo problém, který chcete vyřešit, pomocí rozhodovacího stromu. Pracujete na klasifikačním nebo regresním problému? Pochopení úkolu vás povede při výběru datové sady, která odpovídá vašemu cíli.
2. Relevance domény: Vyberte datovou sadu, která je relevantní pro doménu nebo odvětví, na které se zaměřujete. To zajistí, že rozhodovací strom bude poskytovat cenné poznatky a smysluplné předpovědi v kontextu vaší oblasti zájmu.
3. Kvalita dat: Posuďte kvalitu a spolehlivost datové sady. Zkontrolujte chybějící hodnoty, odlehlé hodnoty a nekonzistence, které mohou ovlivnit výkon algoritmů rozhodovacího stromu. Ujistěte se, že datová sada je čistá a reprezentativní pro scénář reálného světa, který chcete modelovat.
4. Velikost datové sady: Zvažte velikost datové sady. Velká datová sada může poskytnout robustnější a přesnější rozhodovací stromy, zatímco malá datová sada může vést k přeplnění. Usilujte o rovnováhu, která umožňuje dostatečný počet pozorování bez přetížení algoritmů.
Jakmile identifikujete vhodnou datovou sadu, je čas ji předzpracovat, aby bylo zajištěno, že je v čistém a vhodném formátu pro algoritmy rozhodovacího stromu.
V další části se ponoříme do předzpracování dat, než začneme s implementací algoritmů. Předzpracování dat je zásadním krokem, který zajišťuje, že datová sada je ve vhodném formátu pro algoritmus, a pomáhá zlepšit přesnost a efektivitu výsledného rozhodovacího stromu.
Importoval jsem datovou sadu z UCI (https://archive.ics.uci.edu/dataset/367/dota2+games+results), abych provedl binární klasifikaci pomocí rozhodovacích stromů.
Z velkého množství dostupných algoritmů pro vytváření rozhodovacích stromů jsme vybrali ty nejběžněji používané v reálných scénářích. Podívejme se podrobně na každý algoritmus:
- ID3 (iterativní dichotomizér 3):
Algoritmus ID3 využívá kritérium informačního zisku k výběru nejlepších atributů pro rozdělení uzlů v rozhodovacím stromu. Rekurzivně konstruuje strom na základě výpočtů informačního zisku. Implementujeme ID3 od nuly v Pythonu, aniž bychom se spoléhali na nějaké externí knihovny.
Abychom mohli předpovědět klasifikaci pomocí algoritmu ID3, musíme po provedení dělení na základě nejlepšího rozdělení vypočítat entropii rodičovského a potomka.
Po výpočtu entropie je nezbytné určit informační zisk, jak je ukázáno níže, aby se našlo nejlepší rozdělení
Přesnost vypočtená pomocí algoritmu ID3: 0.9235833783054507
2. C4.5:
C4.5 je rozšířením algoritmu ID3, které zahrnuje další funkce, jako je zpracování chybějících hodnot a spojité atributy. K rozhodování o výběru atributu využívá kritérium poměru zisku. Ponoříme se do podrobností implementace C4.5 a prodiskutujeme jeho výhody oproti ID3.
Abychom dosáhli C4.5, musíme před zadáním do modelu vypočítat kritérium poměru zisku informace, abychom předpověděli přesnost.
Přesnost vypočtená pomocí algoritmu C4.5: 0.921856449001619
3. KOŠÍK (Klasifikační a regresní stromy):
CART je všestranný algoritmus, který lze použít pro klasifikační i regresní úlohy. K určení rozdělení atributů používá Gini index nebo střední čtvercovou chybu (MSE) jako míry nečistot. Prozkoumáme principy fungování CART a pochopíme, jak řeší různé typy problémů.
Potřebujeme vypočítat Gini index, abychom mohli vypočítat přesnost pomocí algoritmu CART.
Přesnost předpovězená pomocí algoritmu CART: 0.921856449001619
4. Náhodný les:
Random Forest je výkonná souborová metoda, která kombinuje více rozhodovacích stromů a agreguje jejich předpovědi, aby zlepšila přesnost a snížila nadměrné přizpůsobení. Zavádí náhodnost pomocí bootstrappingu a náhodného výběru funkcí. Implementujeme Random Forest v Pythonu a prodiskutujeme výhody této techniky souboru.
Přesnost předpovězená pomocí Random Forest: 0.95876956287102
5. Zesílení přechodu:
Gradient Boosting je další souborová technika, která iterativně vytváří rozhodovací stromy, přičemž každý následující strom má za cíl opravit chyby, kterých se dopustily předchozí stromy. Dosahuje vynikajícího výkonu spojením slabých žáků do silného prediktoru. Prozkoumáme vnitřní fungování Gradient Boosting a prodiskutujeme jeho výhody oproti jiným algoritmům.
Přesnost předpovězená pomocí gradientBoosting: 0.9592012951969778
Využitím těchto široce používaných algoritmů můžeme efektivně vytvářet rozhodovací stromy, které poskytují cenné poznatky a umožňují informované rozhodování v různých oblastech.
V tomto článku jsme se zabývali implementací algoritmů ID3, C4.5, CART, Random Forest a Gradient Boosting pro konstrukci rozhodovacích stromů. Je důležité poznamenat, že výběr nejlepšího algoritmu závisí na několika faktorech, včetně konkrétního problému, charakteristik datové sady a požadovaných výsledků.
ID3, C4.5 a CART jsou základní algoritmy rozhodovacího stromu, které se dobře hodí pro úlohy zahrnující kategorické atributy a diskrétní cílové proměnné. ID3 je jednoduchý algoritmus, zatímco C4.5 a CART řeší některá omezení ID3, jako je zpracování spojitých atributů a chybějících hodnot. C4.5 s kritériem poměru zisku informace poskytuje lepší strategii výběru atributů při práci s atributy s velkým počtem odlišných hodnot.
Na druhou stranu, Gradient Boosting a Random Forest jsou souborové metody, které kombinují více rozhodovacích stromů k vytvoření přesnějších modelů. Gradient Boosting se zaměřuje na opakované vylepšování modelu učením se z chyb předchozích stromů, zatímco Random Forest vytváří rozmanitou sadu stromů začleněním náhodnosti. Tyto souborové metody, zejména Random Forest, jsou účinné při práci s vysokorozměrnými datovými sadami a zmírňují riziko nadměrného přizpůsobení.
Když je interpretovatelnost klíčová, algoritmy jako ID3 a CART poskytují transparentnější rozhodovací stromy, což umožňuje snazší pochopení a vysvětlení rozhodovacího procesu. Naproti tomu souborové metody jako Random Forest a Gradient Boosting bývají složitější a méně interpretovatelné kvůli kombinaci více stromů.
Nakonec výběr nejvhodnějšího algoritmu závisí na pečlivém zvážení konkrétního problému, povaze dat, požadované interpretovatelnosti modelu a kompromisu mezi přesností a složitostí. Výběrem správného algoritmu a jeho efektivní aplikací mohou být rozhodovací stromy mocnými nástroji pro informovaná rozhodnutí v různých oblastech.
Je však důležité poznamenat, že pokrytí bylo omezené a existuje několik aspektů, které mohou dále zlepšit hledání optimálního modelu rozhodovacího stromu. Tyto aspekty zahrnují zkoumání a ladění různých parametrů, jako je hloubka stromu a počet odhadů v souborových metodách, pro dosažení lepšího výkonu. Navíc zvážení prahu klasifikace a vyhodnocení modelu pomocí technik, jako je křivka ROC, může poskytnout pohled na chování modelu a pomoci optimalizovat jeho výkon.
Pro využití plného potenciálu rozhodovacích stromů je nezbytné ponořit se hlouběji do těchto aspektů, provést důkladné experimentování a použít vhodné techniky pro ladění hyperparametrů, prořezávání a hodnocení výkonu. Díky tomu můžeme dosáhnout přesnějších a spolehlivějších modelů rozhodovacího stromu, které efektivně řeší složitosti a výzvy skutečných problémů.
Algoritmus konstrukce rozhodovacího stromu je výkonná technika dolování dat používaná pro klasifikaci i regresní problémy.
Algoritmus začíná výběrem kořenového uzlu, který představuje nejdůležitější rozhodnutí nebo atribut, který má být učiněn.
Existuje několik algoritmů, které lze použít ke konstrukci rozhodovacích stromů, z nichž každý má svou vlastní sadu silných a slabých stránek. Některé z nejpopulárnějších algoritmů konstrukce rozhodovacího stromu zahrnují ID3, C4.5 a CART.
ID3 (iterativní dichotomizér 3):
Algoritmus ID3 (Iterative Dichotomiser 3) používá k výběru kořenového uzlu informační zisk.
Začíná výběrem atributu s nejvyšším informačním ziskem jako kořenového uzlu a poté rekurzivně rozděluje data na základě hodnot zvoleného atributu.
Algoritmus ID3 je jednoduchý a snadno pochopitelný, ale může být náchylný k přemontování, pokud se strom nechá růst příliš hluboko.
Algoritmus C4.5:
Algoritmus C4.5 je rozšířením algoritmu ID3, který k výběru kořenového uzlu používá poměr zisku informace místo zisku informace.
Poměr zisku informace je měřítkem relativní důležitosti atributu a pomáhá vyhnout se problému s přesahem, který může nastat u algoritmu ID3.
Algoritmus C4.5 je robustnější a přesnější než ID3, ale je také výpočetně dražší.
KOŠÍK (Klasifikační a regresní strom):
Algoritmus CART (Klasifikační a regresní strom) používá k výběru kořenového uzlu Giniho index.
Gini index je mírou znečištění dat a používá se k výběru atributu, který vede k největšímu snížení nečistot.
Algoritmus CART je podobný algoritmu C4.5, ale používá se také pro regresní problémy. Je robustnější a přesnější než ID3 a C4.5, ale je také výpočetně nákladný.
CHAID (chí-kvadrát automatický detektor interakce):
CHAID je užitečný pro kategorická data. Při výběru algoritmu konstrukce rozhodovacího stromu je důležité vzít v úvahu vlastnosti dat, dostupné výpočetní zdroje a požadovanou úroveň přesnosti.
Kromě toho je pro zlepšení přesnosti modelu důležité prořezávání stromu odstraněním větví s nízkou významností.
Díky porozumění různým algoritmům konstrukce rozhodovacího stromu a jejich silným a slabým stránkám mohou organizace efektivně využívat tyto výkonné nástroje k získávání cenných poznatků ze svých dat a přijímání informovanějších rozhodnutí.
Při výběru algoritmu konstrukce rozhodovacího stromu je důležité vzít v úvahu charakteristiky dat, dostupné zdroje výpočetního algoritmu c Decision Tree Construction a požadovanou úroveň přesnosti.
ID3 je jednoduché a snadno pochopitelné, ale může být náchylné k nadměrnému vybavení.
C4.5 a CART jsou robustnější a přesnější, ale také výpočetně dražší. CHAID je užitečný pro kategorická data.
Na závěr, Algoritmus konstrukce rozhodovacího stromu je výkonná technika dolování dat používaná pro klasifikaci i regresní problémy. Existuje několik algoritmů, které lze použít ke konstrukci rozhodovacích stromů, z nichž každý má svou vlastní sadu silných a slabých stránek.
Referenční knihy
Zde jsou knihy, které jsem použil jako reference pro psaní tohoto článku, neváhejte si je přečíst, pokud nechcete, aby se vaše znalosti omezovaly pouze na tento článek.
