© Institut biostatistiky a analýz
Analýza a klasifikace dat –
přednáška 7
RNDr. Eva Koriťáková
Podzim 2016
Hodnocení úspěšnosti klasifikace
a srovnání klasifikátorů
2Koriťáková: Analýza a klasifikace dat
Hodnocení úspěšnosti klasifikace - úvod
3Koriťáková: 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
4Koriťáková: 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
5Koriťáková: 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
6Koriťáková: 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
   







 



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:
𝑇𝑃+𝑇𝑁
𝑇𝑃+𝐹𝑃+𝐹𝑁+𝑇𝑁
7Koriťáková: Analýza a klasifikace dat
• z toho plyne: ෠𝑃𝐴 =
𝑁 𝑐𝑜𝑟
𝑁
(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í
8Koriťáková: Analýza a klasifikace dat
 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
IS pro správnost:
Správnost: (TP+TN)/(TP+FP+FN+TN) = 0,67
Trénovací a testovací data
9Koriťáková: 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
10Koriťáková: 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)
11Koriťáková: 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)
12Koriťáková: 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
13Koriťáková: 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
14Koriťáková: 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...
15Koriťáková: 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
16
• 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í)
Koriťáková: Analýza a klasifikace dat
Příklad - „odlož-jeden-mimo“ křížová validace
17Koriťáková: 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í !!!
18
Postup 1 je nesprávný, je potřebné rozdělit soubor na trénovací a testovací ještě
před redukcí dat, jinak dostaneme nadhodnocené výsledky!!!
Data
Předzpra-
cování
Redukce
Klasifikace
Trénovací
data
Testovací
data
Naučení
klasifikátoru
Data
Předzpra-
cování
Redukce
Klasifikace
Trénovací
data
Testovací
data
Naučení
klasifikátoru
Postup 1:
Postup 2:
Redukce
Koriťáková: Analýza a klasifikace dat
Je klasifikace lepší než náhodná klasifikace?
• permutační testování
• jednovýběrový binomický test
19Koriťáková: 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)
20
PA0,5
→
Koriťáková: Analýza a klasifikace 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 (v případě vyrovnaných skupin), máme v algoritmu zřejmě
někde chybu!
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
21Koriťáková: Analýza a klasifikace dat
Příklad – jednovýběrový binomický test
• 𝑧 =
𝑃 𝐴−𝑃 𝐴0
Τ𝑃 𝐴0 1−𝑃 𝐴0 𝑁
=
0,67−0,5
Τ0,5 1−0,5 6
= 0,83
22Koriťáková: Analýza a klasifikace dat
• uvažujme např. výsledek klasifikace pacientů a kontrol pomocí LDA
(pomocí resubstituce): 𝑃𝐴 = 0,67, 𝑁 = 6, 𝑃𝐴0
= ൗ𝑁 𝑖
𝑁 = 0,5
• 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)
• 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
Srovnání úspěšnosti klasifikace
• Srovnání 2 klasifikátorů
• Srovnání 3 a více klasifikátorů
23Koriťáková: Analýza a klasifikace dat
Srovnání 2 klasifikátorů
24
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 = 𝑁𝑡𝑠
Koriťáková: Analýza a klasifikace dat
Příklad – srovnání 2 klasifikátorů
25
Lineární diskriminační
analýza (LDA)
Metoda 9 nejbližších
sousedů (9-nn)
Koriťáková: Analýza a klasifikace dat
Příklad – srovnání 2 klasifikátorů
26
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ů:
Koriťáková: Analýza a klasifikace dat
Srovnání 3 a více klasifikátorů
27
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.
Koriťáková: Analýza a klasifikace dat
Příklad – srovnání 3 a více klasifikátorů
28
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
Koriťáková: 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
29Koriťáková: Analýza a klasifikace dat
30Koriťáková: 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“