© Institut biostatistiky a analýz Analýza a klasifikace dat – přednáška 9 RNDr. Eva Koriťáková, Ph.D. Selekce a extrakce proměnných • formální popis objektu původně reprezentovaný p-rozměrným vektorem se snažíme vyjádřit vektorem m-rozměrným tak, aby množství diskriminační informace bylo co největší • dva principiálně různé způsoby: 2 1. selekce – výběr těch proměnných, které přispívají k separabilitě klasifikačních tříd nejvíce 2. extrakce – transformace původních proměnných na menší počet jiných proměnných (které zpravidla nelze přímo měřit a často nemají zcela jasnou interpretaci) Koriťáková: Analýza a klasifikace dat x1 x2 x3 x4 x5 x6 x7 x8 … I1 pac. I2 pac. I3 kont. … proměnné subjekty x1 x2 x3 x4 x5 x6 x7 x8 … I1 pac. I2 pac. I3 kont. … proměnné subjekty y1 y2 y3 y4 I1 I2 I3 … Extrakce proměnných 3Koriťáková: Analýza a klasifikace dat • transformace původních proměnných na menší počet jiných proměnných  tzn. hledání (optimálního) zobrazení Z, které transformuje původní p-rozměrný prostor (obraz) na prostor (obraz) m-rozměrný (m ≤ p) • pro snadnější řešitelnost hledáme zobrazení Z v oboru lineárních zobrazení • 3 kritéria pro nalezení optimálního zobrazení Z: – obrazy v novém prostoru budou aproximovat původní obrazy ve smyslu minimální střední kvadratické odchylky → PCA – rozložení pravděpodobnosti veličin v novém prostoru budou splňovat podmínky kladené na jejich pravděpodobnostní charakteristiky → ICA – obrazy v novém prostoru budou minimalizovat odhad pravděpodobnosti chyby • metody extrakce proměnných (≈ metody ordinační analýzy): – analýza hlavních komponent (PCA) – faktorová analýza (FA) – analýza nezávislých komponent (ICA) – korespondenční analýza (CA) – vícerozměrné škálování (MDS) – manifold learning metody (LLE, Isomap atd.) – metoda parciálních nejmenších čtverců (PLS) Analýza nezávislých komponent 4Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent (ICA) 5 Nevýhody: - velmi časově náročná, předstupněm je redukce pomocí PCA - je třeba expertní znalost pro výběr komponent - nutnost stanovit počet komponent předem Výhody: + vícerozměrná metoda + dokáže vytvořit lépe interpretovatelné komponenty než PCA Princip: Hledání statisticky nezávislých komponent v původních datech. Koriťáková: Analýza a klasifikace dat Srovnání s analýzou hlavních komponent (PCA) 6 PCA y2 y1 x2 x1 y1 y2 Nevýhody: - nevyužívá informaci o příslušnosti subjektů do skupin - potřebné určit, kolik hlavních komponent se použije pro transformaci (avšak při změně počtu není nutné PCA přepočítat) Výhody: + vícerozměrná metoda Princip: Vytvoření nových proměnných (komponent) z původních proměnných tak, aby zůstalo zachováno co nejvíce variability. Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent • anglicky Independent Component Analysis (ICA) 7 x1(t) = a11.s1(t) + a12.s2(t) x2(t) = a21.s1(t) + a22.s2(t) • úloha spočívá v nalezení originálních neznámých signálů z jednotlivých zdrojů s1(t) a s2(t), máme-li k dispozici pouze zaznamenané signály x1(t) a x2(t) • ICA umožňuje určit koeficienty aij za předpokladu, že známé signály jsou dány lineárních kombinací zdrojových, a za předpokladu statistické nezávislosti zdrojů v každém čase t Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – model dat • mějme x = (x1,x2,…, xm), což je m-rozměrný náhodný vektor xi = ai1 orig.s1 orig + ai2 orig.s2 orig+…+aim orig.sm orig , i = 1,2,…,m nebo maticově x = Aorig.sorig sorig je vektor originálních skrytých nezávislých komponent a si orig jsou nezávislé komponenty (předpoklad vzájemně statisticky nezávislosti) Aorig je transformační matice 8Koriťáková: Analýza a klasifikace dat • skryté nezávislé komponenty je možno vyjádřit pomocí vztahu: s = W.x • cíl: nalézt lineární transformaci (koeficienty transformační matice W) tak, aby vypočítané nezávislé komponenty si byly vzájemně statisticky nezávislé (W = A-1) Analýza nezávislých komponent - omezení • pouze jedna originální nezávislá komponenta může mít normální rozložení pravděpodobnosti (pokud má více zdrojů normální rozložení, není ICA schopna tyto zdroje ze vstupních dat extrahovat) 9Koriťáková: Analýza a klasifikace dat • pro dané m-rozměrné obrazové vektory je ICA schopna najít pouze m nezávislých komponent • nelze obecně určit polaritu nezávislých komponent • nelze určit pořadí nezávislých komponent Analýza nezávislých komponent - omezení 10 • jsou identifikovány správné původní signály, ale pořadí signálů a jejich polarita je jiná než v původních datech Koriťáková: Analýza a klasifikace dat původní neznámé signály měřené signály signály identifikované pomocí ICA Odhad nezávislých komponent • optimalizace pomocí zvolené optimalizační (účelové, kriteriální, objektové) funkce  a) nalézt kriteriální funkci b) vybrat optimalizační algoritmus ad a) možnost ovlivnit statistické vlastnosti metody ad b) spojitá optimalizační úloha s „rozumnou“ kriteriální funkcí – gradientní metoda, Newtonova metoda – ovlivňujeme rychlost výpočtu (konvergenci), nároky na paměť,… 11Koriťáková: Analýza a klasifikace dat Odhad nezávislých komponent – základní úvaha • nechť existuje m nezávislých náhodných veličin s určitými pravděpodobnostními rozděleními (jejich součet za obecných podmínek konverguje s rostoucím počtem sčítanců k normálnímu rozdělení – tzv. centrální limitní věta); • o vektoru x (který máme k dispozici) předpokládáme, že vznikl součtem nezávislých komponent sorig 12Koriťáková: Analýza a klasifikace dat jednotlivé náhodné veličiny xi mají pravděpodobnostní rozdělení, které je „bližší“ normálnímu než rozdělení jednotlivých komponent si orig • používané míry „nenormality“: – koeficient špičatosti – negativní normalizovaná entropie – aproximace negativní normalizované entropie  Odhad nezávislých komponent – koeficient špičatosti kurt(s) = E{s4} – 3(E{s2}) 2 • Gaussovo rozložení má koeficient špičatosti roven nule, zatímco pro jiná rozložení (ne pro všechna) je koeficient nenulový • při hledání nezávislých komponent hledáme extrém, resp. kvadrát koeficientu špičatosti veličiny s = wi.x 13Koriťáková: Analýza a klasifikace dat • výhody: – rychlost a relativně jednoduchá implementace • nevýhody: – malá robustnost vůči odlehlým hodnotám (pokud v průběhu měření získáme několik hodnot, které se liší od skutečných, výrazně se změní KŠ a tím i nezávislé komponenty nebudou odhadnuty korektně) – existence náhodných veličin s nulovým KŠ, ale nenormálním rozdělením Odhad nezávislých komponent – NNE • Negativní normalizovaná entropie (NNE) = negentropy • Informační entropie - množství informace náhodné veličiny • pro diskrétní náhodnou veličinu s je: H(s) = -i P(s=ai).log2P(s=ai), kde P(s=ai) je pravděpodobnost, že náhodná veličina S je rovna hodnotě ai • pro spojitou proměnnou platí • entropie je tím větší, čím jsou hodnoty náhodné veličiny méně predikovatelné • pro normální rozd. má entropie největší hodnotu ve srovnání s dalšími rozd. • NNE: J(s) = H(sgauss) – H(s), kde sgauss je náhodná veličiny s normálním rozd. 14 p(s)dslogp(s).-H(s) 2 -     Koriťáková: Analýza a klasifikace dat • výhody: – přesné vyjádření nenormality – dobrá robustnost vůči odlehlým hodnotám • nevýhody: časově náročný výpočet  snaha o vhodnou aproximaci NNE, aby byly zachovány její výhody a současně byl výpočet méně náročný Odhad nezávislých komponent – aproximace NNE • použití momentů vyšších řádů kde s je náhodná veličina s nulovou střední hodnotou a jednotkovým rozptylem 15 223 )s(kurt 48 1 }s{E 12 1 J(s)  2 gaussii p 1i i )}]s(G{)}s(G{.[kJ(s) EE   )salog(cosh a 1 (s)G 1 1 1  )2/exp(-s(s)G 2 2  Koriťáková: Analýza a klasifikace dat • nevýhoda: – opět menší robustnost vůči odlehlým hodnotám • použití tzv. p-nekvadratických funkcí kde ki>0 je konstanta, Gi jsou šikovně navržené nelineární funkce a sgauss je normální náhodná proměnná, která spolu s s má nulovou střední hodnotu a jednotkový rozptyl. Je-li použita pouze jedna funkce G, pak je J(s)  [E{G(s)} - E{G(sgauss)}]2 • doporučuje se kde a11,2 nebo Analýza nezávislých komponent – příklad použití 16Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad použití 17Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad použití 18Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad použití 19Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad použití 20Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad 2 • Zadání: určete nezávislé komponenty ve fMRI datech zdravých subjektů, u nichž byl proveden vizuomotorický test. 21 • Řešení (s pomocí GIFT toolboxu v software MATLAB) Koriťáková: Analýza a klasifikace dat http://mialab.mrn.org/software/gift/ Celkem 14 implementovaných ICA algoritmů v GIFT toolboxu: o Infomax o FastICA o Erica o Simbec o Evd o Jade Opac o Amuse o SDD ICA o Semi-blind Infomax o Constrained ICA (Spatial) o Radical ICA o Combi o ICA-EBM o FBSS Analýza nezávislých komponent – příklad 3 • Zadání: nalezněte nezávislé komponenty, které dokáží odlišit tři skupiny subjektů 22 #N Age* [years] Gender F / M Education* [years] HC 57 68 (47 – 81) 40 / 17 16 (12 – 21) ADmci 27 69 (52 – 86) 17 / 10 13 (10 – 22) AD 12 75 (55 – 88) 11 / 1 12 (8 – 25) V1 V2 … S1 S2 … subjekty voxely * Datová matice V1 V2 … K1 K2 ... = K1 K2 ... S1 S2 … subjekty komponenty voxely komponenty Mixing matice Source matice pro nalezení odlišujících komponent pro vizualizaci Koriťáková: Analýza a klasifikace dat Analýza nezávislých komponent – příklad 3 23Koriťáková: Analýza a klasifikace dat • komponenta č. 1: p = 0.0052 komponenta č. 1 ukazuje místa, kde je úbytek šedé hmoty v ADmci a v AD, nicméně v AD větší Analýza nezávislých komponent – příklad 3 24Koriťáková: Analýza a klasifikace dat • komponenta č. 2: komponenta č. 2 ukazuje místa, kde je úbytek šedé hmoty v ADmci a AD víceméně stejný p = 0.0089 Analýza nezávislých komponent – příklad 3 25Koriťáková: Analýza a klasifikace dat • komponenta č. 6: komponenta č. 6 ukazuje místa, kde je úbytek šedé hmoty pouze u AD p = 0.0126 Selekce proměnných 26Koriťáková: Analýza a klasifikace dat Selekce a extrakce proměnných • formální popis objektu původně reprezentovaný p-rozměrným vektorem se snažíme vyjádřit vektorem m-rozměrným tak, aby množství diskriminační informace bylo co největší • dva principiálně různé způsoby: 27 1. selekce – výběr těch proměnných, které přispívají k separabilitě klasifikačních tříd nejvíce 2. extrakce – transformace původních proměnných na menší počet jiných proměnných (které zpravidla nelze přímo měřit a často nemají zcela jasnou interpretaci) Koriťáková: Analýza a klasifikace dat x1 x2 x3 x4 x5 x6 x7 x8 … I1 pac. I2 pac. I3 kont. … proměnné subjekty x1 x2 x3 x4 x5 x6 x7 x8 … I1 pac. I2 pac. I3 kont. … proměnné subjekty y1 y2 y3 y4 I1 I2 I3 … Selekce proměnných • cílem je výběr proměnných, které jsou nejužitečnější pro další analýzu (např. při klasifikaci výběr takových proměnných, které nejlépe od sebe dokáží oddělit skupiny subjektů/objektů) 28 • metod selekce je velké množství, nejpoužívanější metody jsou: – výběr proměnných na základě statistických testů – výběr oblastí mozku (ROI) podle atlasu – algoritmy sekvenční selekce (dopředné či zpětné; algoritmus plus p mínus q; algoritmus min-max) – algoritmus ohraničeného větvení Koriťáková: Analýza a klasifikace dat Výběr proměnných na základě statistických testů 29 Nevýhody: - jednorozměrná metoda (výběr proměnných bez ohledu na ostatní proměnné) - potřeba použít metody korekce pro mnohonásobné testování (např. FDR) Výhody: + rychlé + u obrazů mozku výhodou, že je analýza provedena na celém mozku x1 x2 x3 x4 x5 x6 x7 x8 … I1 pac. I2 pac. I3 kont. I4 pac. I5 kont. … proměnné subjekty p-hodnoty: Princip: Výběr statisticky významných proměnných pomocí dvouvýběrového t-testu či Mannova-Whitneyova testu (když máme 2 skupiny subjektů). 0,34 0,02 0,09 0,01 0,25 0,63 0,03 0,12 Koriťáková: Analýza a klasifikace dat Výběr oblastí mozku (ROI) podle atlasu 30 Nevýhody: - ne vždy dopředu víme, která z oblastí je vhodná pro odlišení skupin osob - některá onemocnění postihují celý mozek (např. schizofrenie) Výhody: + anatomicky/funkčně relevantní – snadnější interpretace + zpravidla rychlé Princip: Výběr oblastí mozku s využitím atlasu mozku podle expertní znalosti daného onemocnění (tzn. výběr oblasti postižené danou nemocí). Koriťáková: Analýza a klasifikace dat Algoritmy sekvenční selekce • výběr optimální podmnožiny obsahující m (m  p) proměnných – kombinatorický problém – p!/(p-m)!m! možných řešení! 31 • předpoklad: monotónnost kritéria selekce – označíme-li Xj množinu obsahující j proměnných, pak monotónnost kritéria znamená, že pro podmnožiny X1  X2  …  Xj  …  Xm splňuje selekční kritérium vztah J(X1)  J(X1)  …  J(Xm) Koriťáková: Analýza a klasifikace dat • tedy: je nutno seřadit proměnné podle toho, jak dobře dokáží diskriminovat trénovací data  hledáme jen kvazioptimální řešení • např. výběr 10 proměnných z 20: 400286221335 !10!10 !20 !)!( !     mmp p Algoritmy sekvenční selekce • algoritmus sekvenční dopředné selekce: – algoritmus začíná s prázdnou množinou, do které se vloží proměnná s nejlepší hodnotou selekčního kritéria – v každém následujícím kroku se přidá ta proměnná, která s dříve vybranými veličinami dosáhla nejlepší hodnoty kritéria, tj. J({Xk+1})=max J({Xkyj}), yj {Y-Xk} 32 • algoritmus sekvenční zpětné selekce: – algoritmus začíná s množinou všech proměnných – v každém následujícím kroku se eliminuje ta proměnná, která způsobuje nejmenší pokles kriteriální funkce, tj. J({Xm-k-1})=max J({Xm-k-yj}), yj {Xm-k} - dopředná selekce – nelze vyloučit ty veličiny, které se staly nadbytečné po přiřazení dalších veličin - zpětná selekce – neexistuje možnost opravy při neoptimálním vyloučení kterékoliv proměnné + dopředný algoritmus je výpočetně jednodušší, protože pracuje maximálně v m-rozměrném prostoru + zpětný algoritmus umožňuje průběžně sledovat množství ztracené informace Výhody : Nevýhody : Koriťáková: Analýza a klasifikace dat Algoritmus plus p mínus q • po přidání p proměnných se q proměnných odstraní • proces probíhá, dokud se nedosáhne požadovaného počtu proměnných • je-li p>q, pracuje algoritmus od prázdné množiny • je-li p