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. •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 csvukrs •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. • •Omezení algoritmu: 1.Jen kategorické atributy 2.Data bez šumu (pro stejné kombinace hodnot vstupních atributů je stejná třida) Obecný algoritmus pro tvorbu rozhodovacích stromů csvukrs Volba atributu (krok 1 algoritmu) entropy Entropie csvukrs 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 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 Příklad T5-IDT-prvni krok 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 Příklad T5-IDT-druhy krok 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 Příklad T5-uplny strom csvukrs •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 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