© Institut biostatistiky a analýzINVESTICE DO ROZVOJE VZDĚLÁVÁNÍ ANALÝZA A KLASIFIKACE DAT RNDr. Eva Janoušová © Institut biostatistiky a analýz HODNOCENÍ ÚSPĚŠNOSTI KLASIFIKACE A SROVNÁNÍ KLASIFIKÁTORŮ © Institut biostatistiky a analýz ÚVOD Subjekt Objem hipokampu Objem komor Skutečnost (správná třída) 1 2 12 pacient 2 4 10 pacient 3 3 8 pacient 4 5 7 kontrola 5 3 9 kontrola 6 4 5 kontrola pacient pacient kontrola kontrola pacient kontrola Vstupní data Výsledek klasifikace Jak dobrá je klasifikační metoda, kterou jsme použili? © Institut biostatistiky a analýz HODNOCENÍ ÚSPĚŠNOSTI KLASIFIKACE þ 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í). 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): © Institut biostatistiky a analýz HODNOCENÍ ÚSPĚŠNOSTI KLASIFIKACE Skutečnost (správná třída) Pacienti (+) Kontroly (-) Výsledek klasifikace Pacienti (+) TP FP TP+FP Kontroly (-) FN TN FN+TN TP+FN FP+TN Senzitivita (sensitivity) Specificita (specificity) Prediktivní hodnota pozitivního testu = přesnost (precision) TP / (TP+FN) TN / (FP+TN) Celková správnost (accuracy) (TP+TN)/(TP+FP+FN+TN) ‖TP / (TP+FP) Chyba (error) (FP+FN)/(TP+FP+FN+TN) © Institut biostatistiky a analýz PŘÍKLAD – KLASIFIKACE POMOCÍ LDA 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 Přesnost: TP/(TP+FP)=2/(2+1)=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 © Institut biostatistiky a analýz INTERVALY SPOLEHLIVOSTI PRO CHYBU þ chyba: 𝐹𝐹+𝐹𝑁 𝑇𝑇+𝐹𝐹+𝐹𝐹+𝑇𝑇 = 𝑁 𝑒𝑒𝑒𝑒𝑒 𝑁 þ 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ˆ © Institut biostatistiky a analýz INTERVALY SPOLEHLIVOSTI PRO CELKOVOU SPRÁVNOST þ celková správnost: 𝑇𝑇+𝑇𝑁 𝑇𝑇+𝐹𝐹+𝐹𝐹+𝑇𝑇 = 1 − 𝑁 𝑒𝑒𝑒𝑒𝑒 𝑁 þ 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í: ( ) ( ) ú ú û ù ê ê ë é - ×+ - ×- N PP P N PP P AA A AA A ˆ1ˆ 96.1ˆ, ˆ1ˆ 96.1ˆ © Institut biostatistiky a analýz PŘÍKLAD – POKRAČOVÁNÍ ( ) ( ) ú ú û ù ê ê ë é - ×+ - ×- 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: © Institut biostatistiky a analýz 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) q k-násobná (k-fold) q „odlož-jeden-mimo“ (leave-one-out, jackknife) © Institut biostatistiky a analýz 1. RESUBSTITUCE þ stejná trénovací a testovací množina þ výhody: + jednoduchá + rychlá þ nevýhody: - příliš optimistické výsledky © Institut biostatistiky a analýz 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 © Institut biostatistiky a analýz 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 © Institut biostatistiky a analýz 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: - výsledek stále hodně závislý na výběru trénovacích dat (i když trochu méně než předtím) - při malých souborech může být polovina dat pro trénování příliš málo trénovací data testovací data testovací data trénovací data © Institut biostatistiky a analýz 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 þ 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... © Institut biostatistiky a analýz 4. KŘÍŽOVÁ VALIDACE (CROSS VALIDATION, CV) þ používán též název příčná validace þ obecně: k-násobná (k-fold) křížová validace þ speciální případ: „odlož-jeden-mimo“ (leave-oneout = jackknife) křížová validace © Institut biostatistiky a analýz 4A. k-NÁSOBNÁ KŘÍŽOVÁ VALIDACE (k-FOLD CROSS VALIDATION) þ 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í) þ výhody: + testovací sady se nepřekrývají + poměrně přesný odhad úspěšnosti klasifikace þ nevýhody: - trénovací sady se překrývají - časově náročné 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í © Institut biostatistiky a analýz 4B. „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 N-1 subjektů na trénování) þ platí výhody a nevýhody zmíněné u k-násobné křížové validace se třemi komentáři: qčasově nejnáročnější ze všech možných k qvelmi vhodná pro malé soubory dat qv některých článcích se uvádí, že lehce nadhodnocuje úspěšnost → doporučuje se 10-násobná křížová validace © Institut biostatistiky a analýz pacient kontrola kontrola kontrola pacient kontrola PŘÍKLAD – “ODLOŽ-JEDEN-MIMO” KŘÍŽOVÁ VALIDACE 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 Senzitivita: 1/(1+2)=0.33 Specificita: 2/(1+2)=0.67 Přesnost: 1/(1+1)=0.50 Správnost: (1+2)/(1+1+2+2)=0.50 Chyba: (1+2)/(1+1+2+2)=0.50 Iterace: Výsledek klasifikace: pacient kontrola kontrola kontrola pacient kontrola © Institut biostatistiky a analýz JE KLASIFIKACE LEPŠÍ NEŽ NÁHODNÁ KLASIFIKACE? þ permutační testování þ jednovýběrový binomický test © Institut biostatistiky a analýz 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! PA0.5 → © Institut biostatistiky a analýz 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 © Institut biostatistiky a analýz 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) © Institut biostatistiky a analýz SROVNÁNÍ ÚSPĚŠNOSTI KLASIFIKACE þ Srovnání 2 klasifikátorů þ Srovnání 3 a více klasifikátorů © Institut biostatistiky a analýz SROVNÁNÍ 2 KLASIFIKÁTORŮ 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 = 𝑁𝑡𝑡 © Institut biostatistiky a analýz SROVNÁNÍ 2 KLASIFIKÁTORŮ - PŘÍKLAD Lineární diskriminační analýza (LDA) Metoda 9 nejbližších sousedů (9-nn) © Institut biostatistiky a analýz SROVNÁNÍ 2 KLASIFIKÁTORŮ - PŘÍKLAD 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ů: © Institut biostatistiky a analýz SROVNÁNÍ 3 A VÍCE KLASIFIKÁTORŮ 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. © Institut biostatistiky a analýz SROVNÁNÍ 3 A VÍCE KLASIFIKÁTORŮ - PŘÍKLAD 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 © Institut biostatistiky a analýz 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 © Institut biostatistiky a analýz Příprava nových učebních materiálů oboru Matematická biologie je podporována projektem ESF č. CZ.1.07/2.2.00/07.0318 „VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ