Regresní a klasifikační stromy (rozhodovací stromy , Decision Trees)
Regresní a klasifikační stromy (Regression , classification trees)
o   Jsou nejméně formální a nejméně parametrickou skupinou statistických modelů
o   Model - popisuje vzájemné vztahy mezi mezi pozorovanými veličinami
o   Další příklady modelů: Lineární regresní model, Zobecněný regresní model(logistická regrese, poissonovská regrese), Neuronové sítě atd.
Struktura stromu
uzel (nodum)
Kořen (root)
uzel (nodum)
uzel (nodum)
list (leaf)
list (leaf)
list (leaf)
list (leaf)
list (leaf)
list (leaf)
list (leaf)
IBA
Struktura stromu
o   Stromy se skládají z: kořene, uzlů - neterminálních uzlů, listů -terminálních uzlů.
o   V každém neterminálním uzlu se strom větví
o   Binární stromy - z jednoho uzlu vyrůstají právě dvě větve o   Nebinární stromy - z jednoho uzlu vyrůstají dvě a více větví
Typy Stromů
o   Klasifikační (rozhodovací) strom - modelujeme závislost kategoriální závisle proměnné na jedné či více nezávislých proměnných , prediktorech (kategoriálních, spojitých)
o   Regresní strom - modelujeme závislost spojité závisle proměnné na jedné či více nezávislých proměnných, prediktorech (kategoriálních, spojitých)
Ülohy - příklady
Klasifikační:
Spamy - určení, který doručený e-mail je spam a který není spam.
Kosatce - třídění kostaců do jednotlivých druhů na základě velikosti jejich korunních a kališních plátků
Regresní:
Ozón - modelování množství ozonu v závislosti na nadmořské výšce, teplotě a rychlosti větru
Klasifikační stromy
Co je to klasifikační strom?
o   Patří mezi neparametrické metody (metody strojového učení, machine learning)
o   Klasifikují vzorky do konečného (malého) předem daného počtu tříd
o   Je to posloupnost rozhodnutí, jejímž výsledkem je zařazení objektu do jedné ze skupin na základě vlastnosti zkoumaného objektu
o   V každém uzlu j"e určena veličina, podle které dělíme datový soubor a hranice, která určuje, kde se dělení má provést (je-li veličina spojitá)
o   Kořen obsahuje celý datový soubor
o   Z každého uzlu vyrůstají dvě (binární strom) nebo více větví
o   Každý list představuje některou ze skupin (úrovně kategoriální závisle proměnné).....
o   Příklad: Botanický klíč
Jinak řečeno....
Každé pozorování patří do jedné z tříd C1,... ,Ck, K>2
o   Pozorování podle hodnot prediktoru postupuje od kořenového uzlu přes větvení v neterminálních uzlech k některému terminálnímu uzlu (listu)
o   Množina všech listů určuje disjunktní rozklad prostoru hodnot prediktoru
o   Terminálnímu uzlu a zároveň pozorováním, která do něj patří je přiřazena některá z tříd C1,... ,Ck.
Botanický klíč - určení skupin
Klíč ke Květeně České republiky, str.48
Rostliny
Rozmnoženi
výtrusy
ANO
Kapradorosty
jehlice, rozmnozonaci organy vsisce
"TOT
nahos ernenne
ANO
krytos emnne jednodelozne
ANO
krytos ernenne dvoudelozne vice pestiku
ANO
krytos ernenne dvoudelozne lpestik atd.
ANO
krytos ernenne
dvoudelozne
lpestik, volne C listky
krytos emnne
dvoudelozne
lpestik, srostle Clistky
IRIS data
o   150 případů, vždy 50 případů ve skupině
o  3 skupiny - druhy kosatc Setosa, Versicolour, Virginica
o 4 prediktory: sepal length sepal width, petal length, petal width
o  Zdroj příkladu: Yu-Shan Shi h - Tree-structured methods
Boxplots of iris data
		Petal Length		m "i _ o		Petal Width		
r- -		I	-j-		4-	_,_	^—	
								
			I					
			—I					
LI								
		I—   —I				1             '             1		
		a						
■■"■ r-l   -								
_	6							
	I setosa	I versicolor	I virginica		i setosa	1 versicolor	i virginica	
		Sepal Length								Sepal Width			
li i'-					|		-i t o pi		1 1				-J-
in			1										
					i				1--------1--------		i		-------------1
li				i				c					
li			i										1 l
	1												
li -t										!			
	1 setosa		1 versicolor		1 virginica				[ setosa		i versicolor		1 virginica
IRIS data - stromy
Classification tree for Iris data
Versicolor       WgiiKd
Iris data
í  í
D    00 O       o 0000    0 0 0
í í           o
oooo o       o
0000                       o   o
00 o               o
00 O     00 o o   o
o
............e "ff"" "cr"
O   000 000 O        O 000
o    ooraooo 00 o o   c
00 O O O   00
("l
c o s 000 í 000 O
o oooooo Ů
O    00
-
T
T
-
3                   4                   5
Petal Length
Klasifikační (rozhodovací) strom Výhody
o   Snadné grafické znázornění
o   Neklade žádné podmínky na typ rozdělení (lineární regresní model - požadaveM normality reziduí)
o   Algoritmy tvorby stromu jsou odolné vůči odlehlým hodnotám
o   trénovací data mohou obsahovat chybějící hodnoty
o   dokáží zachytit nelineární vztahy mezi proměnnými a vysvětlující proměnnou
o    lze použít pro korelované proměnné
IBA
Klasifikační (rozhodovací) strom Nevýhody
o   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í o   Vzhledem k nestabilitě je nutná opatrnost při interpretaci.
o   Řešení: např. Bagging - kombinace více stromů dohromady, aby se minimalizovala jejich variabilita (bude vysvětleno později viz. klasifikační lesy)
o   accuracy (měření přesnosti stromu) 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
o   nevhodné pro malý počet vzorků
Jak roste strom?
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: vyber takovou proměnnou, která rozdělí trénovací soubor na co nejhomogennější skupiny (algoritmy, jimiž se stromy vytváří, tj. algoritmy učení)
o   Algoritmus speciální pro klasifikaci: QUEST
o    Pro regresi i klasifikaci: CART(C&RT), CHAID
o    Další algoritmy: ID3, C4.5, C5.0
o    Obecně nelze říci, který z algoritmů je lepší
o   Výsledkem je vždy strom, který se však liší obsahem uzlů i jejich počtem.
systémy generující stromy
o    ID3 (Quinlan 79)
o   CART (Breiman et al. 84)
o   Assistant (Cestnik et al. 87)
o   C4.5 (Quinlan 93)
o   C5 (Quinlan 97)
o   Stromy ve Wece (Frank 2000)
o   Stromy v Orange (Demšar, Župan 2000)
o    RETIS (Karalič 1992) - pro regresní stromy
K čemu budeme klasifikační stromy využívat?
Máme data
zajímá nás struktura těchto dat, postižení vzájemných vztahů -DATA NYNÍ
o   Predikce, klasifikace dosud neznámých případů - DATA V BUDOUCNU
Pěstujeme klasifikační strom
o   Rozdělení dat do skupin:
trénovací data + testovací data
o   Tvorba stromu na základě trénovacích dat
o   Posouzení schopnosti stromu správně klasifikovat neznáme případy pocházející z množiny testovacích dat. Posouzení predikční schopnosti stromu.
o   Někdy také dělení dat do skupin:
trénovací data+validační data + testovací data
Krizové overovaní
Cross-validace
o   Rozdělení datového souboru do K skupin
(obvykle k= 10)
o   Jedna skupina vždy označena jako testovací. Zbytek skupin slouží k tvorbě stromu.
o   Každá skupina je testovací právě jednou.
o   Celkem vytvořeno K stromů. Na základě testovací skupiny ohodnotíme predikční schopnosti stromu.
o   máme-li malý počet vzorků- možnost použití např. Jack-knife
(vybere se vždy jen jeden vzorek...) -problémy při krosvalidaci není-li dostatečně velký soubor pro dělení na testovací a trénovací podsoubory - při rozdělení může dojít ke ztrátě informace u trénovacích dat a výsledný strom pak chybně klasifikuje
Křížové ověřování (Cross-validace)
Rozdělení datového souboru do K skupin (zde k=6)
TEST	TRAIN	TRAIN	TRAIN	TRAIN	TRAIN
TRAIN	TEST	TRAIN	TRAIN	TRAIN	TRAIN
TRAIN	TRAIN		TRAIN	TRAIN	TRAIN
TRAIN	TRAIN	TRAIN	TEST	TRAIN	TRAIN
TRAIN	TRAIN	TRAIN	TRAIN	TEST	TRAIN
TRAIN	TRAIN	TRAIN	TRAIN	TRAIN	TEST
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 prihs 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í.
o   Příliš malý strom
Příliš malý strom
o   Nemusí postihnout strukturu dat
Snižování složitosti stromu
o   Zastavíme růst stromu, když další dělení není statisticky významné
o   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!
Prořezávání (Cost - complexity Prunning)
"Přerostlý" strom, T
Odřezání koncových větví T - vytváření jednoduššího stromu,T1
Cena jednoduššího stromu (cost-complexity criterion):
kde |TJ je počet listů daného stromu, DstromT je deviance stromu,
a>0 vyvažuje vztah mezi velikostí stromu a kvalitou stromu (modelu)
Hledáme takový strom, který minimalizuje ^(T-,).
Regresní stromy
Regresní stromy I.
o   Modelujeme závislost spojité závisle proměnné na jedné či více nezávislých proměnných (kategoriálních, spojitých)
o   Je to posloupnost rozhodnutí, jejímž výsledkem je zařazení objektu do jednoho z listů na základě vlastností zkoumaného objektu
o   V každém uzlu je určena veličina, podle které dělíme datový soubor a hranice, která určuje, kde dělení má provést (je-li veličina spojitá).
Regresní stromy II.
o   Kořen obsahuje celý datový soubor
o   Z každého uzlu vyrůstají dvě (binární strom) nebo více větví
o   Každému objektu z koncových listů je přiřazena hodnota, kterou vypočteme jako aritmeticky průměr hodnot všech objektů v příslušném listu.
Další možností je vytvořit pro jednotlivé listy regresní modely (viz.následující příklad).
Příklad: Ukázka regresního stromu
Závislost spotřeby plynu na venkovní teplotě
T>-5
+
S=472-77T
T>5
o. co
+
S=631-46.8T
S=470-23.9T
Venkovní teplota
Výhody a nevýhody regresních stromů
Výhody
Snadné grafické znázornění
Neklade žádné podmínky na typ rozdělení (lineární regresní model - požadavek normality reziduí)
Algoritmy tvorby stromu jsou odolné vůči odlehlým hodnotám
Možno použít korelované proměnné
Nevýhody
Nestabilita - tvar stromu velmi závisí na datech
Modelovaná regresní plocha je nespojitá (je-li výsledná hodnota listu rovna aritmetickému průměru hodnot všech objektů v příslušném listu).
Posouzení kvality regresního stromu
o   Minimalizujeme Střední kvadratickou chybu (MSE - mean square error)
o  S rostoucí velikostí stromu sice MSE na množině trénovacích dat klesá. Ale skutečná chyba zpravidla klesá jen do určité velikosti stromu. Pak s narůstající velikostí stromu opět roste.
111
Software - stromy
o      Komerční:
1.     Statistica
2.     Clementine, data miner k SPSS
3.     Answer Tree (SPSS)
4.     Matlab
o      Volně šiřitelné:
1.     R - knihovny tree, rpart
C 4.5 http:;lwww.rulequest.com/Personal
Literatura k dalšímu studiu
Hastie T., Tibshirani R., Friedman J.: The Elements of Statistical Learning, Data mining, Inference and Prediction, Springer 2003
Lažanský et. Kol.: Umělá inteligence I.- IV.
o    Jan Klaschka, Emil Kotrč: Klasifikační a regresní lesy, sborník konference ROBUST 2004
Breiman, L. et al (1984) Classification and Regression Trees, Chapman and Hall
Breiman L. (2001) Random forests. Machine Learning 45, pp. 5-32.