Rozhodovací stromy Marta Žambochová
Obsah: 1 2
Úvod ................................................................................................................................... 2 Algoritmy pro vytváření rozhodovacích stromů ................................................................ 3 2.1 Algoritmus CART ...................................................................................................... 3 2.1.1 Klasifikační stromy ............................................................................................ 3 2.1.2 Regresní stromy.................................................................................................. 4 2.2 Algoritmus ID3 .......................................................................................................... 4 2.3 Algoritmus C4.5 ......................................................................................................... 5 2.4 AID ............................................................................................................................. 5 2.5 CHAID ....................................................................................................................... 6 2.6 QUEST ....................................................................................................................... 6 3 Literatura ............................................................................................................................ 7
1
Rozhodovací stromy Marta Žambochová
1 Úvod Velmi rozšířenou skupinou stromů, kterých se využívá v datových modelech, jsou různé typy rozhodovacích stromů. Rozhodovací stromy jsou struktury, které rekurzivně rozdělují zkoumaná data dle určitých rozhodovacích kritérií. Kořen stromu reprezentuje celý populační soubor. Vnitřní uzly stromu reprezentují podmnožiny populačního souboru . V listech stromu můžeme vyčíst hodnoty vysvětlované proměnné. Rozhodovací strom se vytváří rekurzivně dělením prostoru hodnot prediktorů (vysvětlující, nezávislé proměnné). Máme-li strom s jedním listem, hledáme otázku (podmínku větvení), která nejlépe rozděluje prostor zkoumaných dat do podmnožin, tj. maximalizuje kritérium kvality dělení (tzv. splitting criterium). Takto nám vznikne strom s více listy. Nyní pro každý nový list hledáme otázku, která množinu prediktorů náležící tomuto listu co nejlépe dělí do podmnožin. Proces dělení se zastaví, pokud bude splněno kritérium pro zastavení (tzv. stopping rule). Omezení obsažená v kritériu pro zastavení mohou být např. „hloubka“ stromu, počet listů stromu, stupeň homogennosti množin dat v listech, … Dalším krokem algoritmů je prořezávání stromu (prunning). Je nutno určit „správnou“ velikost stromu (příliš malé stromy dostatečně nevystihují všechny zákonitosti v datech, příliš veliké stromy zahrnují do popisu i nahodilé vlastnosti dat). Vygenerují se podstromy stromu vzniklé budovacím algoritmem a porovnává se kvalita generalizace těchto podstromů (jak dobře vystihují data). Postup může být takový, že se rozhodovací stromy nejdříve vytváří na tzv. trénovacích datech a poté se jejich kvalita ověří na tzv. testovacích datech. Jiným způsobem je křížová validace (cross validation), kdy k vytváření stromu a jeho podstromů použijí všechna data. Poté se data rozdělí na několik disjunktních, přibližně stejně velkých částí a postupně se vždy jedna část dat ze souboru vyjme. Pomocí vzniklých souborů dat se ověřuje kvalita stromu a jeho podstromů. Vybere se takový podstrom, který má nejnižší odhad skutečné chyby. Pokud existuje více podstromů se srovnatelným odhadem skutečné chyby, vybírá se ten nejmenší. Jednotlivé algoritmy vytváření rozhodovacích stromů se liší následnými charakteristikami: pravidlo dělení (splitting rule) kritérum pro zastavení (stoping rule) typ podmínek větvení o multivariantní (testuje se několik prediktorů) o univariantní (v daném kroku se testuje pouze jeden z prediktorů) způsob větvení o binární (každý z uzlů, kromě listů, se dělí na dva následníky) o k-ární (některý z uzlů se dělí na více než dvě části) typ výsledného stromu, popis obsahu listů o klasifikační stromy (v každém listu je přiřazení třídy) o regresní stromy (v každém listu je přiřazení konstanty – odhad hodnoty závislé proměnné) typ prediktorů kategoriální ordinální 2
2 Algoritmy pro vytváření rozhodovacích stromů Pro vytváření rozhodovacích stromů bylo vyvinuto velké množství algoritmů. Nejvíce používané jsou CART, ID3, C4.5, AID, CHAID a QUEST.
2.1 Algoritmus CART Algoritmus poprvé popsali jeho autoři Breiman, Freidman, Olshen a Stone v roce 1984 ve článku „Classification and Regression trees“. Algoritmus je použitelný v případě, že máme jednu nebo více nezávislých proměnných. Tyto proměnné mohou být buď spojité nebo kategoriální (ordinální i nominální). Dále máme jednu závislou proměnnou, která také může být kategoriální (nominální i ordinální) nebo spojitá. Výsledkem algoritmu jsou binární stromy, protože jsou zde přípustné pouze otázky (podmínky dělení) , na které je možno odpovědět ano/ne (Je věk menší než 30 let? Je pohlaví mužské? …) V každém kroku algoritmus prochází všechna možná dělení pomocí všech přípustných hodnot všech nezávislých proměnných a hledá nejlepší z těchto dělení. Měřítkem, které dělení je lepší, je zvýšení čistoty dat. To znamená, že jedno dělení je lepší než druhé, pokud jeho uskutečněním obdržíme dva homogennější (vzhledem k závislé proměnné) soubory dat než uskutečněním druhého dělení. Algoritmus dělení je různý pro klasifikační stromy a pro stromy regresní.
2.1.1 Klasifikační stromy Klasifikační stromy používáme v případě, že je závislá proměnná kategoriální. To znamená, že se soubor původních dat snažíme v závislosti na nezávislých proměnných rozdělit do skupin, přičemž, v ideálním případě, každá skupina má přiřazení ke stejné kategorii závislé proměnné. Homogenita uzlů-potomků je měřena pomocí tzv. funkce znečištění (impurity function) i(t). Maximální homogenita vzniklých dvou potomků je počítána jako maximální změna (snížení) znečištění i(t). i (t ) i (t r ) E (i (t d )) kde tr je rodičovský uzel, td je uzel-potomek. Pro pravého potomka tp, pravděpodobnost pravého potomka Pp a levého potomka tl, pravděpodobnost levého potomka Pl pak dosazením do vzorce pro střední hodnotu dostáváme. i (t ) i (t r ) Pl i (t l ) Pp i (t p ) Algoritmus CART řeší pro každý uzel maximalizační problém pro funkci i(t) přes všechna možná dělení uzlu, to znamená, že hledá dělení, které přináší maximální zlepšení homogenity dat. Funkci i(t) je možno definovat různými způsoby. Mezi dva nejrozšířenější patří tzv. Gini index a Twoing pravidlo. Gini index Gini index je asi nejpoužívanější definice funkce znečištění. Funkce i(t) je definována následovně: i (t ) P (k | t ) P (l | t ) k l
3
kde t je uzel, k,l jsou indexy třídy závislé proměnné, k,l = 1, …, K; P(k|t), P(l|t) jsou podmíněné pravděpodobnosti. Dosazením této funkce do předpisu pro i(t) dostáváme: K
K
K
k 1
k 1
k 1
i(t ) i(t r ) Pl i (t l ) Pp i (t p ) 1 P 2 (k | t r ) Pl (1 P 2 (k | t l )) Pp (1 P 2 (k | t p )) K
K
K
k 1
k 1
k 1
P 2 ( k | t r ) P 2 ( k | t l ) P 2 ( k | t p )
Gini index hledá v trénovacích datech největší třídu závislé proměnné a odděluje ji od ostatních dat. Gini index dobře funguje pro znečištěná data. Twoing pravidlo Na rozdíl od Gini indexu Twoing pravidlo hledá dvě třídy, které dohromady obsáhnou více než 50% dat. Twoing pravidlo maximalizuje následující změnu funkce znečištění. 2 Pl Pp K i(t ) P(k | tl ) P(k | t p ) 4 k 1 kde t je uzel, k,l jsou indexy třídy závislé proměnné, k,l = 1, …, K; Pp pravděpodobnost pravého potomka tp a Pl, pravděpodobnost levého potomka tl ; P(k|t), P(l|t) jsou podmíněné pravděpodobnosti. Vytváření stromů s pomocí Twoing pravidla je pomalejší než za použití Gini indexu. Výhodou ovšem je, že vytváříme více vybalancované stromy.
2.1.2 Regresní stromy Regresní stromy se používají v případě, že závislá proměnná není kategoriální. Každá její hodnota může být v obecnosti různá. V tomto případě algoritmus hledá nejlepší dělení na základě minimalizace součtu rozptylů v rámci jednotlivých dvou vzniklých uzlů-potomků. Algoritmus pracuje na základě algoritmu minimalizace součtu čtverců.
2.2 Algoritmus ID3 Další z užívaných algoritmů je algoritmus ID3 (Iterative Dichotomizer 3). Poprvé jej autor Quinlan,J.R. popsal v roce 1975. Tento algoritmus opět pracuje na principu induktivního vytváření stromu odshora dolů. Je založen na principu tzv. „Ockhamovy břitvy“ (jsou-li dva modely srovnatelně dobré, pak se preferuje jednodušší model a složitější je znevýhodněn). Algoritmus je použitelný v případech, že všechny proměnné jsou kategoriální. Je určený především pro vytváření menších stromů. Algoritmus opět začíná s jediným uzlem – kořenem stromu, jemuž náleží všechny datové objekty. V každém kroku je pro každý listový uzel, který dosud neobsahuje homogenní data, hledáno co nejlepší dělení, pomocí něhož vzniknou další listové uzly. V tomto algoritmu je pro dělení vybrán jeden z atributů (nezávislá proměnná) a dělení je provedeno na tolik uzlů-potomků, kolik má tento atribut kategorií. Jako testový je vybírán takový atribut, jehož míra charakterizující homogenitu dat je minimální. Tato míra
4
homogenity se nazývá entropie. Entropie je definována pro každou ze vznikajících větví předpisem: n n E (b) ( bc ) log 2 ( bc ) nb nb c kde b je vznikající větev, c je třída závislé proměnné, nb je počet objektů ve větvi b, ncb je počet objektů třídy c ve větvi b. Pro minimalizaci se pak používá průměrná entropie přes všechny větve dělení daného uzlu pro daný atribut, která je definována předpisem: n E ( b ) E (b) nt kde nt je celkový počet objektů ve všech větvích. Pokud existuje dělení pomocí nějakého atributu, které má hodnotu entropie 0, bude tento krok budování stromu poslední a proces dělení končí.
2.3 Algoritmus C4.5 Algoritmus popsal jeho autor Quinlan,J.R. v roce 1993 v materiálu „C4.5: Programs for Machine Learning“. Je založen na principu algoritmu ID3, ale má několik vylepšení, která jsou zvláště potřebná pro SW implementaci. Mezi tato vylepšení patří možnost využití algoritmu pro spojité atributy, pro data s chybějícími údaji, ale i další. Kromě obecné entropie je zde využívána i podmíněná entropie, která je definována předpisem: n n E ( x | T ) bx log 2 bx nb nb Na základě těchto dvou entropií je dále definován zisk, který se snažíme maximalizovat přes různá dělení atributů dle hodnot x. Zisk je definován následným předpisem: Zisk ( A, x) E A E ( x | A) kde A je vybraný atribut, EA jeho entropie, x hodnota.
2.4 AID V roce 1963 navrhli J.N. Morgan a J.A. Sonquist jednoduchou metodu na vytváření stromů pro předpovídání kvantitativní proměnné. Tuto metodu nazvali AID (Automatic Interaction Detection). Algoritmus začíná společným shlukem všech objektů a dále provádí postupně štěpení. Každý kvantitativní (nebo alespoň ordinální) prediktor je testován pro dělení následujícím způsobem. Setřídíme všech n (n je počet zkoumaných objektů) hodnot prediktoru a zkoušíme všech n-1 způsobů, jak tento setříděný soubor rozdělit na dvě části. Pro každé dělení vypočítáme vnitroskupinový součet čtverců hodnot závislé proměnné. Z těchto n-1 štěpení vybereme to nejlepší (s minimálním součtem čtverců) a toto budeme brát jako dělení daného prediktoru. Ke kategoriálním (ne ordinálním) prediktorům přistupujeme odlišně. Z důvodu, že kategorie nelze setřídit musíme zkoumat všechny možné skupiny pro štěpení na dvě části. 5
Těchto různých dělení je 2k-1 (kde k je počet kategorií). Dále pokračujeme obdobně jako v případě kvantitativních prediktorů výpočtem a minimalizací vnitroskupinových součtů čtverců hodnot závislé proměnné. Ze všech prediktorů nakonec vybereme pro výsledné dělení ten, který má nejmenší vnitroskupinový součet čtverců. Takto se pokračuje, dokud se nedostaneme k výsledku, že neexistuje žádné významné dělení.
2.5 CHAID Metodu CHAID (Chi-squared Automatic Interaction Detektor) vyvinul v roce 1980 G.V. Kass. Tato metoda je modifikací metody AID pro kategoriální závislou proměnnou. Výsledkem jsou nebinární stromy. Metoda využívá k testování 2- test. Z důvodu obavy o časovou náročnost v původním algoritmu autor hledá pouze suboptimální štěpení namísto prohledávání všech možných a hledání optimálního štěpení. Algoritmus štěpení probíhá následovně. V rámci jednoho listového uzlu se vytvoří kontingenční tabulka (rozměrů mxk) hodnot prediktoru (m kategorií) a závislé proměnné (k kategorií). Dále se najde dvojice kategorií prediktoru, pro které má subtabulka rozměrů 2xk nejméně významnou hodnotu 2- testu. Tyto dvě kategorie se sloučí. Tímto nám vzniká nová kontingenční tabulka o rozměrech (m-1)xk. Proces slučování opakujeme až do doby, kdy klesne významnost 2- testu pod předem zadanou hodnotu. Tímto je ukončen proces štěpení jednoho rodičovského uzlu na několik uzlů-potomků. Dále se pokračuje obdobně pro každý listový uzel až do doby nevýznamného výsledku 2- testu.
2.6 QUEST Tato metoda je popsána ve článku z roku 1997 autorů W.Y. Loh and Y.S. Shih: „Split selection methods for classification trees“. Algoritmus je použitelný pouze pro nominální závislou proměnnou. Obdobně, jako v případu CART, jsou vytvářeny pouze binární stromy. Na rozdíl od metody CART, která výběr proměnné pro štěpení uzlu a výběr dělícího bodu provádí v průběhu budování stromu současně, provádí metoda QUEST toto odděleně. Metoda QUEST (for Quick, Unbiased, Efficient, Statistical Tree) odstraňuje některé nevýhody algoritmů používajících vyčerpávající hledání (např. CART), jako je náročnost zpracování, snížení obecnosti výsledku, … Tato metoda je vylepšením algoritmu FACT, který popsali autoři W.-Z. Loh a N. Vanichsetakul v roce 1988. V prvním kroku algoritmus převede všechny kategoriální nezávislé proměnné na „ordinální“ pomocí CRIMCOORD transformace. Dále v každém listovém uzlu, je pro každou proměnnou prováděn ANOVA F-test. Pokud největší ze vzniklých F-statistik je větší než předem daná hodnota F0, pak příslušná proměnná je vybrána pro dělení uzlu. Pokud tomu tak není, je pro všechny proměnné proveden Levenův F-test. Pokud je největší Levenova F-statistika větší než F0, pak je příslušná proměnná vybrána pro dělení uzlu. Pokud tomu tak není (není žádní ANOVA Fstatistika ani Levenova F-statistika větší než hodnota F0, je pro dělení vybrána proměnná s největší ANOVA F-statistikou. Pro dělení uzlu je tedy vybrána ta nezávislá proměnná, která je se závislou proměnnou nejvíce asociována.
6
Pro hledání dělícího bodu pro vybranou nezávislou proměnnou je využívána metoda Kvadratické diskriminační analýzy (QDA), na rozdíl od algoritmu FACT, kde je využívána metoda Lineární diskriminační analýzy (LDA). Tento postup je rekurzivně opakován až do zastavení (na základě kritéria pro zastavení).
3 Literatura 1. Antoch J., Klasifikace a regresní stromy. Sborník ROBUST 88 2. Bentley, J. L.: Multidimensional Binary Search Trees Used for Associative Searching. Comm. ACM, vol. 18, pp. 509-517, 1975 3. Berikov, V., Litvinenko, A.: Methods for statistical data analysis with decision trees,
http://www.math.nsc.ru/AP/datamine/eng/decisiontree.htm 4. Loh, W.-Y. and Shih, Y.-S. , Split selection methods for classification trees, Statistica Sinica, vol. 7, 815-840. , 1997 5. Savický, P., Klaschka, J., a Antoch J.: Optimální klasifikační stromy. Sborník ROBUST 2000 6. SPSS-white paper- AnswerTree Algorithm Summary 7. Timofeev R.: Classification and Regression Trees (CART) Theory and Applications, CASE Center of Applied Statistics and Economics, Humboldt University, Berlin, 2004 8. Wilkinson, L.: Tree Structured Data Analysis: AID, CHAID and CART - Sun Valley, ID, Sawtooth/SYSTAT Joint Software Konference,1992 9. Žambochová M.:Použití stromů ve statistice 10. Žambochová, M.: Rozhodovací stromy a mrkd-stromy v analýze dat, Sborník …
7
