Dolování dat Rozhodovací stromy Jan Górecki Název prezentace Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Logolink_OP_VVV_hor_barva_cz Obsah přednášky •Co jsou Rozhodovací stromy •Obecný algoritmus a omezení •Příklad na bankovních datech •Gini index •Převod stromu na pravidla •Prořezávání •Práce s numerickými atributy •Úloha klasifikace objektů do tříd (tedy učení s učitelem). •Top down induction of decision trees (TDIDT) - metoda divide and conquer (rozděl a panuj) •Metoda specializace v prostoru hypotéz – stromů (postup shora dolů, počínaje prázdným stromem). •Cílem je nalézt nějaký strom konsistentní s trénovacími daty. •Dává se přednost menším stromům (Occamova břitva). Rozhodovací stromy idt-1 ID3 (Ross Quinlan) a CART (leo breiman) vznikly nezávisle kolem 1979-80 •TDIDT algoritmus 1.vezmi jeden atribut jako kořen dílčího stromu, 2.rozděl data na podmnožiny podle hodnot tohoto atributu, 3.nepatří-li všechna data v podmnožině do téže třídy, pro tuto podmnožinu opakuj postup od bodu 1. • •Motivace: •Chyba (=1-správnost) pařezu vs chyba stromu s jedním uzlem • Obecný algoritmus pro tvorbu rozhodovacích stromů Jak najít strom, který „pasuje“ na daná data? • • • • • • •Chyba(pařez) = 4/12 Příklad csvukrs 1. krok: Atribut jako kořen dílčího stromu Pro každý atribut (příjem, konto, pohlaví, nezaměstnaný) spočítáme chybu při jeho použití jako kořenového uzlu. Pro výpočet chyby můžeme použít různé metriky, jako je Gini nebo entropie. Pro jednoduchost použijeme chybovou metriku, kde chyba je relativní počet chyb modelu na daných datech. Chyba(příjem) = Chyba(konto) => použijeme Occamovu břitvu – Pro ‘příjem‘ je strom jednodušší (jen 2 větvě) narozdíl od 3 větví pro ‘konto‘ 2. krok: Rozdělíme data podle vybraného atributu a vytvoříme pro něj podstromy T5-IDT-prvni krok Data rozdělená podle atributu „příjem“: ·vysoký příjem: 5x ano (listový uzel, žádná další rozdělení) ·nízký příjem: 3x ano, 4x ne (budeme dále rozdělovat) csvukrs 3. krok: Opakování algoritmu pro podmnožinu s nízkým příjmem prijem konto pohlavi nezamestnany uver nizky nizke muz ne ne nizky nizke zena ano ne nizky stredni muz ano ne nizky stredni zena ano ne nizky stredni muz ne ano nizky vysoke zena ano ano nizky vysoke muz ano ano 3. krok: Opakování algoritmu pro podmnožinu s nízkým příjmem Opakujeme kroky 1 a 2 pro data s nízkým příjmem a zbývajícími atributy (konto, pohlaví, nezaměstnaný). T5-IDT-druhy krok T5-uplny strom •Tedy, tvorba rozhodovacích stromů je založena na prohledávání prostoru stromů: •Shora dolů •Heuristické •Dále: •Jednoduché použití •Má schopnost generalizovat, např. pro [příjem(nízký), konto(nízké), pohlaví(muž), nezaměstnaný(ano)] dává úvěr = ne Shrnutí T5-uplny strom csvukrs Volba atributu (krok 1 algoritmu) entropy p Před zkouškou: p1 = p2 = 0,5 H(p1, p2) = 1 Po zkoušce: p1 = 0, p2 = 1 H(p1, p2) = 0 H(p, 1-p) Pro T=2 je: p1 = p, p2 = 1-p1 = 1 – p, tedy H(p) = H(p, 1-p) Porovnat entropii pařezu s entropií stromu s jedním uzlem Entropie spočtená z dat entropy pano = 8/12 = 2/3 pne = 4/12 = 1/3 p = (2/3, 1/3) Volba atributu (krok 1 algoritmu) Hledáme atribut s minimální hodnotou kritéria (střední entropie H)! Hodnoty zvažovaného vstupního atributu Třídy X Y ano ne suma entropie vysoké 4 0 4 0 střední 2 2 4 1 nízké 2 2 4 1 suma 12 entropy H(konto) = 4/12*H(konto(vysoké)) + 4/12*H(konto(střední)) + 4/12*H(konto(nízké)) = 1/3 * 0 + 1/3 * 1 + 1/3 * 1 = 0.6667 csvukrs Příklad csvukrs Příklad csvukrs •H(konto) = 4/12*H(konto(vysoké)) + 4/12*H(konto(střední)) + 4/12*H(konto(nízké)) = 1/3 * 0 + 1/3 * 1 + 1/3 * 1 = 0.6667 •H(pohlaví) = 6/12*H(pohlaví(muž)) + 6/12*H(pohlaví(žena)) = 1/2 * 0.9183 + 1/2 * 0.9183 = 0.9183 •H(nezaměstnaný) = 6/12*H(nezaměstnaný(ano)) + 6/12*H(nezaměstnaný(ne)) = 1/2 * 1 + 1/2 * 0.6500 = 0.8250 Příklad csvukrs •H(konto) = 2/7*H(konto(vysoké)) + 3/7*H(konto(střední)) + 2/7*H(konto(nízké)) = 2/7 * 0 + 3/7 * 0.9183 + 2/7 * 0 = 0.3935 •H(pohlaví) = 4/7*H(pohlaví(muž)) + 3/7*H(pohlaví(žena)) = 4/7 * 1 + 3/7 * 0.9183 = 0.9650 •H(nezaměstnaný) = 5/7*H(nezaměstnaný(ano)) + 2/7*H(nezaměstnaný(ne)) = 5/7 * 0.9709 + 2/7 * 1 = 0.9792 • Příklad csvukrs •H(pohlaví) = 2/3*H(pohlaví(muž)) + 1/3*H(pohlaví(žena)) = 2/3 * 1 + 1/3 * 0 = 0.6667 •H(nezaměstnaný) = 2/3*H(nezaměstnaný(ano)) + 1/3*H(nezaměstnaný(ne)) = 2/3 * 0 + 1/3 * 0 = 0 • •Pozn: V případě kategoriálních atributů se každý atribut může pro větvení stromu vybrat v jedné větvi nejvýše jednou. Příklad csvukrs Gini index gini Hledáme atribut s minimální hodnotou kritéria (střední Gini index)! Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset. https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity Převod stromů na pravidla idt-2 1.If příjem(vysoký) then úvěr(ano) 2.If příjem(nízký) Ù konto(vysoké) then úvěr(ano) 3.If příjem(nízký) Ù konto(střední) Ù nezaměstnaný(ano) then úvěr(ne) 4.If příjem(nízký) Ù konto(střední) Ù nezaměstnaný(ne) then úvěr(ano) 5.If příjem(nízký) Ù konto(nízké) then úvěr(ne) csvukrs •Důvody: •Bezchybná klasifikace trénovacích dat nezaručuje kvalitní klasifikaci dat testovacích (overfitting) •Úplný strom může být příliš veliký •Redukce stromu, aby v listovém uzlu „převažovaly“ příklady jedné třídy. •pre-pruning – modifikuje se zastavovací kritérium (krok 3 algoritmu) = větvit se nebude pokud počet příkladů v uzlu klesne pod danou hodnotu nebo pokud relativní počet příkladů jedné třídy překročí danou hodnotu •post-pruning – vytvoří se úplný strom, který se následně redukuje – ukazuje se jako úspěšnější než pre-prunning, protože předem lze těžko poznat, jak nastavit kritéria zastavení •Lze kombinovat pre-pruning s post-pruningem. Prořezávání stromů csvukrs 1.Pro každou zvažovanou hodnotu hodnoty Min Leaf Size generuj: a.Jeden strom a spočti chybu klasifikace na celých datech (resubstitution error). b.Pět stromů tak, že data se rozdělí na pět částí a vždy čtyři z nich se použije pro trénování stromu a pátá část se použije změření chyby klasifikace (cross-validated error). Pre-pruning Obrázek generován z sem5.txt 3a) Select Appropriate Tree Depth Post-pruning •Na rozdíl od pre-pruningu, není třeba vytvořit celý strom pro každou volbu parametrů – celý strom se vytvoří pouze jednou a ten se pak ořezává Dvě strategie: Ořezávej větve stromu, které nejvíce snižují chybu na testovacích datech (s využitím křížové validace) dokud: a)je možno chybu ořezáváním snížit - strategie Minimální chyba (Minimum error) b)je chyba menší než minimální chyba (z předchozí strategie) + standardní odchylka minimální chyby - strategie Nejmenší strom (Smallest tree) – tato strategie je schopna produkovat menší stromy než předchozí strategie za cenu mírně vyšší chyby c) • • https://www.displayr.com/machine-learning-pruning-decision-trees/ •Algoritmus pracuje s kategoriálními atributy, numerické je třeba diskretizovat: • 1.off-line v rámci přípravy a předzpracování dat 2. 2.on-line v rámci běhu modifikovaného algoritmu –binarizace na základě entropie • Práce s numerickými atributy csvukrs 1.Seřaď vzestupně hodnoty diskretizovaného atributu A, 2.Pro každou možnou hodnotu dělícího bodu q spočítej entropii H(Aq) 3.Vyber dělící bod q , který dá nejmenší hodnotu H(Aq) 4. 4. 4. Algoritmus diskretizace První člen součtu se týká příkladů, které mají hodnotu atributu menší než θ ( H(A(< θ)) je entropie na těchto příkladech, n(A(<θ))/n je relativní četnost těchto příkladů), druhý člen součtu se analogicky týká příkladů, které mají hodnotu atributu větší než θ. csvukrs Příklad 1. H(konto22500) = 3/12*H(konto(<22500)) + 9/12*H(konto(>22500)) = 1/4 * 0.9183 + 3/4 * 0.5640 = 0.6526 H(konto40000) = 5/12*H(konto(<40000)) + 7/12*H(konto(>40000)) = 5/12 * 0.9706 + 7/12 * 0.5917 = 0.7497 H(konto55000) = 6/12*H(konto(<55000)) + 6/12*H(konto(>55000)) = 1/2 * 1 + 1/2 * 0.6500 = 0.8250 H(konto75000) = 7/12*H(konto(<75000)) + 5/12*H(konto(>75000)) = 7/12 * 0.9852 + 5/2 * 0 = 0.5747 csvukrs Příklad idt-4 csvukrs •na rozdíl od kategoriálních atributů se mohou v jedné větvi numerické atributy opakovat • • • • • Kategoriální vs numerické atributy csvukrs •Úloha odhadu hodnoty nějakého numerického atributu. • •Volba atributu (krok 1): •kritérium redukce směrodatné odchylky • • • • • Regresní stromy idt-rt csvukrs •příklady jsou reprezentovány hodnotami atributů, •úkolem je klasifikovat příklady do konečného (malého) počtu tříd, •trénovací data mohou být zatížena šumem, •trénovací data mohou obsahovat chybějící hodnoty Použití rozhodovacích stromů csvukrs •Rozhodovací stromy dělí prostor atributů na (mnoharozměrné) hranoly rovnoběžné s osami souřadné soustavy: • • • • • • Vyjadřovací síla rozhodovacích stromů silasymb idt-4 csvukrs Děkuji za pozornost Některé snímky převzaty od: prof. Ing. Petr Berka, CSc. berka@vse.cz