Rozhodovací strom

Rozhodovací strom (také nazývaný klasifikační strom nebo regresní strom) je nástroj pro podporu rozhodování používaný ve strojovém učení , analýze dat a statistice . Struktura stromu je "listy" a "větve". Na okrajích („větvech“) rozhodovacího stromu jsou zapsány vlastnosti, na kterých závisí účelová funkce, hodnoty účelové funkce jsou zapsány do „listů“ a ve zbývajících uzlech jsou vlastnosti, kterými případy se liší. Chcete-li klasifikovat nový případ, musíte sejít po stromu na list a vrátit odpovídající hodnotu.

Takové rozhodovací stromy jsou široce používány při dolování dat. Cílem je vytvořit model , který předpovídá hodnotu cílové proměnné na základě více vstupních proměnných.

Každý list představuje hodnotu cílové proměnné, jak se mění od kořene podél okrajů stromu k listu. Každý vnitřní uzel je mapován na jednu ze vstupních proměnných.

Strom lze také "naučit" rozdělením původních sad proměnných do podmnožin na základě kontroly hodnot vlastností. Tato akce se opakuje na každé z výsledných podmnožin. Rekurze končí, když má podmnožina v uzlu stejné hodnoty cílové proměnné, takže k předpovědím nepřidává žádnou hodnotu. Proces shora dolů, indukce rozhodovacího stromu (TDIDT) [1] , je příkladem pohlcujícího chamtivého algoritmu a je zdaleka nejběžnější strategií rozhodovacího stromu pro data, ale není jedinou možnou strategií.

Při dolování dat lze rozhodovací stromy použít jako matematické a výpočetní techniky, které pomohou popsat, klasifikovat a zobecnit sadu dat, kterou lze zapsat následovně:

Závislá proměnná Y je cílová proměnná, která má být analyzována, klasifikována a shrnuta. Vektor se skládá ze vstupních proměnných , , atd., které se používají k dokončení tohoto úkolu.

Základní definice

Analýza rozhodovacího stromu využívá vizuální a analytický nástroj pro podporu rozhodování k výpočtu očekávaných hodnot (nebo očekávaných přínosů) konkurenčních alternativ.

Rozhodovací strom se skládá ze tří typů uzlů:

• Rozhodovací uzly – obvykle reprezentované čtverci
• Uzly pravděpodobnosti - reprezentované jako kruh
• Uzly uzavírací – znázorněné jako trojúhelník

Na obrázku výše by se rozhodovací strom měl číst zleva doprava. Rozhodovací strom nemůže obsahovat cyklické prvky, to znamená, že každý nový list se může následně pouze rozdělit, neexistují žádné konvergující cesty. Při ruční konstrukci stromu tedy můžeme narazit na problém jeho dimenze, proto zpravidla můžeme rozhodovací strom získat pomocí specializovaného softwaru. Rozhodovací strom je obvykle prezentován ve formě schematického výkresu, což usnadňuje pochopení a analýzu.

Typologie stromů

Rozhodovací stromy používané při dolování dat jsou dvou hlavních typů:

• Strom pro klasifikaci, když je předpokládaný výsledek třída, do které data patří;
• Strom pro regresi, kdy lze předpokládaný výsledek považovat za reálné číslo (například cena domu nebo délka pobytu pacienta v nemocnici).

Výše uvedené termíny poprvé zavedl Breiman a kol . [2]

Některé metody umožňují sestavit více než jeden rozhodovací strom (soubory rozhodovacích stromů):

1. Bagrování přes rozhodovací stromy, nejranější přístup . Sestaví několik rozhodovacích stromů, opakovaně interpoluje data s náhradou ( bootstrap ), a jako konsensuální odpověď dává hlas stromům (jejich průměrnou předpověď); [3]
2. Klasifikátor Random Forest je založen na baggingu , ale navíc k němu náhodně vybírá podmnožinu prvků v každém uzlu, aby byly stromy nezávislejší;
3. Zesílení stromu lze použít pro regresní i klasifikační problémy. [4] Jedna implementace posilování stromu, algoritmus XGBoost , byla opakovaně použita vítězi soutěží analýzy dat.
4. "Rotace lesa" - stromy, ve kterých je každý rozhodovací strom analyzován první aplikací analýzy hlavních komponent (PCA) na náhodné podmnožiny vstupních prvků. [5]

Algoritmy konstrukce stromů

Další funkci lze vybrat různými způsoby:

• Algoritmus ID3 , kde k volbě vlastnosti dochází na základě informačního zisku ( angl.  Gain ), nebo na základě Giniho kritéria .
• Algoritmus C4.5 (vylepšená verze ID3), kde je výběr vlastností založen na normalizovaném informačním zisku ( Gain Ratio ) . 
• Algoritmus CART a jeho modifikace — IndCART, DB-CART.
• Automatický detektor chí-kvadrát interakce (CHAID). Provádí víceúrovňové oddělení při výpočtu klasifikace stromu; [6]
• MARS: rozšiřuje rozhodovací stromy pro zlepšení digitálního zpracování dat.

V praxi jsou v důsledku těchto algoritmů stromy často příliš podrobné, což při další aplikaci způsobuje mnoho chyb. To je způsobeno fenoménem nadměrného vybavení . Pro redukci stromů se používá prořezávání ( anglicky  pruning ).

Výhody metody

Na rozdíl od jiných metod dolování dat má metoda rozhodovacího stromu několik výhod:

• Snadno pochopitelné a interpretovatelné.
• Nevyžaduje speciální přípravu dat, jako je normalizace dat, přidávání fiktivních proměnných a odstraňování chybějících dat.
• Umět pracovat s kategorickými i intervalovými proměnnými. (Jiné metody pracují pouze s daty, kde existuje pouze jeden typ proměnné. Například poměrovou metodu lze aplikovat pouze na nominální proměnné a metodu neuronové sítě pouze na proměnné měřené na intervalové škále.)
• Používá model „bílé skříňky“, to znamená, že pokud je v modelu pozorována určitá situace, pak ji lze vysvětlit pomocí booleovské logiky. Příkladem "černé skříňky" může být umělá neuronová síť , protože získané výsledky je obtížné vysvětlit.
• Umožňuje vyhodnotit model pomocí statistických testů. To umožňuje posoudit spolehlivost modelu.
• Metoda funguje dobře, i když byly porušeny původní předpoklady zahrnuté v modelu.
• Umožňuje pracovat s velkým množstvím informací bez speciálních přípravných postupů. Tato metoda nevyžaduje speciální vybavení pro práci s velkými databázemi.

Nevýhody metody

• Problém získání optimálního rozhodovacího stromu je NP-úplný problém , z hlediska některých aspektů optimality i pro jednoduché problémy [7] [8] . Praktická aplikace algoritmu rozhodovacího stromu je tedy založena na heuristických algoritmech, jako je „chamtivý“ algoritmus, kde je jediné optimální řešení zvoleno lokálně v každém uzlu. Takové algoritmy nemohou zajistit optimalitu celého stromu jako celku.
• Proces vytváření rozhodovacího stromu může vytvořit příliš složité struktury, které plně nereprezentují data. Tento problém se nazývá overfitting [9] . Abychom se tomu vyhnuli, je nutné použít metodu „úpravy hloubky stromu“.
• Existují pojmy, které je obtížné z modelu pochopit, protože je model popisuje komplexně. Tento jev může být způsoben problémy XOR, parity nebo multiplexeru. V tomto případě máme co do činění s neúměrně velkými stromy. Existuje několik přístupů k řešení tohoto problému, například pokus o změnu reprezentace konceptu v modelu (vypracování nových úsudků) [10] , nebo použití algoritmů, které koncept úplněji popisují a reprezentují (např. , metoda statistických vztahů, logika induktivního programování).
• U dat, která zahrnují kategorické proměnné s velkým souborem úrovní (uzávěrů), je větší informační váha přiřazena těm znakům, které mají více úrovní [11] .

Kontrola hloubky stromu

Omezování hloubky stromu je technika, která umožňuje zmenšit velikost rozhodovacího stromu odstraněním částí stromu, které mají malou hmotnost.

Jednou z otázek, která vyvstává v algoritmu rozhodovacího stromu, je optimální velikost konečného stromu. Malý strom tedy nemusí zachytit tu či onu důležitou informaci o vzorovém prostoru. Je však těžké říci, kdy by se měl algoritmus zastavit, protože nelze předvídat, které přidání uzlů významně sníží chybu. Tento problém je známý jako "efekt horizontu". Obecná strategie omezení stromu je však zachována, to znamená, že odstranění uzlů je implementováno, pokud neposkytují další informace [12] .

Úprava hloubky stromu by měla snížit velikost modelu trénovacího stromu, aniž by se snížila jeho přesnost předpovědi nebo prostřednictvím křížové validace. Existuje mnoho metod pro úpravu hloubky stromu, které se liší mírou optimalizace výkonu.

Regulační metody

Prořezávání stromů lze provádět shora dolů nebo zdola nahoru. Shora dolů - prořezávání začíná od kořene, zdola nahoru - počet listů stromu se snižuje. Jednou z nejjednodušších metod řízení je snížit chybu omezení stromu. Počínaje listy je každý uzel nahrazen nejoblíbenější třídou. Pokud změna neovlivní přesnost predikce, uloží se.

Příklad problému

Předpokládejme, že nás zajímá, zda náš oblíbený fotbalový tým vyhraje příští zápas. Víme, že to závisí na řadě parametrů; vyjmenovat je všechny je beznadějný úkol, takže se omezíme na ty hlavní:

• zda je soupeř výše v pořadí;
• zda se zápas hraje doma;
• zda některý z vedoucích družstev nevynechá zápas;
• prší.

Máme k tomu pár statistik:

Rád bych pochopil, zda náš tým vyhraje v příštím zápase.

Viz také

• Náhodný les  - klasifikátor založený na použití komisí z rozhodovacích stromů
• Rekvalifikace
• Strojové učení  je třída metod umělé inteligence , jejichž charakteristickým rysem není přímé řešení problému, ale učení v procesu aplikace řešení mnoha podobných problémů.
• Rozhodovací tabulka

Poznámky

1. ↑ Quinlan, JR Indukce rozhodovacích stromů  //  Strojové učení. - Kluwer Academic Publishers, 1986. - No. 1 . - S. 81-106 . Archivováno z originálu 20. ledna 2022.
2. ↑ 1 2 Breiman, Lev; Friedman, JH, Olshen, RA, & Stone, CJ Klasifikační a regresní stromy  . - Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984. - ISBN 978-0-412-04841-8 .
3. ↑ Breiman, L. Bagging Predictors  //  Machine Learning. - 1996. - Ne. 24 . - S. 123-140 .
4. ↑ Friedman, JH Stochastické zesílení gradientu  . — Stanfordská univerzita, 1999.
5. ↑ Hastie, T., Tibshirani, R., Friedman, JH Prvky statistického učení : Dolování dat, inference a predikce  . — New York: Springer Verlag, 2001.
6. ↑ Kas ,  G.V. _  Řada C (Aplikovaná statistika). — Sv. 29 , č. 2 . - str. 119-127 . - doi : 10.2307/2986296 . Archivováno z originálu 2. dubna 2022.
7. ↑ Hyafil, Laurent; Rivest, R.L. Konstrukce optimálních binárních rozhodovacích stromů je NP-kompletní  //  Dopisy pro zpracování informací. - 1976. - Sv. 5 , č. 1 . - str. 15-17 . - doi : 10.1016/0020-0190(76)90095-8 .
8. ↑ Murthy S. Automatická konstrukce rozhodovacích stromů z dat: multidisciplinární průzkum  //  Data Mining and Knowledge Discovery. - 1998. - Ne. 2 . - str. 345-389 . Archivováno z originálu 2. dubna 2022.
9. ↑ Max Bramer. Principy  dolování dat . - Springer, 2007. - ISBN 978-1-84628-765-7 .
10. ↑ Induktivní logické programování  / Horváth, Tamás; Yamamoto, Akihiro, eds. - Springer, 2003. - ISBN 978-3-540-20144-1 .
11. ↑ Deng, H., Runger, G., Tuv, E. Bias of Importance Measures for Multi-valued Attributes and Solutions // Umělé neuronové sítě a strojové učení - ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792  ( ( anglicky) / Honkela, T., Duch, W., Girolami, M., Kaski, S. (eds). - Berlin, Heidelberg: Springer, 2011. - ISBN 978-3-642-21737-1 .
12. ↑ Rychlý algoritmus prořezávání rozhodovacího stromu zdola nahoru

Odkazy

• Poznámky k přednášce o rozhodovacích stromech
• Applet rozhodovacích stromů poskytuje několik vzorových datových sad příkladů, které se můžete naučit a klasifikovat

Literatura

• Levitin A. V. Kapitola 10. Meze výkonu algoritmů: Rozhodovací stromy // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 409-417. — 576 s. — ISBN 978-5-8459-0987-9
• Paklin N.B., Oreshkov V.I. Kapitola 9. // Business Analytics: Od dat ke znalostem (+CD): Výukový program. 2. vyd. - Petrohrad. : Peter, 2013. - S. 428-472. - ISBN 978-5-459-00717-6 .