Analýza a klasifikace dat - přednáška 6 MU RNDr. Eva Janousova IBA » Podzim 2015 Sekvenční klasifika Typy klasifikátorů t- 1. Podle reprezentace vstupních dat: - příznakové klasifikátory: paralelní x sekvenční - strukturální (syntaktické) klasifikátory - kombinované klasifikátory 2. Podle jednoznačnosti zařazení do skupin: - deterministické klasifikátory - pravděpodobnostní klasifikátory 3. Podle typů klasifikačních a učících algoritmů: - parametrické klasifikátory - neparametrické klasifikátory 4. Podle způsobu učení: - učení s učitelem: dokonalým x nedokonalým - učení bez učitele 5. Podle podle principu klasifikace: - klasifikace pomocí diskriminačních funkcí - klasifikace pomocí vzdálenosti od etalonů klasifikačních tříd - klasifikace pomocí hranic v obrazovém prostoru Janoušová: Analýza a klasifikace dat (^J Typy klasifikátorů - podle reprezentace vstupních dat • příznakové - vstupní data vyjádřena vektorem hodnot jednotlivých proměnných (příznaků): - paralelní - zpracování vektoru jako celku (např. Bayesův klasifikátor) - sekvenční - zpracování (občas i měření) proměnných postupně (např. klasifikační stromy) A A B C D E 1 id vek pohlaví vy^ka vaha 2 1 38 Z 164 45 3 2 35 M 157 90 4 3 25 Z 17S 70 • strukturální (syntaktické) - vstupní data popsána relačními strukturami • kombinované-jednotlivá primitiva doplněna příznakovým popisem MU Janoušová: Analýza a klasifikace dat (^J Sekvenční klasifikace - motivace • až dosud (bayesovské klasifikátory, klasifikátory s diskriminační hranicí, s minimální vzdáleností,...) - pevný konstantní počet příznaků • kolik a jaké proměnné? - málo proměnných - možná chyba klasifikace - moc proměnných - možná nepřiměřená pracnost, vysoké náklady - použít proměnné, které nesou co nejvíce informace o klasifikační úloze • sekvenční klasifikace - kompromis mezi velikostí klasifikační chyby a cenou určení příznaků - klasifikace na základě klasifikačního stromu - klasifikace s rostoucím počtem proměnných, přičemž okamžik ukončení klasifikační procedury stanoví klasifikátor sám podle předem daného kritéria pro kvalitu rozhodnutí (tj. na základě vlastností klasifikačních tříd, resp. objektů v nich) MU Janoušová: Analýza a klasifikace dat |yj 5 Klasifikační (rozhodovací) stromy a lesy Princip: Postupné rozdělování datasetu do skupin podle hodnot jednotlivých proměnných. (Zmenšený hipokampus Zvětšené komory Zmenšená amygdala \e Any/X Pacient Kontrola Pacient Kontrola Klasifikační lesy-použití více klasifikačních stromů ke klasifikaci. Janoušová: Analýza a klasifikace dat IBA W 6 Klasifikace s rostoucím počtem proměnných Princip: Seřadíme proměnné podle množství informace, které nesou, a pak opakovaně provádíme klasifikaci objektu (subjektu) s postupně se zvyšujícím počtem proměnných, dokud objekt nejsme schopni jednoznačně zařadit Kritéria pro řízení sekvenčního klasifikátoru: • Waldovo kritérium • Reedovo kritérium • Modifikované Waldovo kritérium • Modifikované Reedovo kritérium IBA Waldovo kritérium objekt x popsán množinou hodnot proměnných {x^ x2,...} mějme p(xv x2, Xj|cl)1) a p(xv x2, Xj|u)2), což jsou /-rozměrné hustoty pravděpodobnosti (tzn. dané prvními / proměnnými) výskytu objektu x = (xv x2,x,) v /-těm klasifikačním kroku v třídách (jô1 a co2 A a B jsou konstanty (0 A, pak se objekt x zařadí do třídy b)1 a proces se ukončí g (B,A), přidáme další proměnnou (příznak) xi+1 a proces se opakuje A A 1 B p zařazení do třídy Optimální vlastnosti Waldova kritéria, protože: ---------------- • průměrný počet proměnných je menší nebo stejný jako u kritérií s pevným počtem _ proměnných 1 2 3 4 5 / • průměrný počet kroků je menší než u jiných * sekvenčních kritérií H—I—I—I-h Janoušová: Analýza a klasifikace dat *jL |yj g Reedovo kritérium u více než 2 klasifikačních tříd založeno na výpočtu zobecněného věrohodnostního poměru pro /c-tou třídu A,(x | cok) a mezní hodnoty k-té třídy A(cok) postup: původní počet tříd výpočet Aj(x | cok) a A(ok) vyřazení tříd, u nichž Aj(x| cok) = A(cok) zbývající třídy přepočet Aj(x | cok) a A(cok) vyřazení tříd, u nichž Aj(x| cok) = A(cok) pokud není v některém kroku možné vyloučit žádnou třídu, zvýší se počet proměnných o 1 a proces pokračuje od začátku ^ 9 IBA Modifikované Waldovo kritérium • přes optimální vlastnosti Waldova kritéria může nastat: - počet kroků pro některé objekty velký, i když střední hodnota nízká - střední hodnota počtu kroků velká, pokud chceme malé pravděpodobnosti chybných rozhodnutí • 2 možnosti řešení: a) po určitém počtu kroků se b) zavedení proměnných hranic A(i) a B(i) sekvenční výpočet přeruší a dokončí se na základě nějakého rozhodnutí vycházejícího z nějakého kritéria založeného na pevném počtu příznaků Janoušová: Analýza a klasifikace dat |yj 10 Modifikované Reedovo kritérium ( ■ V' 1—- zobecněný věrohodnostní poměr se srovnává s prahem Gr(i) = gr V ^max J přičemž pokud A,(x | cor) < Gr(i), třída cor vyloučena z dalšího rozhodování jinak je postup stejný jako u klasického Reedova kritéria MU V4>-W A CD 11 Poznámka )- • nelze dopředu říci, která klasifikační metoda bude pro daná data fungovat nejlépe -> potřebné vyzkoušet více klasifikačních metod a zvolit nejvhodnější pro daná data • u velkých datových souborů je obtížné dopředu určit, zda je možné data oddělit lineárně nebo ne -> potřebné vyzkoušet lineární i nelineární klasifikační metody Hodnocení úspěšnosti klasifikace a srovnání klasifikátorů Janoušová: Analýza a klasifikace dat Hodnocení úspěšnosti klasifikace - úvod Vstupní data Subjekt voxel voxel voxel 12 3 Skutečnost (správná třída) 1 pacient 2 pacient 3 pacient 4 kontrola 5 kontrola 6 kontrola Výsledek klasifikace pacient pacient kontrola kontrola pacient kontrola Jak dobrá je klasifikační metoda, kterou jsme použili? Janoušová: Analýza a klasifikace dat IBA W 14 Hodnocení úspěšnosti klasifikace Matice záměn (konfusní matice, confusion matrix): Skutečnost (správná třída) Pacienti (+) Kontroly (-) Výsledek Pacienti W klasifikace Kontroly (-) TP FP FN TN TP („true positive") - kolik výsledků bylo skutečně pozitivních (tzn. kolik pacientů bylo správně diagnostikováno jako pacienti). FP („falše positive") - kolik výsledků bylo falešně pozitivních (tzn. kolik zdravých lidí bylo chybně diagnostikováno jako pacienti). FN („falše negative") - kolik výsledků bylo falešně negativních (tzn. kolik pacientů bylo chybně diagnostikováno jako zdraví). TN („true negative") - kolik výsledků bylo skutečně negativních (tzn. kolik zdravých lidí bylo správně diagnostikováno jako zdraví). MU Janoušová: Analýza a klasifikace dat *|L |yj 15 Hodnocení úspěšnosti klasifikace Skutečnost (správná třída) Pacienti Kontroly (+) (-) Pacienti Výsledek (+) TP FP klasifikace Kontroly (-) FN TN TP+FN FP+TN 1 i Senzitivita Specificita (sensitivity) (specificity) TP/ (TP+FN) TN / (FP+TN) Celková správnost (accuracy): (TP+TN)/(TP+FP+FN+TN) Chyba (error): (FP+FN)/(TP+FP+FN+TN) MU Janoušová: Analýza a klasifikace dat *|L |yj 15 Příklad - klasifikace pomocí FLDA Subjekt Skuteč- Výsledek nost LDA 1 P P 2 P P 3 P K 4 K K 5 K P 6 K K Senzitivita:TP/(TP+FN)=2/(2+l)=0,67 Specificita:TN/(FP+TN)=2/(l+2)=0,67 Správnost: (TP+TN)/(TP+FP+FN+TN)=(2+2)/(2+l+l+2)=0,67 Chyba: (FP+FN)/(TP+FP+FN+TN)=(l+l)/(2+l+l+2)=0,33 MU Janoušová: Analýza a klasifikace dat |yj 17 Výsledek klasifikace Skutečnost (správná třída) Pacienti (+) Kontroly (-) Pacienti (+) Kontroly (-) TP=2 FN=1 FP=1 TN=2 Intervaly spolehlivosti pro celkovou správnost TP+TN celková správnost: TP+FP+FN+TN • z toho plyne: PA = ^ (tedy Ncor~Bi(N, PA)) • za splnění předpokladů, že PA ■ N > 5, (l - PA) ■ N > 5 a N > 30, lze spočítat 95% interval spolehlivosti pro správnost pomocí aproximace na normální rozdělení: PA -1,96 • SE p'+1,96- TV TV MU ,....., Janoušová: Analýza a klasifikace dat *|L ; 18 Příklad - pokračování Správnost: (TP+TN)/(TP+FP+FN+TN) = 0,67 IS pro správnost: Pa~ i96.J^Jl^a}p j 96- jPal1 ^ TV 0.66-1.96- J°ME0M;0>66 + 1.96. 10,66(1-0,66) [0,29;1,00] MU Janoušová: Analýza a klasifikace dat |yj 19 Trénovací a testovací data 1. resubstituce 2. náhodný výběr s opakováním (bootstrap) 3. predikční testování externí validací (hold-out) 4. křížová validace (cross validation) /e-násobná (/e-fold) „odlož-jeden-mimo" (leave-one-out, jackknife) MU Janoušová: Analýza a klasifikace dat |yj 20 1. resubstituce • stejná trénovací a testovací množina • výhody: +jednoduché + rychlé • nevýhody: - příliš optimistické výsledky!!! Janoušová: Analýza a klasifikace dat |yj 21 2. náhodný výběr s opakováním (bootstrap) • náhodně vybereme N subjektů s opakováním jako trénovací data (tzn. subjekty se v trénovací sadě mohou opakovat) a zbylé subjekty (ani jednou nevybrané) použijeme jako testovací data • pro rozumně velká data se vybere zhruba 63,2% subjektů pro učení a 36,8% subjektů pro testování • trénování a testování se provede jen jednou • výhody: + velká trénovací sada + rychlé • nevýhody: - data se v trénovací sadě opakují - výsledek vcelku závislý na výběru trénovacích dat MU Janoušová: Analýza a klasifikace dat |yj 22 3. predikční testování externí validací (hold-out) použití části dat (většinou dvou třetin) na trénování a zbytku dat (třetiny) na testování výhody: + nezávislá trénovací a testovací sada nevýhody: - méně dat pro trénování i testování - výsledek velmi závislý na výběru trénovacích dat trénovací data testovací data MU Janoušová: Analýza a klasifikace dat |yj 23 3. predikční testování externí validací (hold-out) -modifikace 1 • použití části dat (obvykle poloviny) pro trénování a zbytku (poloviny) pro testování a následné přehození testovací a trénovací sady -> zprů-měrování 2 výsledků klasifikace • výhody: + nezávislá trénovací a testovací sada • nevýhody: - při malých souborech může být polovina dat pro trénování příliš málo - výsledek velmi závislý na výběru trénovacích dat (i když trochu méně než předtím) trénovací data testovací data testovací data trénovací data MU Janoušová: Analýza a klasifikace dat |yj 24 3. predikční testování externí validací (hold-out) -modifikace 2 • r-krát náhodně rozdělíme soubor na trénovací a testovací data (většinou dvě třetiny pro trénování a třetinu pro testování) a r výsledků zprůměrujeme iterace 1 iterace 2 iterace 3 iterace 4 iterace r trénovací data testovací data • výhody: + poměrně přesný odhad úspěšnosti klasifikace • nevýhody: - trénovací i testovací sady se překrývají - časově náročné MU Janoušová: Analýza a klasifikace dat |yj 25 4. /r-násobná křížová validace (/c-fold cross validation) i- • používán též název příčná validace • rozdělení souboru na k částí, 1 část použita na testování a zbylých k-1 částí na trénování -> postup se opakuje (všechny části lx použity pro testování) • speciálním případem je „odlož-jeden-mimo" (leave-one-out) CV (pro /c=N) napr. pro k=5: iterace 1 testování trénování trénování trénování trénování iterace 2 iterace 3 iterace 4 iterace 5 trénování testování trénování trénování trénování trénování trénování testování trénování trénování trénování trénování trénování testování trénování trénování trénování trénování trénování testování • výhody: + testovací sady se nepřekrývají + poměrně přesný odhad úspěšnosti klasifikace • nevýhody: - časově náročné MU Janoušová: Analýza a klasifikace dat |yj 26 „odlož-jeden-mimo" křížová validace • anglický překlad: leave-one-out (nebo jackknife) • pro k=N (tzn. v každé z N iterací je jeden subjekt použit na testování a zbylých A/-1 subjektů na trénování) • platí výhody a nevýhody zmíněné u /e-násobné křížové validace se čtyřmi komentáři: - časově nejnáročnější ze všech možných k - velmi vhodná pro malé soubory dat - na rozdíl od jakékoliv /c-fold CV dostaneme vždy pouze jeden výsledek úspěšnosti (tzn. výsledek úspěšnosti nezávisí na tom, jak se jednotlivé subjekty „namíchají" do jednotlivých skupin) - v některých článcích se uvádí, že lehce nadhodnocuje úspěšnost -> doporučuje se 10-násobná křížová validace MU Janoušová: Analýza a klasifikace dat |yj 27 Příklad - „odlož-jeden-mimo" křížová validace Iterace: iter. 1 iter. 2 iter. 3 iter. 4 iter. 5 iter. 6 Skutečnost: Výsledek klasifikace: pacient pacient pacient kontrola pacient kontrola kontrola kontrola kontrola pacient kontrola kontrola Výsledek klasifikace Skutečnost pac. kont. pacient kontrola TP=1 FP=1 FN=2 TN=2 Senzitivita: /( +2)=0,33 Specificita: 2/(l+2)=0,67 Správnost: (l+2)/(l+l+2+2)=0,50 Chyba: (l+2)/(l+l+2+2)=0,50 Janoušová: Analýza a klasifikace dat IBA W 28 Upozornění!!! Je potřebné rozdělit soubor na trénovací a testovací ještě před redukcí dat, jinak dostaneme nadhodnocené výsledky!!! Trénovací fáze Testovací fáze Y GVa m) *{N\ i) -9 □ □ □ * □ □ □ Vpca {n x m) (1 x m) i (IX Testovací obraz rozložený do vektoru Vybrané príznaky pomncí PCA Klasifikační skóre Janoušová: Analýza a klasifikace dat IBA W 29 Je klasifikace lepší než náhodná klasifikace? \-- • permutační testování • jednovýběrový binomický test MU Janoušová: Analýza a klasifikace dat |yj 30 Permutační testování • r-krát náhodně přeházíme identifikátory příslušnosti do skupin u subjektů a provedeme klasifikaci (se stejným nastavením jako při použití originálních dat) • p-hodnota se vypočte jako: n/r, kde n je počet iterací, v nichž byla úspěšnost klasifikace (např. celková správnost) vyšší nebo rovna úspěšnosti klasifikace originálních dat (PA) • pozn. pokud histogram z r celkových správností získaných permutacemi neleží kolem 0,5 (v případě vyrovnaných skupin), máme v algoritmu zřejmě někde chybu! MU Janoušová: Analýza a klasifikace dat |yj 31 Jednovýběrový binomický test • testujeme, zda se liší celková správnost (což je podíl správně zařazených subjektů) od správnosti získané náhodnou klasifikací • správnost u náhodné klasifikace: PA =ní/n> kde Nt je počet subjektů nejpočetnější skupiny Pa-Pa0 • z — pA0(l-PA0))/N • Pokud |z| >1,96, zamítáme nulovou hypotézu o shodnosti správnosti naší klasifikace a správnosti náhodné klasifikace MU Janoušová: Analýza a klasifikace dat |yj 32 Příklad - jednovýběrový binomický test • uvažujme např. výsledek klasifikace pacientů a kontrol pomocí LDA (pomocí resubstituce): PA = 0,67, N = 6, PAq = Ni/N = 0,5 • protože |z| <1,96, nezamítáme nulovou hypotézu o shodnosti správnosti naší klasifikace a správnosti náhodné klasifikace (tzn. neprokázali jsme, že by naše klasifikace byla lepší než náhodná klasifikace) • nezamítnutí nulové hypotézy vyplývá už i z vypočteného intervalu spolehlivosti (0,29 - 1,00), protože tento interval spolehlivosti obsahuje hodnotu 0,5 Pa-Pa 0,67-0,5 Janoušová: Analýza a klasifikace dat IBA IMJ 33 Srovnání úspěšnosti klasifikace i-- • Srovnání 2 klasifikátorů • Srovnání 3 a více klasifikátorů MU Janoušová: Analýza a klasifikace dat *|L J^J = 34 Srovnání 2 klasifikátorů Klasifikátor 1 Klasifikátor 2 Správně (1) Chybně (0) Správně (1) Chybně (0) Nu N10 N01 iV00 Celkem: Nlt + N10 + JV01 + JV00 = Nts (Wh — JViol — I)' McNemarův test: JVbi + Mo Pokud x2 > 3,841, zamítáme nulovou hypotézu H0 o shodnosti celkové správnosti klasifikace pomocí dvou klasifikátorů Dvouvýběrový binomický test: P\-P2 Nu+Niq Mi+JVoi * , , Pokud |z| > 1,96, zamítáme nulovou hypotézu H0 o shodnosti podílu správně klasifikovaných subjektů dvou klasifikátorů Dvouvýb. binomický test předpokládá nezávislost (tzn. že každý klasifikátor byl testován na jiném testovacím souboru) -> raději používat McNemarův test MU Janoušová: Analýza a klasifikace dat *|L |yj 35 Příklad - srovnání 2 klasifikátorů Lineární diskriminační Metoda 9 nejbližších analýza (LDA) sousedů (9-nn) -1C -:■ i ň -iií -S ť MU Janoušová: Analýza a klasifikace dat |yj 36 Příklad - srovnání 2 klasifikátorů LDA 9-nn Matice záměn: 42 8 44 6 8 42 2 48 84% správnost 92% správnost Shody u klasifikátorů: Klasifikátor 1: LDA Klasifikátor 2: 9-nn Správně (1) Chybně (0) Správně (1) Chybně (0) N1± = 82 N10 = 2 N01 = 10 JV00 = 6 McNemarův test: Dvouvýb. binomický test: x2 = Cl 10 — 2| - l)2 _49 10 + 2 ~T2 4.0833 0.84 - 0.92 z — Protože x2 > 3,841, zamítáme H0. 7(2 x 0.88 x 0.12)/(100) Protože |z| < 1,96, nezamítáme H0. -1.7408 Janoušová: Analýza a klasifikace dat IBA W 37 Srovnání 3 a více klasifikátorů Testuje se, zda jsou statisticky významně odlišné správnosti klasifikátorů měřené na stejných testovacích datech -tzn. H0: p1 = p2 = ••• = pL , kde pL je správnost L-tého klasifikátorů. Poté je možno srovnávat správnosti klasifikátorů vždy po dvou, aby se zjistilo, které klasifikátory se od sebe liší. Cochranův Q test: Qc = (L-l) LT - E^i {Ljf Pokud Qc > x2 (L — 1)/ zamítáme H0. F-test: msa Pokud Fcal > F(L - 1, (L - 1) X (Nts - 1)), zamítáme H0. msab Looney doporučuje F-test, protože je méně konzervativní. IBA IMJ 38 Příklad - srovnání 3 a více klasifikátorů Matice záměn: LDA 9-nn Parzen 42 8 44 6 47 3 8 42 2 48 5 46 84% správnost 92% správnost 92% správnost 3 x (842 + 922 + 922) - 2682 Cochranův Q test: Qc = 2 x v 7 * 3.7647 3 x 268 — (80 x 9+11x4 +6 x 1) Protože Qc < x2 (L — 1) = 5,991, nezamítáme H0. 0 2223 F-test: Fcai = t^t^t ^ 4.0492 0.0549 Protože Fcař > F(2; 198) = 3,09, zamítáme H0. Janoušová: Analýza a klasifikace dat *jL (yj 3g Shrnutí • výpočet úspěšnosti klasifikace (správnosti, chyby, senzitivity, specificity a přesnosti) pomocí matice záměn • výpočet intervalu spolehlivosti pro správnost a chybu • volba trénovacího a testovacího souboru: - resubstituce - náhodný výběr s opakováním (bootstrap) - predikční testování externí validací (hold-out) - křížová validace (cross validation): k-násobná, „odlož-jeden-mimo" • srovnání úspěšnosti klasifikace s náhodnou klasifikací - permutační testování - jednovýběrový binomický test • srovnání úspěšnosti klasifikace 2 klasifikátorů: - McNemarův test - dvouvýběrový binomický test • srovnání úspěšnosti klasifikace 3 a více klasifikátorů: - Cochranův Q test - F-test MU Janoušová: Analýza a klasifikace dat |yj 40 Příprava nových učebních materiálů pro obor Matematická biologie je podporována projektem OPVK č. CZ.1.07/2.2.00/28.0043 „Interdisciplinární rozvoj studijního oboru Matematická biologie" evropský sociální fond V ČR EVROPSKÁ UNIE INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ MINISTERSTVO ŠKOLSTVÍ, OPVzdělávání MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost MU Janoušová: Analýza a klasifikace dat |yj 41