PA081: Programování numerických výpočtů
8. Analýza hlavních komponent
Trocha statistiky
Ještě trocha statistiky
Aleš Křenek a Jan Fousek
jaro 2013
Úvodní příklad
PA081: Programování numerických
výpočtů
A. Křenek, J. Fousek
do zemské atmosféry proletěl velký meteorit
ještě před dopadem explodoval a rozpadl se na mnoho úlomků
na zemi najdeme jen část z nich
je třeba určit
► jak velký byl průměr shluku úlomků před dopadem
► pod jakým úhlem meteorit dopadl
► jakým směrem letěl
□     s   4 :
Trocha statistiky
Ještě trocha statistiky
■O0.O
2/23
Obecná motivace
► soubor opakovaného měření nějakého jevu apod.
► pro každý prvek souboru více měřených hodnot -n rozměrný prostor
► hledáme nezávislé (kolmé) směry zodpovědné za proměnlivost hodnot
Obecná motivace
A. Křenek, J. Fousek
soubor opakovaného měření nějakého jevu apod.
► pro každý prvek souboru více měřených hodnot -n rozměrný prostor
► hledáme nezávislé (kolmé) směry zodpovědné za proměnlivost hodnot
v případě dopadu meteoritu
► zaznamenáme souřadnice nálezu úlomků
► směr největšího rozptylu určuje směr dopadu
► rozptyl nejmenší ze všech směrů určuje poloměr shluku
► poměr rozptylu ve směru dopadu a v kolmém směru odpovídá úhlu dopadu
Trocha statistiky
Ještě trocha statistiky
3/23
Analýza hlavních komponent
Principal Component Analysis (PCA)
hledá nezávislé hlavní směry zodpovědné za proměnlivost dat a určuje jejich relativní význam
některé směry nemají žádný nebo minimální význam
► více veličin než prvků souboru (např. pixely obrázku)
► významné závislosti v celém jevu
► PCA je dokáže identifikovat-redukce počtu dimenzí
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
Trocha statistiky
► náhodná veličina, soubor vzorků, ...
► viz základní kursy statistiky
► střední (očekávaná) hodnota náhodné veličiny X
EX = x = iix
1 N
N
i=l
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
Trocha statistiky
► náhodná veličina, soubor vzorků, ...
► viz základní kursy statistiky
► střední (očekávaná) hodnota náhodné veličiny X
EX = x = nx
1 N
N
i=l
rozptyl (variance)
var(X)
N
1 N
— X(xt-EX)2 i=l
vystihuje, jak moc jsou prvky souboru vzdáleny od střední hodnoty
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
■O0.O
Trocha statistiky
kovariance
► zobecnění rozptylu na vzájemný vztah dvou veličin
cov(X, Y) =
N
1 N
■EX)(yt-EY)
malý rozptyl v jedné veličině (rozložení vzorku podél druhé osy) kovarianci zmenšuje bez ohledu na chování druhé veličiny
současný výskyt (x,y) a (x, -y) se ruší
nejvyšší absolutní hodnota při lineární závislosti X = ±Y
triviálně cov(X,X) = var(X) a cov(X, Y) = cov(Y,X)
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
Trocha statistiky
jednoduchý příklad graficky
•—		> —•
		
		
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
□      (5    4 :
7/23
Trocha statistiky
jednoduchý příklad graficky
matice kovariance veličin X\,..., Xn
(    var(Xi) cov(X1,X2) cov(X2, Xi)      var(X2)
V coviX^X^) cov(Xn,X2)
COV(XuXn) \
cov(X2,Xn) var(Xn) J
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
7/23
PCA formálněji
► prvky analyzovaného souboru chápeme jako vektory v n-rozměrném prostoru
► hledáme souřadný systém, jehož bázové vektory jsou hlavní směry daného souboru
► tedy kovariance mezi různými veličinami jsou nulové
► matice kovariance je diagonální
2 = VAVr
► 2 je symetrická, proto jsou A; reálné a V ortogonální
► V lze volit tak, že A; jsou uspořádány od největší
Aplikace - rozpoznávání tváří
► prvky souboru jsou normalizované fotografie
► stejné rozlišení
► obličej zabírá (přibližně) stejné pixely
► pozadí je vždy stejné
► černá a bílá odpovídá stejným hodnotám
► proměnné (složky vektoru) jsou jednotlivé pixely
► tj. obrázek 256 x 256 znamená 65536 proměnných
► datová matice Djvxn - N obrázků o n pixelech
Aplikace - rozpoznávání tváří
vycentrování dat
► spočteme „průměrný obrázek" /j (průměr každého sloupce - pixelu)
1 N
fc=0
► odečteme od datové matice uy = dij - lij matice kovariance
1 T ž-nxn = J^j     j"U U
PA081: Programování numerických
výpočtů
A. Křenek, J. Fousek
Úvod
Trocha statistiky
Rozpoznávání tváří
Domácí úkol
Ještě trocha statistiky
Zpracování dat fMRI
► U je centrovaná datová matice
►jen maticový zápis definice kovariance
Aplikace - rozpoznávání tváří
► výpočet vlastních hodnot 2
► přímočarý postup
► použijeme implementaci pro symetrické matice,
► aplikujeme na ^-j-UTU
► zbytečně „nafouklá" data (n » N)
Aplikace - rozpoznávání tváří
► výpočet vlastních hodnot 2
► přímočarý postup
► použijeme implementaci pro symetrické matice,
► aplikujeme na ^-j-UTU
► zbytečně „nafouklá" data (n » N)
► obrácený rozklad UUr = V'A'V'r
► vynásobení V' zprava, UT zleva a ozávorkování
UrU(UrV) = (UTV')A'
► tedy UrV jsou vlastní vektory 2 = UTU
► A' jsou její vlastní hodnoty
► ostatní vlastní hodnoty jsou nulové
► počítali jsme rozklad podstatně menší matice N x N
Aplikace - rozpoznávání tváří
► vlastní vektory 2 jsou „typické tváře"
► jsou vzájemně nezávislé
► charakterizují nějaké rysy tváří
► ne všechny jsou stejně významné
► přispívají k variabilitě vstupu úměrně velikosti vlastních hodnot
► zvolíme (experimentálně) prahovou hodnotu 0 < a < 1 (např. 0.95)
► uvažujeme pouze Ai,..., Am tak, že
Úvod
Trocha statistiky
Rozpoznávání tváří
Domácí úkol
Ještě trocha statistiky
Zpracování dat ÍMRI
Shrnutí
m N
1 Ai = a- X A,
í=i í=i
► ostatní Am+i,..., Ajv zanedbáme
► typicky pro rozumně velký počet N platí m <šc N
Aplikace - rozpoznávání tváří
každý obrázek p lze reprezentovat souřadnicemi v prostoru PCA
p' = Vr(p-AO
► přitom posledních n-m komponent p' lze zanedbat
► lze použít k výrazné kompresi
rozpoznání neznámé tváře
► spočteme p' pro všechny vstupní obrázky
► spočteme p' pro neznámý vstup
► hledání nejbližšího prvku provedeme pouze v m dimenzích
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
□     s   4 :
■OQ.O
13/23
Domácí úkol
implementujte popsanou metodu rozpoznávání tváří použijte fotografie kamarádů/spolužáků z IS MU
► jsou přijatelně uniformní
► převeďte na černobílou, snažte se dosáhnout stejnoměrného jasu
vyzkoušejte účinnost na jiných fotografiích stejných lidí
zjistěte, jaké rysy tváře hlavní komponenty postihují
► zvolíme libovolné hodnoty prvních m souřadnic, p' doplníme nulami
► provedeme zpětnou transformaci na obrázek
p = Vp' + ij
pracujte i týmově, výsledky můžete předvést na některé z příštích přednášek
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
□     s   4 :
■OQ.O
Ještě trocha statistiky
praktické nevýhody kovariance
► závislost na absolutní hodnotě veličin
► neintuitivní jednotky (m2 v úvodním příkladu, ale např kgm, kdybychom uvažovali také hmotnost úlomku)
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
Ještě trocha statistiky
praktické nevýhody kovariance
► závislost na absolutní hodnotě veličin
► neintuitivní jednotky (m2 v úvodním příkladu, ale např kgm, kdybychom uvažovali také hmotnost úlomku)
zavádíme pojem korelace corriX, Y) --
cov(X, Y) ^var(X)var(Y)
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
► existuje více podob, toto je nejběžnější tzv. „Pearsonova"
► nadále vypovídá o vztahu veličin
► je normovaná do intervalu [-1,1] a bez jednotek
► ±1 - plná lineární závislost, 0 - zcela nezávislé
PCA provádíme obdobně na korelační matici
► numericky potenciálně lepší vlastnosti kvůli rovnoměrnému škálování
► zpravidla stejně převáží nepoměr vlastních hodnot:-(
Zpracování dat fMRI
funkční magenetická rezonance 3D diagnostická metoda funkce mozku
► založena na NMR - rezonance atomových jader v magnetickém poli
► v různém chemickém kontextu různé spektrum
► specificky fMRI detekuje množství okysličené krve
výstupní data
► 3D struktura voxelů, typicky desítky až stovky v jednom rozměru
► v každém voxelu jedna skalární hodnota
► série desítek až stovek takových snímků
použití PCA
► detekce vzorů chování bez apriorního zavedení nějakého modelu
► upozorní na artefakty v datech, které by jinak zkreslovaly další analýzu
► může napovědět, jaký funkční model zvolit
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
Zpracování dat fMRI
► zpracovávaná data
► série desítek až stovek 3D snímků
► každý desítky až stovky voxelů ve všech dimenzích
► zpravidla ruční výběr zpracovávané oblasti
Zpracování dat fMRI
A. Křenek, J. Fousek
zpracovávaná data
► série desítek až stovek 3D snímků
► každý desítky až stovky voxelů ve všech dimenzích
► zpravidla ruční výběr zpracovávané oblasti
prostorová korelace
► matice korelace z UTU (odpovídá rozpoznávání tváří)
► voxely jsou nezávislé náhodné veličiny
► snímky chápeme jako jednotlivá pozorování
► vysoká korelace - voxely se v čase chovají na sobě závisle
► významnější vlastní vektory - reprezentativní snímky, z nichž dokážeme ostatní poskládat
Trocha statistiky
Ještě trocha statistiky
17/23
Zpracování dat fMRI
A. Křenek, J. Fousek
časová korelace
► (podstatně méně intuitivní)
► matice korelace z UUT
► body v čase jsou nezávislé náhodné veličiny
► voxely jsou jednotlivá místa jejich pozorování
► poloha bodu v prostoru vypovídá o jeho chování v čase
► významné vlastní vektory - reprezentativní vzory chování voxelů
Trocha statistiky
Ještě trocha statistiky
Zpracování dat fMRI
série 120 snímků mozku
nej významnější komponenty časové korelace
Temporal components (sd, % variance explained)
-0.68, 46.9% -
0.29, 8 6% -
-$.17, 2 9%
60 80 Frame
A. Křenek, J. Fousek
Trocha statistiky
Ještě trocha statistiky
první zachycuje zjevně artefakt na začátku snímání
□       4 (5 ►   4 = ►   < -E ►
Zpracování dat fMRI
► stejný efekt je patrný na prostorových hlavních komponentách
Spatial components
Slice (0 based)
► červené oblasti označují vzájemně závislé voxely
► sklon chovat se v čase stejně
► představte si na 3 voxelech, rozmístění 120 bodů odpovídajících snímkům v prosotoru, a vektorech hlavních komponent
► 1. komponenta: artefakt měření je v krajích a ve svislé ose
Zpracování dat fMRI
ze souboru odstraníme prvních několik snímků
Temporal components (sd, % variance explained)
první komponenta ukazuje už jasný lineární trend další jsou víceméně pravidelné oscilace
Zpracování dat fMRI
► hlavní komponenty prostorových korelací
► červená (resp. modrá) znamená voxely, které definují danou komponentu
► variabilita v čase v konkrétním hlavním směru je dána těmito voxely
► směry jsou vzájemně nezávislé
► každý voxel je výrzně modrý nebo červený jen v jednom řádku
Shrnutí
A. Křenek, J. Fousek
analýza hlavních komponent
nalezení vzájemně nezávislých směrů variability vzorku identifikace jejich významu - snížení počtu dimenzí aplikace ve zpracování obrazu 2D - rozpoznávání tváří 3D - fMRI scany mozku
Trocha statistiky
Ještě trocha statistiky