Pokročilé neparametrické metody Rozhodovací stromy
Klára Komprdová
evropský	
sociální	
r?
fond V ČR EVROPSKÁ UNIE
MINISTERSTVO ŠKOLSTVÍ. MLÁDEŽE A TĚLOVÝCHOVY
j l Z
OP Vzdělávání pro konkurenceschopnost
•y -P,
m
if ■i
i
INVESTICE DO ROZVOJE VZDELÁVANÍ
Pokročilé neparametrické metody J
Stromy typu CART
Pokročilé neparametrické metody
Strom typu CART
o Breiman et al. 1984
o vhodné pro kategoriální i regresní úlohy
o rostou na základě rekurzivního binárního dělení
kořen
X2 ^ a1
Pokročilé neparametrické metody
Jak roste strom CART?
o pozorování rozdělena do dvou dceřiných uzlů, na základě hodnoty a prediktoru X, které jsou dále děleny opět binárně na další uzly
o hodnoty vysvětlujících proměnných, použité při větvení, rozdělují daný prostor na sadu pravoúhelníků a pak pro každý z nich fitují
jednoduchý model
Pokročilé neparametrické metody   f BA
Grafické znázornění stromu CAR!
o rozdělení pozorování do kategorií A a B závisle proměnné Y s použitím dvou spojitých prediktorů X,, X2
l j
Pokročilé neparametrické metody
Jak na to?
(Tibshirani et. al, 2001). Pokročilé neparametrické metody
Jak najít správné rozdělení?
o existuje mnoho algoritmů, jak vybírat proměnné a hranice podle kterých bude probíhat dělení datového souboru
o hlavní princip: snažíme se najít takové rozdělení závisle proměnné Y prediktorem X, aby hodnoty proměnné Y byly uvnitř uzlu co nejhomogennější a zároveň mezi uzly co nejrozdílnější
o který prediktor (a jeho hodnota) nám zajistí nejlepší rozdělení zjistíme pomocí tzv. kriteriální statistiky (spliting criterium), která určuje homogenitu uzlu
o existuje několik měření kriteriálních statistik, které se navíc liší podle toho, zda se jedná o klasifikační nebo regresní strom
o nejčastěji používanými měřeními pro stromy typu CART: Kritérium minima kvadratické chyby , Gini index, Entropie a klasifikační chyba
Pokročilé neparametrické metody   f BA
Kriteriální statistika pro regresní stromy
o Předpokládejme, že máme strom rozdělený do určitého počtu terminálních uzlů a odpověď závisle proměnné modelujeme jako konstantu pro každý terminálni uzel.
o Pokud použijeme kritérium, které minimalizuje střední kvadratickou chybu, nejlepším odhadem bude průměr.
o Kritérium Kritérium minima kvadratické chyby (Least Square Deviation LSD):
kde Nt je počet pozorování v uzlu t a yj(t) jsou hodnoty závisle proměnné v uzlu t
Pokročilé neparametrické metody
Kriteriální statistika pro klasifikační stromy
Gini index:
G/ = 2>*(l-/Ü = l-2>
2 tc
c=\
c=\
Entropie:
Klasifikační chyba:
H=-Y, Ptc l0g2 Ptc
c=l
ME = l-max{/?řc}
kde ptc je podíl pozorování y, s kategorií c v uzlu t z celkového počtu všech pozorování y, v tomto uzlu neboli pravděpodobnost kategorie c v uzlu t.
• Gini index - nejčastěji používané měření pro klasifikační stromy - hodnota Giny indexu se rovná nule, pokud je v konečném uzlu pouze jediná třída a dosahuje maxima, pokud je v konečném uzlu v každé třídě stejný počet pozorování.
Impurity measurement
Pokročilé neparametrické metody IBA.
Celkové hodnoty indexů pro rozdělení
o Ve chvíli, kdy dojde k rozdělení uzlu na dva dceřiné uzly, je Gl spočítán pro každý dceřiný uzel.
o Hodnota Gl indexů jednotlivých dceřiných uzlů je vážena velikostí dceřiného uzlu.
o Glcelk = součet Gl (i) dceřiných uzlů, které jsou vynásobeny příslušným podílem pozorování v daném dceřiném uzlu z celkového počtu pozorování v původním mateřském uzlu.
kde K je počet dceřiných uzlů (v případě binárního stromu se K= 2), Nt'\e počet pozorování v mateřském uzlu ta A/Jsou počty v dceřiných uzlech.
1=1
Pokročilé neparametrické metody
Stejně pro další indexy...Entropie
o Celková entropie:
o Entropie dosahuje maxima, pokud jsou jednotlivé kategorie proměnné Y rovnoměrně zastoupeny v uzlech a minima pokud pozorování v uzlu náležejí pouze do jediné kategorie.
Entropie je často používána v algoritmu C4.5.
o GAIN (information gain, informační zisk) a měří pokles v entropii.
GAINcelk =H-
Pokročilé neparametrické metody
Klasifikační chyba
Celková klasifikační chyba pro dané dělení = vážený součet ME v dceřiných uzlech, o   ME je podíl chybně klasifikovaných pozorování o 1 - ME je celková přesnost stromu = podíl správně klasifikovaných pozorování
o Klasifikační chyba je obvykle používána k finálnímu měření přesnosti klasifikačního stromu, proto je logické její použití jako kriteriální statistiky
preferovány jiné indexy —> Entropie a Gini index jsou mnohem více citlivé na změny v pravděpodobnostech uzlů než M E
Pokročilé neparametrické metody
Příklad
Di
Pokročilé neparametrické metody   f BA
uzel   nA    nB     pA     pB     pt       Gini = 1 - p2A - p2B pt*Gini
CD 1
celkový
l
CD
celkový
uzel   nA     nB     pA     pB     pt      ME = 1 - max{pA, p J pt*ME
CD
'i
celkový
*3
CD
'/i
celkový
Pokročilé neparametrické metody IBA.
Obecný průběh kriteriálních statistik pro rozdělení do dvou kategorií A a 8 závisle proměnné Yjako funkce podílu první kategorie pA.
0        0.1        0.2       0.3       0.4       0.5       0.6       0.7       0.8       0.9 1
Pa
Všechny kriteriální statistiky dosahují svého maxima, pokud je kategorie rovnoměrně rozmístěna mezi uzly (pA = 0,5) a minima, pokud je zastoupena pouze jedna kategorie (pA = 1 nebo pA = 0 pB = 1).
(Tibshirani et. al, 2001). Pokročilé neparametrické metody
Výsledná hodnota predikce - regresní strom
o Každému objektu z koncových listů je přiřazena hodnota, kterou vypočteme jako aritmetický průměr hodnot všech objektů v příslušném listu.
o Výsledný odhad hodnot závisle proměnné tak bude nabývat pouze tn hodnot, kde tn je počet terminálních uzlů
o Další možností je vytvořit pro jednotlivé listy regresní modely
x Nemusí však být dostatečný počet dat v koncové uzlu
x Výsledný vztah nelze popsat regresí (není zde závislost, vzorky v terminálním uzlu nesplňují předpoklady regrese)
x Metoda začne nabývat na složitosti
Pokročilé neparametrické metody
Příklad - ozón
temperature< 82.5
windí-=6.6
windH=
10.6
temperature< 77.5
18.47 n=49
r~
13 n=4
48.71 n=7
windí-=4.3
radiatipn< 82
92.5 n=4
temperat[jre< 87.5
6^5~ 88!23 n=10 n=13
112 n=4
—I
36.75
n=20
Pokročilé neparametrické metody
Příklad: Ukázka regresního stromu
Závislost spotřeby plynu na venkovní teplotě
Přiřazení hodnoty terminálnímu uzlu
klasifikační strom - každému uzlu, včetně kořenového, je přiřazena výsledná kategorie závisle proměnné
výsledná kategorie - má v daném uzlu největší zastoupení
nové pozorování je klasifikováno podle kategorie uzlu, do kterého je stromem zařazeno
může se stát, že po rozdělení do dvou terminálních uzlů bude oběma uzlům přiřazena stejná kategorie, zejména je-li podíl kategorií proměnné Y nevyrovnaný —> výhodu mají kategorie, které jsou u proměnné Y více zastoupeny
• možnost použít vážení jednotlivých kategorií
Pokročilé neparametrické metody
Příklad hurikány
o Atlantické hurikány jsou klasifikovány podle ovlivnění tropickými (Trop) nebo baroklinickými (Baro) jevy.
o Tropická cyklona při vývoji prochází třemi stádii: tropická deprese —► tropická bouře —► hurikán.
o K dispozici je šest prediktorů, na základě kterých by mělo být možné tyto dvě třídy hurikánů odlišit.
o Jedná se o datum, zeměpisnou šířku a délku tropické deprese (LATDEPR, LONDEPR) (První stádium při vzniku hurikánu) a datum, zeměpisnou šířku a délku, kdy bouře dosáhla statutu hurikánu (LATHUR, LONHUR).
Pokročilé neparametrické metody
Příklad hurikány
BARO TROP
ID = 1 N=209 BARO
109 100
<= 23.500000
ID =2		N =89
TROP		
	80	
9		
> 23.500000
ID=3			N = 120
		BARO	
			
LATDEPR
<= 19.850000
> 19.850000
ID = 12 N=41 BARO
ID=13 N=79 BARO
77
	<= 17.350000			> 17.350000		
ID = 14		N=26		ID=15		N = 15
	BARO			TROP		
	20				12	
		6		3		
						
Co vše můžeme zjistit ze stromu
Jak interpretovat strom ?
Jaká je celková přesnost stromu ?
Která ze dvou skupin je lépe klasifikována?
Které parametry jsou významné ?
Pokročilé neparametrické metody
Rozložení hurikánů BARO a TROP v období jejich výskytů a podél zeměpisné šířky vzniku hurikánů.
Pokročilé neparametrické metody
Algoritmus růstu stromu CART
Rozděl soubor na trénovací a testovací —► poměr se určuje na základě počtu pozorování a účelu studie
Najdi nejlepší rozdělení každého z prediktoru: Pro spojité proměnné
o    seřaď hodnoty každého prediktoru od nejmenší po největší.
o    Projdi všechny hodnoty prediktoru X a spočítej kriteriální statistiku všech možných rozdělení proměnné Y na dva potenciální dceřiné uzly.
o    Pokud je dělicí hodnota a prediktoru X větší nebo rovna hodnotě xh pozorování y, náleží do levého uzlu, jinak do pravého (popřípadě naopak).
o    Hodnota a, pro kterou je kriteriální statistika minimální, je vybrána jako nejlepší možné dělení závisle proměnné Y pomocí daného prediktoru.
o    Pro každý prediktor tak získáme jednu hodnotu (nejlepší potenciální rozdělení) kriteriální statistiky —► Následně je vybrán prediktor s nejnižší hodnotou kriteriální statistiky a hodnota a je použita k rozdělení souboru (hodnot y,) do dvou dceřiných uzlů.
Pro kategoriální prediktor
o    projdi všechny možné kombinace, tvořené jednotlivými kategoriemi prediktoru a hodnot nebo kategorií závisle proměnné -^použij dělení s nejnižší hodnotou kriteriální statistiky.
Rozděl soubor na dva dceřiné uzly t, a t2 podle hodnoty prediktoru vybrané v kroku 2.
Opakuj krok 2 a 3, dokud se dělení nezastaví na předem definované hodnotě (dokud není dosaženo některého z pravidel pro zastavení růstu stromu). Protože vybíráme vždy z celé množiny prediktoru, může být stejný prediktor použit ve stromě vícekrát.
Použij testovací soubor k ověření vhodné velikosti stromu, a pokud je strom příliš velký, prořež strom.
Pokročilé neparametrické metody IBA
Pravidla pro zastavení růstu stromu (stopping rules)
o Strom nemůže růst donekonečna —> maximální velikost je dána velikostí souboru
o Strom se zastaví sám v těchto případech:
• terminálni uzel obsahuje pouze jedno pozorování;
• všechna pozorování v uzlu mají stejnou hodnotu všech prediktoru;
• všechna pozorování v uzlu mají stejnou hodnotu závisle proměnné.
o Strom můžeme v růstu omezit nastavením některých parametrů a k dalšímu rozdělení nedochází, pokud je dosaženo zadaných hodnot:
• maximální počet větvení daného stromu;
• maximální počet pozorování v koncovém uzlu;
• frakce pozorování v uzlu, která již nemůže být oddělena;
• velikosti chyby v potenciálních dceřiných uzlech - například uzel se nerozdělí, pokud střední kvadratická chyba (MSE) nebo procento nesprávně klasifikovaných vzorku v důsledku rozdělení překročí určitou hranici.
Pokročilé neparametrické metody
Stromy typu CART -pokračování
Pokročilé neparametrické metody IBA.
Výběr optimálního stromu
o strom bude mít velikost podle námi zvolených pravidel (nebo pravidel defaultně nastavených v softwaru), která mohou být subjektivní
o Jak tedy poznat, strom správné velikosti?
• rozdělení souboru na trénovací a testovací
• na trénovacím souboru se strom učí a roste
• testovací soubor není při tvorbě stromu vůbec použit a slouží pouze k jeho otestování
o nedoučený (underfitting) strom —> je příliš jednoduchý a chyba na testovacím i trénovací souboru bude velká
o přetrénovaný (overíitting) strom —> je zbytečně složitý, trénovací chyba je většinou malá, ale testovací velká
!Je tedy třeba najít vhodný kompromis!
Pokročilé neparametrické metody   f BA
Rozdíl ve velikosti chyby mezi testovacím a trénovacím souborem při různé velikosti stromu, dané počtem terminálních uzlů
030
025
0.20
tu
% 0.15
O 10
0.05
0.00
-e- trénovací soubor ~@- testovací soubor
,-0
.O
O   Q   Q o
—L_l_
_l_J_
6 B 10 12 počet termináhícri uztů
14
16
Nejprve byla spočítána chyba (procento chybně zaklasifikovaných pozorování) na testovacím a trénovacím souboru pro strom s 16 terminálními uzly. Postupně bylo vždy zpětně odstraněno poslední rozdělení uzlů, čímž se snížil počet terminálních uzlů o jedna. Pro takto zmenšený strom byla opět spočítána chyba pro oba soubory. Takto se postupně strom zmenšoval, až zbyl pouze jeden uzel-kořen
jsiromu.
Pokročilé neparametrické metody IBA.
Příklad přetrénování stromu I
o kvůli odlehlé hodnotě
i j
Pokročilé neparametrické metody
Příklad přetrénování stromu II
o z důvodu nedostatečného počtu trénovacích dat
X,
Pokročilé neparametrické metody IBA.
Velikost stromu
Příliš velký strom
o Může být „přeučený", tj. může být příliš specializovaný na datový soubor, který se použil pro jeho konstrukci.
o Pokud ho použijeme pro klasifikaci „neznámých" případu, nemusí být pnhs uspesný.
o Neplatí tedy, že čím je strom větší, tím je lepší.
o Dobře naučený strom nepopisuje každý konkrétní případ, spíše by měl popisovat obecnější závislosti, které se v datech vyskytují.
Příliš malý strom
o Nemusí postihnout strukturu dat
Pokročilé neparametrické metody
Prořezávání stromu
o parametrem, který určuje složitost stromu, je jeho velikost.
o U CART začínáme s „přerostlým", příliš detailně větveným stromem. Tento strom následně redukujeme pomocí některé z metod
Prořezávání (pruning)
Zmenšování, scvrkávání se (shrinking) - metoda pro regresní strom
K určení optimální velikosti stromu —> kritérium složitosti stromu (cost-complexity criterium)
Pokročilé neparametrické metody
Kritérium složitosti stromu
Mějme strom T0. Prořezáním určitého počtu koncových uzlů dostaneme strom Tv
Cena jednoduššího stromu (cost-complexity criterium):
kde |je počet terminálních uzlů stromu a DT^ je deviance stromu. Parametr a > 0 vyjadruje kompromis mezi velikostí stromu a jeho vyčerpanou variabilitou. Hledáme tedy, pro každé a, takový strom , který minimalizuje Ca(T). K určení odhadu a se používá krosvalidace
Ca{Tl)=DTl+aTl
Pokročilé neparametrické metody
Křížové ověřování (krosvalidace)
o Křížová validace patří mezi validační techniky
o Pozorování jsou rozdělena do k nezávislých podsouborů
o Jeden podsoubor se použije pro testování (pozorování nejsou použita při tvorbě modelu) všech ostatních /c-1 skupin pro tvorbu modelu —> je tedy vytvořeno k modelů otestovaných na k testovacích souborech
o Z výsledků testovacích souborů můžeme určit stabilitu metody (spočítat např. průměr a směrodatnou odchylku přesnosti na testovacím souboru) a její predikční schopnost.
o Stromy jsou obecně velmi nestabilní metody —> i malá změna v datech může způsobit změny v rozhodovacích pravidlech a můžeme získat odlišný strom s jinou přesností.
• Jak velká je tato variabilita, zjistíme z rozsahu hodnot přesnosti stromu pro jednotlivé testovací soubory.
o Výhoda křížové validace spočívá v použití nezávislého datového souboru pro testování - každé pozorování je pro testování použito právě jedenkrát
Pokročilé neparametrické metody   f BA
Křížové ověřování (krosvalidace)
k=1 k=2 k=Z..................k=10
Trénovací soubor
□
i        i i
*-►<
i i i
Pokročilé neparametrické metody IBA.
Výběr optimálního stromu
o Pomocí křížové validace vybereme takové a, aby měl strom co největší přesnost, ale zároveň byl rozdíl v chybě mezi testovacím a trénovacím souborem co nejmenší
velké a složitost malé a
Pokročilé neparametrické metody
Příklad - ozón
wind>=6.6
temperat jre< 77.5
18 47 n=49
r~
13 n=4
radiati >n< 82
—I
36.75
n=20
temperature< 82.5
92.5 n=4
48 71 n=7
wind> = 10.6
wind>=4.3
temperat[jre< 87.5
ô/TŠ 88:23 n=10 n=13
112 n=4
Pokročilé neparametrické metody IBA
Měření přesnosti stromu
o Označme e(f) chybu na trénovacím souboru (re-substitution errors) a ď(f) chybu na testovacím souboru (generalization errors).
o Při použití pouze trénovacího souboru lze získat dva odhady celkové chyby stromu.
• optimistický odhad, kdy předpokládáme, že chyba trénovacího souboru se rovná chybě na testovacím souboru e\t) = e{ť)
• pesimistický odhad, kdy je pro každý terminálni uzel e'(ř) = (e(ř)+0,5)
o Celková chyba je tedy: e\T) = e(7) + N x 0,5 , kde N je počet terminálních uzlů
Pokročilé neparametrické metody JfiA
Měření přesnosti stromu II
o Mějme soubor obsahující 100 měření. Pro strom s 20 terminálními uzly a 10 chybně zařazenými pozorováními z trénovacího souboru je:
• optimistický odhad chyby = 10/100 = 10%
• pesimistický odhad chyb = (10 + 20x0,5)/100 = 20%.
o Chyba na trénovacím souboru však není dobrým ukazatelem, jak dobře bude strom klasifikovat/predikovat nová data.
o Proto se k odhadu celkové (obecné) chyby stromu používá převážně testovací soubor.
Pokročilé neparametrické metody   f BA
Matice záměn (confusion matrix)
pozorované
ano
ne
celkem
predikované			
ano	a (TP)	b (FP, chyba I. druhu)	a+b
ne	c (FN, chyba II. druhu)	d (TN)	c+d
celkem	a+c	b+d	n
			
	Sensitivita, FNR	Specificita, FPR	
PPV
NPV
a = pravdivě pozitivní (TP- true positive) b = falešně pozitivní (FP - falše positive) c = falešně negativní (FN - falše negative) d = pravdivě negativní (TN - true negative)
Senzitivita-podíl (procento) správně zařazených pozitivních případů, ze všech případů, které byly před povezeny jako pozitivní (např. Procento lokalit kde se taxon vyskytl, ze všech lokalit predikovaných jako výskyty)
specificita - podíl správně zařazených negativních případů, ze všech případů předpovězených jako negativní (např. procento lokalit kde se taxon nevyskytl, ze všech lokalit predikovaných jako nevýskyt).
Pokročilé neparametrické metody
Měření přesnosti klasifikačního stromu
o Celková správnost, (Overall accuracy, Correct classification rate):
OA=(a+d)/n
o Klasifikační chyba:
MR = (b+c)/n
o Cohenovo kappa:
Kp= (OA-EA)/(1-EA),
kde EA = ((a+c)(a+b)+(b+d)(c+d))/n2
o Na testovacím souboru, použití krosvalidačních technik pro zjištění obecnosti a stability stromu
Pokročilé neparametrické metody IBA
Měření přesnosti klasifikačního stromu II
o Tato měření však nezohledňují různou velikost skupin ani rozdílnost oproti náhodnému výsledku, a proto může snadno dojít k nadhodnocení nebo naopak podhodnocení kvality modelu.
o Mějme příklad klasifikačního stromu pro závisle proměnnou se dvěma kategoriemi a počtem pozorování v jednotlivých kategoriích A = 100 a B = 10. Počet správně klasifikovaných pozorování v jednotlivých kategoriích je následující A = 100 a B = 0.
O A = 100/110=0,91
o Procento správně klasifikovaných pozorování by v tomto případě bylo zhruba 91% —> takový strom nám není k užitku, protože nedokázal kategorie odlišit a všechna pozorování v kategorii C klasifikoval jako kategorii A.
Pokročilé neparametrické metody IBA
Měření přesnosti klasifikačního stromu III
o Korekci na velikost kategorií lze však provést jednoduchou úpravou:
kde J je celkový počet kategorií, npc je počet správně klasifikovaných pozorování v kategorii c a nc je počet všech pozorování v kategorii c.
o Pro náš příklad se pak celková adjustovaná správnost stromu rovná:
1 r 100   0 } 100 + 10
v
= 0,5
J
o Celková správnost se používá především pro srovnání s ostatními klasifikačními metodami nebo pro výběr vhodného stromu, v praxi nás však častěji zajímá procento správně klasifikovaných pozorování
pro každou kategorii.
Pokročilé neparametrické metody J
Určení přesnosti regresního stromu
o U regresního stromu je přesnost, určována stejně jako v lineární regresi, pomocí koeficientu determinace R2.
o Koeficient determinace je obecně definován jako podíl variability závislé proměnné Y, vysvětlené modelem k celkové variabilitě proměnné Y.
o V našem případě jde o variabilitu vysvětlenou stromem
2   variabilita _vy světlena _modelem        residualni _variabilita
K —-— 1--— 1--,
celková  variabilita  Y celková  variabilita  Y        vv _\2
- - l^Vi-y)
o kde ýj = je průměr v příslušných terminálních uzlech a odchylka od průměru uzlu ŕ je spočítána vždy pro pozorování   zařazené do tohoto terminálního uzlu.
o Koeficient determinace nabývá hodnot od 0 do 1. Při hodnotě R2 = 1 jsme vysvětlili veškerou variabilitu pomocí stromu a predikované hodnoty ý, se shodují s pozorovanými hodnotami yr
o Je opět možné spočítat chybu regresního stromu pro trénovací soubor e\t) = 1 - R2tren a testovací soubor e(f) = 1 - R2test
Pokročilé neparametrické metody IBA.
Příklad - ozón
temperature< 82.5
windí-=6.6
windH=
10.6
temperature< 77.5
18.47 n=49
r~
13 n=4
48.71 n=7
windí-=4.3
radiatipn< 82
92.5 n=4
temperat[jre< 87.5
6^5~ 88!23 n=10 n=13
112 n=4
—I
36.75
n=20
Pokročilé neparametrické metody
Je strom vytvořený na základě prediktorů s nejnižší kriteriální statistikou opravdu
nejpřesnější?
Pokročilé neparametrické metody
Primární, zástupné a kompetitivní proměnné
Primární proměnná dosahuje nejlepšího dělení daného uzlu a je použita jako pravidlo ve stromě
Může se stát, že proměnná, která je téměř stejně vhodná (kriteriální statistika má podobnou hodnotu) jako vybraná primární proměnná, zůstane skrytá, i když může mít větší interpretační hodnotu —> takovéto proměnné se nazývají zástupné (surrogates) a kompetitivní proměnné.
Zástupné proměnné nesou podobnou informaci jako primární proměnná a většinou jsou s ní korelované. Pro každý uzel lze zjistit, nakolik rozdělují pozorování v dceřiných uzlech stejně jako primární proměnná.
Kompetitivní proměnná rozděluje daný uzel odlišně než primární
Na základě hodnot kriteriální statistiky se tak v případě absence primární proměnné rozdělí uzel podle kompetitivní nebo zástupné proměnné.
Je tedy vybrán jiný prediktor s další nejlepší hodnotou kriteriální statistiky.
Velký význam pro interpretaci
Pokročilé neparametrické metody
Určení primární, kompetitivní a zástupné proměnné při rozdělení pozorování kategorií A, B, C do dvou terminálních uzlů
A= 100, B = 100, c = 100 f
proměnná X	kategorie	uzel 1	uzel		2
	A	90	10		
primární	B	90	10		
					
	C	20		80	
	A	80	20		
zástupná	B	85	15		
					
	C	25		75	
	A	80		20	
kompetitivní	B	20	80		
	C	10	90		
Pokročilé neparametrické metody
Příklad hurikány
BARO TROP
<= 23.500000
ID =2		N =89
TROP		
	80	
9		
ID = 1 N=209 BARO
109 100
> 23.500000
ID=3			N = 120
		BARO	
			
LATDEPR
<= 19.850000
> 19.850000
ID = 12 N=41 BARO
ID=13 N=79 BARO
77
	<= 17.350000			> 17.350000		
ID = 14		N=26		ID=15		N = 15
	BARO			TROP		
	20				12	
		6		3		
						
Co vše můžeme zjistit ze stromu
Jak interpretovat strom ?
Jaká je celková přesnost stromu ?
Která ze dvou skupin je lépe klasifikována?
Které parametry jsou významné ?
Pokročilé neparametrické metody
Příklad hurikány
0.6
0.5
0.4
o 0.3
0.2
0.1
0.0
Cost sequence Dependent variable: CLASS
2 3 Tree number
Má strom správnou velikost?
					
					
					
					
(	)-—-<				
--------------------c					
Resub. cost CV cost
Pokročilé neparametrické metody
Příklad
o atlantické hurikány BARO a TROP jsme schopni klasifikovat v obou případech s vysokou přesností
# OABARO = 97/1 09 = °>89 3 OATROP = 92/1 00 = °-92
o V tomto případě by se jednalo o optimistický odhad chyby
• e'(ř) = 1- OAtren na trénovacím souboru
o Stejný výpočet bychom však mohli provést pro pozorování z testovacího souboru a získat objektivnější měření chyby
. e'(t) = 1-OAtBSt
Pokročilé neparametrické metody
Výhody stromů
Snadné grafické znázornění - jednoduchá interpretace
Neklade žádné podmínky na typ rozdělení ©   Algoritmy tvorby stromu jsou odolné vůči odlehlým hodnotám ©   Možno použít korelované proměnné ©    Prediktory mohou být všech typu
©   Výsledky přesnosti stromu lze snadno porovnat s výsledky jiných modelů
©   rychlá metoda při klasifikaci nových případů
©   Metoda je vhodná pro klasifikaci i regresi (pro regresi s jistými omezeními)
Pokročilé neparametrické metody
Klasifikační (rozhodovací) strom Nevýhody
® Nestabilita - tvar stromu velmi závisí na datech, malá změna v datech způsobí změny v rozhodovacích pravidlech uvnitř uzlů
+ změna výsledných klasifikací/predikcí
• Vzhledem k nestabilitě je nutná opatrnost při interpretaci.
• Řešení: např. Bagging - kombinace většího počtu stromů, aby se minimalizovala jejich variabilita (bude vysvětleno později viz. klasifikační lesy)
® měření přesnosti stromu (accuracý) je výrazně závislé na krosvalidačním mechanizmu, selekčních kritériích a výběru mechanizmu pro minimalizaci chyby stromu
® nevhodné pro malý počet vzorků a velký počet tříd
® vytváření stromů vyžaduje zkušenosti
Pokročilé neparametrické metody
Algoritmy učení
Je celá řada algoritmů pro růst stromu
obecně nelze říci, který z algoritmů je lepší, záleží na řešeném problému výsledkem je strom, který se však liší obsahem uzlů i jejich počtem
ID3 (Quinlan 1979)
CHAID - Chi-squared Automatic Interaction Detector (Kass,1980)
• CART (Breiman et al. 1984)
• Assistant (Cestnik et al. 1987)
MARS - Multivariate Adaptive Regression Splines (Friedman, 1991) RETIS (Karalič 1992) - pro regresní stromy
• C4.5 (Quinlan 1993)
QUEST - Quick, Unbiased and Efficient Statistical Tree (Loh & Shin, 1997)
• C5 (Quinlan 1997)
• PRIM - Patient Rule Induction Method (Friedman & Fisher, 1999)
• Stromy ve Wece (Frank 2000) Stromy v Orange (Demšar, Župan 2000)
Pokročilé neparametrické metody
Příklad III: Regresní strom CART
o V tomto příkladu budeme sledovat závislost denního měření koncentrace ozónu (ppb) na rychlosti větru (míle/h), teplotě vzduchu (denní maximum ve stupních Fahrenheita) a intenzitě slunečního záření (cal/cm2) v New Yorku. Soubor obsahuje celkem 111 měření, která proběhla od května do září v roce 1973.
o Přízemní ozón je součástí tzv. fotochemického smogu, který se vyskytuje v místech s intenzivní automobilovou dopravou. Jeho původcem jsou oxidy dusíku emitované jako součást spalin ze spalovacích motorů. Působením slunečního záření se tyto oxidy štěpí a vzniklé radikály reagují s kyslíkem za vzniku ozónu. Jeho zvýšené koncentrace můžeme tedy očekávat v letních měsících při vyšších teplotách. Určitý nárůst koncentrací ozónu lze ale očekávat i za slunečného počasí v chladnějších měsících, pokud jsou zhoršené rozptylové podmínky. Podíváme se, zdali jsou tato očekávání ověřitelná pomocí výše zmíněných měření.
Pokročilé neparametrické metody