© Institut biostatistiky a analýz Analýza a klasifikace dat – přednáška 7 RNDr. Eva Janoušová Podzim 2014 Hodnocení úspěšnosti klasifikace a srovnání klasifikátorů 2Janoušová: Analýza a klasifikace dat Hodnocení úspěšnosti klasifikace - úvod 3Janoušová: Analýza a klasifikace dat Subjekt voxel 1 voxel 2 voxel 3 ... Skutečnost (správná třída) 1 pacient 2 pacient 3 pacient 4 kontrola 5 kontrola 6 kontrola pacient pacient kontrola kontrola pacient kontrola Vstupní data Výsledek klasifikace Jak dobrá je klasifikační metoda, kterou jsme použili? Hodnocení úspěšnosti klasifikace 4Janoušová: Analýza a klasifikace dat Skutečnost (správná třída) Pacienti (+) Kontroly (-) Výsledek klasifikace Pacienti (+) TP FP Kontroly (-) FN TN Matice záměn (konfusní matice, confusion matrix): TP („true positive“) – kolik výsledků bylo skutečně pozitivních (tzn. kolik pacientů bylo správně diagnostikováno jako pacienti). FP („false positive“) – kolik výsledků bylo falešně pozitivních (tzn. kolik zdravých lidí bylo chybně diagnostikováno jako pacienti). FN („false 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í). Hodnocení úspěšnosti klasifikace 5Janoušová: Analýza a klasifikace dat Skutečnost (správná třída) Pacienti (+) Kontroly (-) Výsledek klasifikace Pacienti (+) TP FP Kontroly (-) FN TN TP+FN FP+TN Senzitivita (sensitivity) Specificita (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) Příklad – klasifikace pomocí FLDA 6Janoušová: Analýza a klasifikace dat Subjekt Skuteč- nost Výsledek LDA 1 P P 2 P P 3 P K 4 K K 5 K P 6 K K Výsledek klasifikace Skutečnost (správná třída) Pacienti (+) Kontroly (-) Pacienti (+) TP=2 FP=1 Kontroly (-) FN=1 TN=2 Senzitivita: TP/(TP+FN)=2/(2+1)=0,67 Specificita: TN/(FP+TN)=2/(1+2)=0,67 Správnost: (TP+TN)/(TP+FP+FN+TN)=(2+2)/(2+1+1+2)=0,67 Chyba: (FP+FN)/(TP+FP+FN+TN)=(1+1)/(2+1+1+2)=0,33 Intervaly spolehlivosti pro chybu • chyba: 𝐹𝐹+𝐹𝑁 𝑇𝑇+𝐹𝐹+𝐹𝐹+𝑇𝑇 = 𝑁 𝑒𝑒𝑒𝑒𝑒 𝑁 7Janoušová: Analýza a klasifikace dat • ze statistického hlediska – odhad pravděpodobnosti chyby: 𝑃� 𝐸 = 𝑁 𝑒𝑒𝑒𝑒𝑒 𝑁 (vychází z: 𝑁𝑒𝑒𝑒𝑒𝑒~𝐵𝐵(𝑁, 𝑃𝐸 )) • za splnění předpokladů, že 𝑃� 𝐸 ∙ 𝑁 > 5, 1 − 𝑃� 𝐸 ∙ 𝑁 > 5 a 𝑁 > 30, lze spočítat 95% interval spolehlivosti pro chybu pomocí aproximace na normální rozdělení: ( ) ( )         − ⋅+ − ⋅− N PP P N PP P EE E EE E ˆ1ˆ 96,1ˆ; ˆ1ˆ 96,1ˆ ( ) ( )         − ⋅+ − ⋅− N PP P N PP P AA A AA A ˆ1ˆ 96,1ˆ; ˆ1ˆ 96,1ˆ Intervaly spolehlivosti pro celkovou správnost • celková správnost: 𝑇𝑇+𝑇𝑁 𝑇𝑇+𝐹𝐹+𝐹𝐹+𝑇𝑇 = 1 − 𝑁 𝑒𝑒𝑒𝑒𝑒 𝑁 8Janoušová: Analýza a klasifikace dat • z toho plyne: 𝑃�𝐴 = 1 − 𝑃� 𝐸 = 𝑁 𝑐𝑐𝑐 𝑁 (tedy 𝑁𝑐𝑐𝑐~𝐵𝐵(𝑁, 𝑃𝐴)) • za splnění předpokladů, že 𝑃�𝐴 ∙ 𝑁 > 5, 1 − 𝑃�𝐴 ∙ 𝑁 > 5 a 𝑁 > 30, lze spočítat 95% interval spolehlivosti pro správnost pomocí aproximace na normální rozdělení: Příklad – pokračování 9Janoušová: Analýza a klasifikace dat ( ) ( )         − ⋅+ − ⋅− N PP P N PP P EE E EE E ˆ1ˆ 96,1ˆ; ˆ1ˆ 96,1ˆIS pro chybu: ( ) ( )       − ⋅+ − ⋅− 6 33,0133,0 96,133,0; 6 33,0133,0 96,133,0 [ ]00,1;29,0 ( ) ( )         − ⋅+ − ⋅− N PP P N PP P AA A AA A ˆ1ˆ 96,1ˆ; ˆ1ˆ 96,1ˆ ( ) ( )       − ⋅+ − ⋅− 6 66,0166,0 96,166,0; 6 66,0166,0 96,166,0 [ ]71,0;0 IS pro správnost: Chyba: (FP+FN)/(TP+FP+FN+TN) = 0,33 Správnost: (TP+TN)/(TP+FP+FN+TN) = 0,67 Trénovací a testovací data 10Janoušová: Analýza a klasifikace dat 4. křížová validace (cross validation) - k-násobná (k-fold) - „odlož-jeden-mimo“ (leave-one-out, jackknife) 1. resubstituce 2. náhodný výběr s opakováním (bootstrap) 3. predikční testování externí validací (hold-out) 1. resubstituce 11Janoušová: Analýza a klasifikace dat • stejná trénovací a testovací množina • výhody: + jednoduché + rychlé • nevýhody: - příliš optimistické výsledky!!! 2. náhodný výběr s opakováním (bootstrap) 12Janoušová: Analýza a klasifikace dat • 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 3. predikční testování externí validací (hold-out) 13Janoušová: Analýza a klasifikace dat • 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 3. predikční testování externí validací (hold-out) – modifikace 1 14Janoušová: Analýza a klasifikace dat • 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 3. predikční testování externí validací (hold-out) – modifikace 2 15Janoušová: Analýza a klasifikace dat • 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 • 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é trénovací data testovací data iterace 1 iterace 2 iterace 3 iterace 4 iterace r... 16Janoušová: Analýza a klasifikace dat • 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 1x použity pro testování) • speciálním případem je „odlož-jeden-mimo“ (leave-one-out) CV (pro k=N) • výhody: + testovací sady se nepřekrývají + poměrně přesný odhad úspěšnosti klasifikace • nevýhody: - časově náročné 4. k-násobná křížová validace (k-fold cross validation) testování trénování trénování trénování trénování např. pro k=5: iterace 1 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í „odlož-jeden-mimo“ křížová validace • platí výhody a nevýhody zmíněné u k-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 k-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 17 • 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 N-1 subjektů na trénování) Janoušová: Analýza a klasifikace dat Příklad - „odlož-jeden-mimo“ křížová validace 18Janoušová: Analýza a klasifikace dat pacient kontrola kontrola kontrola pacient kontrola 1 2 3 4 5 6 iter. 1 iter. 2 iter. 3 iter. 4 iter. 5 iter. 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 Skutečnost: pacient pacient pacient kontrola kontrola kontrola Výsledek klasifikace Skutečnost pac. kont. pacient TP=1 FP=1 kontrola FN=2 TN=2 Iterace: Výsledek klasifikace: pacient kontrola kontrola kontrola pacient kontrola Senzitivita: 1/(1+2)=0,33 Specificita: 2/(1+2)=0,67 Správnost: (1+2)/(1+1+2+2)=0,50 Chyba: (1+2)/(1+1+2+2)=0,50 Upozornění !!! 19Janoušová: Analýza a klasifikace dat Je potřebné rozdělit soubor na trénovací a testovací ještě před redukcí dat, jinak dostaneme nadhodnocené výsledky!!! Je klasifikace lepší než náhodná klasifikace? • permutační testování • jednovýběrový binomický test 20Janoušová: Analýza a klasifikace dat 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: 𝑛 𝑟⁄ , 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, máme v algoritmu zřejmě někde chybu! 21 PA0,5 → Janoušová: Analýza a klasifikace dat 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: 𝑃𝐴0 = 𝑁 𝑖 𝑁� , kde 𝑁𝑖 je počet subjektů nejpočetnější skupiny • 𝑧 = 𝑃 𝐴−𝑃 𝐴0 𝑃 𝐴0 1−𝑃 𝐴0 𝑁⁄ • Pokud 𝑧 >1,96, zamítáme nulovou hypotézu o shodnosti správnosti naší klasifikace a správnosti náhodné klasifikace 22Janoušová: Analýza a klasifikace dat Příklad – jednovýběrový binomický test • uvažujme např. výsledek klasifikace pacientů a kontrol pomocí LDA (pomocí resubstituce): 𝑃𝐴 = 0,67, 𝑁 = 6, 𝑃𝐴0 = 𝑁 𝑖 𝑁� = 0,5 • 𝑧 = 𝑃 𝐴−𝑃 𝐴0 𝑃 𝐴0 1−𝑃 𝐴0 𝑁⁄ = 0,67−0,5 0,5 1−0,5 6⁄ = 0,83 • Protože 𝑧 <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) 23Janoušová: Analýza a klasifikace dat Srovnání úspěšnosti klasifikace • Srovnání 2 klasifikátorů • Srovnání 3 a více klasifikátorů 24Janoušová: Analýza a klasifikace dat Srovnání 2 klasifikátorů 25 McNemarův test: Dvouvýběrový binomický test: 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 Klasifikátor 1 Klasifikátor 2 Správně (1) Chybně (0) Správně (1) 𝑁11 𝑁10 Chybně (0) 𝑁01 𝑁00 Celkem: Pokud χ2 > 3,841, zamítáme nulovou hypotézu H0 o shodnosti celkové správnosti klasifikace pomocí dvou klasifikátorů Pokud 𝑧 >1,96, zamítáme nulovou hypotézu H0 o shodnosti podílu správně klasifikovaných subjektů dvou klasifikátorů 𝑁11 + 𝑁10 + 𝑁01 + 𝑁00 = 𝑁𝑡𝑡 Janoušová: Analýza a klasifikace dat Příklad – srovnání 2 klasifikátorů 26 Lineární diskriminační analýza (LDA) Metoda 9 nejbližších sousedů (9-nn) Janoušová: Analýza a klasifikace dat Příklad – srovnání 2 klasifikátorů 27 Matice záměn: McNemarův test: Dvouvýb. binomický test: Klasifikátor 1: LDA Klasifikátor 2: 9-nn Správně (1) Chybně (0) Správně (1) 𝑁11 = 82 𝑁10 = 2 Chybně (0) 𝑁01 = 10 𝑁00 = 6 9-nnLDA správnost správnost Protože χ2 > 3,841, zamítáme H0. Protože 𝑧 < 1,96, nezamítáme H0. Shody u klasifikátorů: Janoušová: Analýza a klasifikace dat Srovnání 3 a více klasifikátorů 28 Cochranův Q test: F-test: Looney doporučuje F-test, protože je méně konzervativní. Testuje se, zda jsou statisticky významně odlišné správnosti klasifikátorů měřené na stejných testovacích datech – tzn. 𝐻0: 𝑝1 = 𝑝2 = ⋯ = 𝑝 𝐿 , kde 𝑝 𝐿 je správnost L-tého klasifikátoru. Poté je možno srovnávat správnosti klasifikátorů vždy po dvou, aby se zjistilo, které klasifikátory se od sebe liší. Pokud 𝑄 𝐶 > χ2 (𝐿 − 1), zamítáme H0. Pokud 𝐹𝑐𝑐𝑐 > 𝐹(𝐿 − 1, 𝐿 − 1 × 𝑁𝑡𝑡 − 1 ), zamítáme H0. Janoušová: Analýza a klasifikace dat Příklad – srovnání 3 a více klasifikátorů 29 Cochranův Q test: F-test: Matice záměn: 9-nnLDA Parzen Protože 𝑄 𝐶 < χ2 𝐿 − 1 = 5,991, nezamítáme H0. Protože 𝐹𝑐𝑐𝑐 > 𝐹 2; 198 = 3,09, zamítáme H0. správnost správnost správnost Janoušová: Analýza a klasifikace dat 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 30Janoušová: Analýza a klasifikace dat 31Janoušová: Analýza a klasifikace dat 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“