Pokročilé neparametrické metody esf-komplet-barva.jpg Klára Komprdová logo-IBA Další typy stromů CHAID, PRIM, MARS logo-IBA Pokročilé neparametrické metody logo-IBA Pokročilé neparametrické metody CHAID - Chi-squared Automatic Interaction Detector ¢G.V.Kass (1980) ¢Strom pro kategoriální proměnné→ převod spojitých proměnných na ordinální ¢Je často využíván v komerčních sférách, především v marketingu a průzkumech veřejného mínění, má ale použití i v přírodovědných oborech. ¢nebinárního typu —Po prvním dělení nemusí zbývat dostatek pozorování na vytvoření dalších „pater“ stromu →vhodnější pro větší datové soubory. ¢Jako kriteriální statistika pro větvení se používá c2 –test. logo-IBA Pokročilé neparametrické metody Příklad - kosatce logo-IBA Pokročilé neparametrické metody c2 –test - opakování ¢c2 –test je použit pro zjištění nezávislosti v kontingenční tabulce, která je tvořena kombinací kategorií závisle proměnné a prediktoru ¢Jsou-li Y a X nezávislé, má testová statistika přibližně Pearsonovo c2 rozdělení s υ = (r-1)(s-1) stupni volnosti, kde r je počet řádků a s je počet sloupců v kontingenční tabulce. ¢Nezávislost v kontingenční tabulce znamená, že se obě proměnné navzájem neovlivňují v hodnotách, které nabývají. ¢Hypotéza nezávislosti jevů je zde nulovou hypotézou H0. ¢Pearsonův c2 –test je často označován jako test dobré shody. logo-IBA Pokročilé neparametrické metody Kontingenční tabulka kategorie prediktoru X kategorie Y j i 1 2 … s Celkem 1 p11 p12 … p1s R1 2 p21 p22 … p2s R2 … … … … … … r pr1 pr2 … prs Rr Celkem S1 S2 … Ss n porovnáváme očekávané četnosti v kontingenční tabulce s jejich skutečnými četnostmi logo-IBA Pokročilé neparametrické metody c2 –test ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢kde i a j je označení řádků (resp. sloupců) v kontingenční tabulce, pij je pozorovaná frekvence, oij očekávaná frekvence, n je celkový počet pozorování, Ri je počet pozorování v řádku i, Sj je počet pozorování ve sloupci j. logo-IBA Pokročilé neparametrické metody Příklad - Rozdělení semen dvou příbuzných rostlin podle barvy a tvaru ¢Bylo zkoumáno celkem 160 semen dvou druhů příbuzných rostlin. Semena byla roztříděna do následujících kategorií: žluté/hladké; žluté/vrásčité; zelené/hladké; zelené/vrásčité ¢ žluté/hladké žluté/vrásčité zelené/hladké zelené/vrásčité Celkový součet Druh1 10 25 10 15 60 Očekávaný počet Druh2 20 30 20 30 100 Očekávaný počet Celkový součet 30 55 30 45 160 logo-IBA Pokročilé neparametrické metody Algoritmus růstu stromu CHAID ¢Krok1: pro každý prediktor Xi: Vytvoř kontingenční tabulku kategorií závisle proměnné a prediktoru. ¢ ¢Krok 2: mohou nastat tři případy: —Pokud je počet kategorií prediktoru > 2, utvoří se dvojice z kategorií prediktoru→ kategoriální x ordinální. Najde se taková dvojice, která si je co do hodnot závisle proměnné Y nejvíce podobná →dvojice, jejíž c2 - test má nejvyšší p hodnotu. —Pokud má prediktor 2 kategorie → algoritmus pokračuje krokem 5 —Pokud má prediktor X pouze jednu kategorii → p hodnota je nastavena na 1 — ¢Krok 3: Dvojice s nejvyšší p hodnotou, která není statisticky významná nebo větší než alpha2, se sloučí do jedné skupiny. —u ordinálního prediktoru se spojují pouze sousední kategorie —u kategoriálního jsou dvojice vytvořeny kombinací všech kategorií. —Prediktor X je dále používán s novými již sloučenými kategoriemi —Pokud je i po sloučení počet kategorií > 2, algoritmus se vrátí do kroku 2. Pokud ne, algoritmus pokračuje krokem 4 nebo 5. ¢ ¢Pozn: alpha2, 3 a 4 jsou hodnoty zadané uživatelem logo-IBA Pokročilé neparametrické metody Algoritmus růstu stromu CHAID ¢Krok 4: Sloučené kategorie mohou být zpětně rozděleny. Jestliže se nově vytvořené skupiny kategorií skládají ze tří nebo více původních kategorií, najde se nejlepší binární rozdělení mezi sloučenými kategoriemi (s nejnižší p hodnotou). Pokud je p hodnota významná nebo větší než alpha3, dojde k rozdělení. ¢ ¢Krok 5: Každá kategorie, která má velmi málo pozorování (minimum je definováno uživatelem), je spojena s nejpodobnější kategorií (opět určeno na základě největší p hodnoty) ¢ pozn: toto nastavení je volitelné a bývá dostupné jen v některých softwarech. ¢ ¢Výše popsaným postupem jsme získali optimální sloučení pro každý prediktor. ¢ ¢Krok 6: V posledním kroku je spočítána adjustovaná p hodnota c2 testu pro sloučené kategorie každého z prediktorů pomocí Bonferroniho korekce. Vybere se prediktor s nejmenší adjustovanou p hodnotou nebo hodnotou větší než alpha4. Tento prediktor s optimálně sloučenými kategoriemi je použit k rozdělení uzlu. Pokud významný prediktor nelze nalézt, uzel se již dále nedělí a je považován za terminální. ¢ logo-IBA Pokročilé neparametrické metody Algoritmus růstu stromu CHAID – ilustrační příklad ¢Zajímá nás klasifikace potravních strategií druhů makrozoobentosu podle různých kategorií nadmořské výšky. Pro jednoduchost se budeme zabývat pouze jedním prediktorem. ¢ ¢ N-nížinné S - střední P - podhorské H - horské sběrači spásači filtrátoři dravci Kontingenční tabulka -v buňkách by byly počty jednotlivých druhů Krok 1 logo-IBA Pokročilé neparametrické metody Algoritmus růstu stromu CHAID – ilustrační příklad ¢Pro každou podtabulku je spočítán Pearsonův c2 -test nezávislosti. Najdeme největší p hodnotu testu, pokud není signifikantní (menší než zvolené α), kategorie spojíme. Protože je nadmořská výška ordinální parametr, můžeme sloučit pouze vedlejší kategorie. tab3 Krok 2 a 3 logo-IBA Pokročilé neparametrické metody Algoritmus růstu stromu CHAID – ilustrační příklad tab3 Test sloučených kategorií: Opět spočítáme Pearsonův c2-test nezávislosti pro každou podtabulku, nyní již sloučených kategorií. Obě p hodnoty byly statisticky významné pro zvolené α=0,05 a k dalšímu sloučení již nedochází. Přecházíme rovnou do kroku 6, neboť jsme získali optimální sloučení prediktoru → krok 4 a 5 není v našem příkladu potřeba. Krok 2 a 3 p*B logo-IBA Pokročilé neparametrické metody ¢Finální rozdělení uzlu: —Za předpokladu, že je nadmořská výška prediktorem s nejnižší adjustovanou p hodnotou, původní uzel obsahující celý datový soubor bude rozdělen na tři dceřiné uzly, podle sloučených kategorií nadmořské výšky. Algoritmus růstu stromu CHAID – ilustrační příklad chaid3 Krok 6 logo-IBA Pokročilé neparametrické metody Bonferroniho korekce ¢V algoritmu dochází k současnému testování více hypotéz →v našem příkladu bylo třeba učinit celkem čtyři testy pro možné sloučení kategorií. ¢ ¢Při mnohonásobném testování však vzrůstá pravděpodobnost, že zamítneme nulovou hypotézu H0, přestože platí. ¢ ¢Počet prováděných testů u metody CHAID roste s počtem kategorií závisle proměnné a prediktorů. ¢ ¢Použitím Bonferroniho korekce je možné zmírnit vliv mnohonásobného testování a získat porovnatelné p hodnoty pro jednotlivé prediktory s různým počtem kategorií. ¢ ¢Výsledná p hodnota pro kontingenční tabulku kategorií závisle proměnné a optimálně sloučeného prediktoru je vynásobena B koeficientem, čímž získáme adjustovanou p hodnotu pro daný prediktor. logo-IBA Pokročilé neparametrické metody Bonferroniho korekce - Koeficient B ¢ordinální proměnná → slučování sousedních kategorií ¢kategoriální proměnná→ slučování všech možných kombinací ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢kde r je počet řádků a s je počet sloupců kontingenční tabulky kategorií závisle proměnné a prediktoru. logo-IBA Pokročilé neparametrické metody Příklad- kosatce chaid iris1 logo-IBA Pokročilé neparametrické metody Strom CHAID ¢Růst stromu se zastaví, pokud je dosaženo následujících pravidel: —není možné nalézt žádné významné rozdělení. —Všechna pozorování závisle proměnné v uzlu mají stejnou hodnotu nebo identickou hodnotu pro každý prediktor. —Pokud je dosaženo uživatelem definovaných nastavení, která se týkají: ¢parametrů velikosti stromu jako je nastavení počtu terminálních uzlů nebo větví; ¢počtu pozorování v uzlu, které je menší než minimum stanovené uživatelem nebo počtu pozorování, které by po rozdělení vedlo k dceřiným uzlům s menším počtem pozorování, než je definováno uživatelem. ¢ ¢Celkovou správnost stromu OAkateg určujeme stejně jako v případě stromu CART. K odhadu obecné chyby e(t) je možné opět použít k-testovacích souborů z krosvalidace. ¢ ¢ logo-IBA Pokročilé neparametrické metody PRIM - Patient Rule Induction Method logo-IBA Pokročilé neparametrické metody logo-IBA Pokročilé neparametrické metody PRIM - Patient Rule Induction Method ¢PRIM (Friedman & Fisher, 1999) - metoda primárně určena pro regresi. ¢ ¢PRIM podobně jako ostatní rozhodovací stromy rozděluje pozorování závisle proměnné Y pomocí hodnot prediktorů do uzlů t1,..,tN, → označovaných jako okna B1,…, BK ¢ ¢Graficky můžeme okna znázornit jako jednotlivé regiony v prostoru prediktorů X1,…, XM. ¢ ¢V případě metody PRIM se však vyhledávají takové regiony, ve kterých je průměr hodnot závisle proměnné Y nejvyšší (nebo nejnižší). ¢ ¢Výsledkem je sada jednoduchých pravidel, která definují jednotlivá okna a rozdělují pozorování závisle proměnné ¢ logo-IBA Pokročilé neparametrické metody PRIM prim1 Mějme 100 pozorování. Závisle proměnná Y označuje presenci yi = 1 (trojúhelníky) nebo absenci yi = 0 (kolečka) určitého druhu rostliny. Pro jednoduchost uvažujme pouze dva spojité prediktory: teplotu X1 a srážky X2. Rostlina bude přítomna s větší pravděpodobností v podmínkách daných rozsahem prediktorů (a1 ≤ X1 ≤ b1) ∩ (a2 ≤ X2 ≤ b2), které jsou zde znázorněny pomocí okna B. logo-IBA Pokročilé neparametrické metody PRIM - algoritmus ¢1. Soubor se rozdělí na testovací a trénovací (v poměru zadaném uživatelem). Seřadí se hodnoty prediktorů od nejmenší po největší. Okno obsahuje celý datový soubor (trénovací) ¢ ¢2. Okno se zmenšuje podél jedné hrany o malé množství pozorování (často α=0.1 nebo α=0.05) – tak aby výsledný průměr ve zmenšeném okně byl co největší (nejmenší) ¢ ¢Krok 1 a 2 se opakuje dokud okno neobsahuje předem stanovené minimum pozorování (např. 10) ¢ ¢3. dochází k reverznímu procesu-okno je zpětně rozšiřováno do všech směrů, ale jen pokud se zvýší průměr v okně ¢Z kroku 1-3 se získá sekvence oken o různém počtu pozorování ¢ ¢4. použije se krosvalidace k vybrání optimálního okna B1- testovací soubor! ¢5. Odstraní se vzorky z okna B1 -pozorování která jsou odstraněna z okna mají nejvyšší (nejnižší) hodnoty prediktoru Xj ¢ ¢ ¢Krok 2-5 se opakuje, dokud není dosaženo konečného počtu oken B1,B2 ,….. BK ¢ ¢Okna jsou dána rozhodovacími pravidly ¢Stejně jako v CART lze použít kategoriální prediktor ¢ logo-IBA Pokročilé neparametrické metody PRIM - algoritmus ¢200 bodů, rovnoměrně rozdělených do jednotkového čtverce ¢Závisle proměnná Y má hodnotu 1 (červená barva) pokud je 0.5