Analýza a klasifikace dat - přednáška 7 MU RNDr. Eva Janousova IBA » Podzim 2015 Schéma analýzy a klasifikace dat Předzpracování I _____________i Redukce I _____________i Klasifikace Ukázka - kognitivní data apod. A B C D E 1 id vek pohlaví výska vaha 2 l 38 Z 164 45 3 2 36 M 90 4 3 26 Z 17S 70 A B D E 1 id vek pohlaví výska vaha 2 l 35 Z 164 45 3 2 36 M 167 90 4 3 26 Z 17S 70 B c D A 1 id vek pohlaví výska vaha 2 1 3s|z 164 45 2 36 Im 167 90 4 3 25 Z 1 17S 70 1 L__________ _____________________________P nebo Ukázka - obrazová data r. . Janoušová: Analýza a klasifikace dat IBA M 2 Proč používat redukci dat? Obrazová data Klasifikace X voxely ■ ■ ■ subjekty h • • • 270 x 1 000 000 subjekty \ • • • pac. kon. MU Janoušová: Analýza a klasifikace dat (^J Proč používat redukci dat? Obrazová data X -t—> 2b_í-L voxely 270 x 1 000 000 -t—> voxely ■■ ■ h • • • 270 x 1 000 -t—> h • • • pac. kon. MU Janoušová: Analýza a klasifikace dat (^J Proč používat redukci dat? )- • zjednodušení další práce s daty • možnost použití metod analýzy dat, které by na původní data nebylo možno použít • umožnění vizualizace vícerozměrných dat - může být nápomocné k nalezení vztahů v datech či k jejich interpretaci • redukce dat může být i cílem analýzy (např. identifika ce oblastí mozku, kde se nejvíce liší od sebe liší skupiny subjektů) MU Janoušová: Analýza a klasifikace dat |yj 5 Volba a výběr proměnných - úvod • počáteční volba proměnných je z velké části empirická, vychází ze zkušeností získaných při empirické klasifikaci člověkem a závisí kromě rozboru podstaty problému i na technických (ekonomických) možnostech a schopnostech hodnoty proměnných určit • kolik a jaké proměnné? - málo proměnných - možná nízká úspěšnost klasifikace či jiných analýz - moc proměnných - možná nepřiměřená pracnost, vysoké náklady KOMPROMIS (určit ty proměnné, jejichž hodnoty nesou nejvíce informace z hlediska řešené úlohy, tj. např. ty proměnné, kterou jsou nejefektivnější pro vytvoření co nejoddělenějších klasifikačních tříd) MU Janoušová: Analýza a klasifikace dat (yj 6 Zásady pro volbu proměnných I výběr proměnných s minimálním rozptylem uvnitř tříd ~H-^A í. Z. 2- 1 x3£. xtmm ^imŕut výběr proměnných s maximální vzdáleností mezi třídami P<*3> i -i-Xa § Janoušová: Analýza a klasifikace dat /BA (Ml 7 Zásady pro volbu proměnných II • výběr vzájemně nekorelovaných proměnných - pokud jsou hodnoty jedné proměnné závislé na hodnotách druhé proměnné, pak použití obou těchto proměnných nepřináší žádnou další informaci pro správnou klasifikaci výběr proměnných invariantních vůči deformacím - volba elementů formálního popisu závisí na vlastnostech původních i předzpracovaných dat a může ovlivňovat způsob předzpracování 0 A A A B B A ! A A A Janoušová: Analýza a klasifikace dat IBA W 8 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 obsažené v původním vektoru bylo v co největší míře zachováno • dva principiálně různé způsoby: 1. selekce - výběr těch proměnných, které přispívají k separabilitě klasifikačních tříd nejvíce yi r Ví . —— —j *1 , HLASIFIKATOE. X - - 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) *1 S5M5LO(t Z(y) CLASIFIKÁTOt y* , 03r MU Janoušová: Analýza a klasifikace dat (^J Extrakce proměnných )- • 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) - ... Janoušová: Analýza a klasifikace dat *|L jyj Metody ordinační analýzy - opakování • analýza hlavních komponent, faktorová analýza, korespondenční analýza a vícerozměrné škálování se snaží zjednodušit vícerozměrnou strukturu dat výpočtem souhrnných os • metody se liší v logice tvorby těchto os - maximální variabilita (analýza hlavních komponent, korespondenční analýza) - maximální interpretovatelnost os (faktorová analýza) - převod asociační matice do Euklidovského prostoru (vícerozměrné škálování) • redundanční analýza a kanonická korelační analýza se snaží nalézt vztah mezi dvěma sadami vícerozměrných dat MU Janoušová: Analýza a klasifikace dat |yj H Analýza hlavních komponent Janoušová: Analýza a klasifikace dat Analýza hlavních komponent-opakování • anglicky Principal component analysis (PCA) • snaha redukovat počet proměnných nalezením nových latentních proměnných (hlavních komponent) vysvětlujících co nejvíce variability původních proměnných • nové proměnné (y^ y2) lineární kombinací původních proměnných (x^ x2) • předpoklad: kvantitativní proměnné s normálním rozdělením MU Janoušová: Analýza a klasifikace dat |yj 13 Postup PCA-opakování 1. Volba asociační matice (autokorelační, kovarianční nebo kor. koeficientů) 2. Výpočet vlastních čísel a vlastních vektorů asociační matice: - vlastní vektory definují směr nových faktorových os (hlavních komponent) v prostoru - vlastní čísla odrážejí variabilitu vysvětlenou příslušnou komponentou 3. Seřazení vlastních vektorů podle hodnot jim odpovídajících vlastních čísel (sestupně) 4. Výběr prvních m komponent vyčerpávajících nejvíce variability původních dat MU Janoušová: Analýza a klasifikace dat |yj 14 Identifikace optimálního počtu hlavních komponent pro další analýzu )- • pokud je cílem ordinační analýzy vizualizace dat, snažíme se vybrat 2-3 komponenty • pokud je cílem ordinační analýzy výběr menšího počtu dimenzí pro další analýzu, můžeme ponechat více komponent (např. u analýzy obrazů MRI je úspěchem redukce z milionu voxelů na desítky) • kritéria pro výběr počtu komponent: 1. Kaiser Guttmanovo kritérium: - pro další analýzu jsou vybrány osy s vlastním číslem >1 (při analýze matice korelačních koeficientů) nebo větším než průměrná hodnota vlastních čísel (při analýze kovarianční matice) - logika je vybírat osy, které přispívají k vysvětlení variability dat více, než připadá rovnoměrným rozdělením variability 2. Sutinový graf (scree plot) - grafický nástroj hledající zlom ve vztahu počtu os a vyčerpané variability 3. Sheppardův diagram - grafická analýza vztahu mezi vzdálenostmi objektů v původním prostoru a redukovaném prostoru o daném počtu dimenzí MU Janoušová: Analýza a klasifikace dat *|L |yj 15 PCA - volba asociační matice • autokorelační matice - data nejsou nijak upravena (zohledňována průměrná hodnota i rozptyl původních dat) • kovarianční (disperzní) matice - data centrována (od každé proměnné odečtena její střední hodnota) - zohledňován rozptyl původních dat • matice korelačních koeficientů - data standardizována (odečtení středních hodnot a podělení směrodatnými odchylkami) - použití, pokud mají proměnné různá měřítka • každou úpravou původních dat ale přicházíme o určitou informaci!!! MU Janoušová: Analýza a klasifikace dat |yj 16 Analýza hlavních komponent-volba asociační matice )- • s jakými daty PCA pracuje v případě použití různých asociačních matic: původní data kovarianční matice (odečten průměr) autokorelační matice (data neupravována) matice korelačních koeficientů (odečten průměr a podělení SD) Janoušová: Analýza a klasifikace dat |yj 17 PCA-obecněji dáno K objektů (subjektů), k=l,...,K, charakterizovaných p proměnnými (objekty nejsou rozděleny do klasifikačních tříd) proměnné o Vj v2 ... vp xl • • • XK aproximujme nyní kterýkoliv obraz xk lineární kombinací m ortonormálních vektorů (m < p) m ckiei i=l koeficienty c^ lze považovat za velikost /-té souřadnice vektoru vyjádřeného v novém systému souřadnic s bází e/V i=l,2,...,m _ T Cki ~Xkei Janoušová: Analýza a klasifikace dat (J^J) 18 PCA - kritérium minimální střední kvadratické odchylky nalezení optimálního zobrazení pomocí kritéria minimální střední kvadratické odchylky: ^ 2 Z k = • vztah lze pomocí dříve uvedených vztahů upravit na: m i=l ki střední kvadratická odchylka pro všechny objekty x,, k=l,...,Kje: 1 K y K 2 m k=\ k=\ 1=1 1 Ä T Janoušová: Analýza a klasifikace dat IBA W 19 PCA - kritérium minimální střední kvadratické odchylky musíme zvolit bázový systém e, tak, aby střední kvadratická odchylka e2 byla minimální Zm , , , i=\Ckiei s bázovým systémem e,, optimálním podle kritéria minimální střední kvadratické chyby, nazýváme diskrétní Karhunenův- Loevův rozvoj střední kvadratická odchylka s2 = 1 K m Ktí 2-IX 7=1 k=\ 1 K -z T k=l je minimální, když je maximální výraz ^efK(x)ez9 kde *-(x) = —^x,.x 7=1 ^ k=l T k je autokorelační matice řádu m. Protože je symetrická a semidefinitní, jsou její vlastní čísla Áif i=l,...,m, reálná a nezáporná a vlastní vektory Vj, jsou buď ortonormální, neboje můžeme ortonormalizovat (v případě násobných vlastních čísel). Janoušová: Analýza a klasifikace dat IBA m 20 PCA - kritérium minimální střední kvadratické odchylky • uspořádáme-li vlastní čísla sestupně podle velikosti, tj. Ä1>Ä2>... >Am>0 a podle toho očíslujeme i odpovídající vlastní vektory, lze dokázat, výše uvedený výraz dosahuje maxima, jestliže platí e, = v,, \=l,...,m a pro velikost maxima je m m max^ef./r(x).e. =^A, i=\ 1=1 * pak pro minimální střední kvadratickou platí Km m p 1 _ _m _m _l = '.2>a2-2>,= (*(x)) - £ 4 = £ 4 ř'=l /=! i=m+\ min ^ it=l • minimální střední kvadratickou je tedy rovna součtu těch vlastních čísel, jimž odpovídající vlastní vektory nebyly použity při aproximaci objektu MU ,.....t Janoušová: Analýza a klasifikace dat J^j}} 21 PCA-vlastnosti Karhunenova-Loevova rozvoje • při daném počtu m členů rozvoje poskytuje ze všech možných aproximací nejmenší střední kvadratickou odchylku • při použití kovarianční matice jsou transformované souřadnice nekorelované; pokud se výskyt obrazů řídí normálním rozložením zajišťuje nekorelovanost i jejich nezávislost • vliv každého členu uspořádaného rozvoje se zmenšuje s jeho pořadím • změna požadavků na velikost střední kvadratické odchylky nevyžaduje přepočítávat celý rozvoj, nýbrž jen změnit počet jeho členů MU Janoušová: Analýza a klasifikace dat |yj 22 PCA-geometrická interpretace použití obou hlavních komponent PCA - rozdělení do tříd odečtení průměru každé skupiny zvlášt -> není vhodné (odlišení tříd jen podle rozptylu) yi odečtení celkového průměru čp f /'V** 0 J,--- ^----- -> je vhodné (neodstraňuje vliv středních hodnot obrazů v jednotlivých třídách ) Janoušová: Analýza a klasifikace dat IBA W 24 PCA a klasifikace PCA často nebývá vhodnou metodou redukce dat před klasifikací 25 PCA a klasifikace Když hlavní komponenta vyčerpává hodně variability, neznamená to, že musí rovněž dobře klasifikovat vysoká korelace mezi proměnnými 1 a 2 - způsobená tím, že se skupiny od sebe hodně liší \ # pacient • kontrola proměnná 1 -> v tomto případě obě proměnné budou korelovat s první hlavní komponentou a dokáží dobře diskriminovat pacienty a kontroly vysoká korelace mezi proměnnými 1 a 2 - skupiny se ale od sebe neliší proměnná 1 -> v tomto případě obě proměnné budou také korelovat s první hlavní komponentou, ale nedokáží diskriminovat pacienty a kontroly MU Janoušová: Analýza a klasifikace dat |yj 26 PCA - rozšiřující poznatky souvislost se singulárním rozkladem (SVD - Singular Value Decomposition): If — TT r vT - matice U a V jsou ortogonální a normované (ortonormální) - matice U složena z vlastních (charakteristických) vektorů matice XXT(n n) - matice V z vlastních vektorů matice XTX(pp) - Matice ľ je typu k x k a její diagonála je tvořena singulárními hodnotami, které jsou na hlavní diagonále uspořádány podle klesající velikosti a které jsou rovny odmocninám vlastních čísel matice XXTi XTX • výpočet PCA, když je p » n: - 1. způsob: iterativní postupný výpočet vlastních vektorů a vlastních čísel - 2. způsob: výpočet vlastních vektorů v; „velké'' kovarianční matice XTX(pp) z vlastních vektorů w; „malé'' kovarianční matice XXT(n n) takto: v,. = Xrw, MU Janoušová: Analýza a klasifikace dat |yj 27 PCA - příklad - řešení v Matlabu • Zadání: Proveďte PCA na objemech 6 mozkových struktur u 833 subjektů. • Řešení: [num, txt, raw] = xlsread('Data_neuro.xlsx',l); data = num(:,23:28); % vyber 6 proměnných s objemy mozkových struktur [coeff,score,latent] = pca(data); Souřadnice subjektů v novém prostoru Matice vlastních vektorů :core K | EB 833*6 double EB 6x6 double 1 2 3 4 5 6 1 2 3 4 5 6 1 -541.6758 322J0604 90.5446 94.2298 -249.6611 -273529 1 -0J0355 0.8886 -0.0485 01217 03093 -0.3103 2 -306.1072 508.2459 -423.5306 -204.0785 -40.5948 -148.3389 2 -0JD313 0.3748 -0.0956 0.2942 0.8661 0.1132 3 218.0346 473.6196 192.8200 -163.2062 323617 128.0769 3 0.0010 0.1000 0.9870 0.1023 0.0218 0.0702 4 -492.7048 535.5033 -267.8827 -74.2783 -56.0326 -351.3861 4 -0JM20 0.0560 -0.1046 0.9024 -03676 0.1903 5 -346.3904 240.7737 -312.9827 -106.9215 5J0059 32JS323 5 -0J0231 0.2331 -0.0580 -02714 -01363 05217 6 -123.1009 749.8831 -315.0017 -241.6806 53.2878 -46.0834 6 0.9985 0.0493 -0.0083 0.0094 0.0086 0.0160 7 -1.1798e+03 76.8159 -150.7726 321.9671 -182.4523 162.2400 8 -321.2074 8.9410 -2552537 151.7913 -36.5035 192.6580 vlastní vektory jsou ve sloupcích (jsou seřazené II 1 /IV/ 1 \ 9 -345.8090 464.1571 -374.4555 11.8603 -5.8649 91.6828 10 -1.4653&+03 697.7425 -380.2903 267.2337 -19.2383 -81.4055 hlavní komponenty jsou ve sloupcích (jsou seřazené podle vlastních čísel); v řádcích jsou subjekty Vlastní čísla Janoušová: Analýza a klasifikace dat latent K | EB 6x1 double 1 1 4J036Se+05 2 139O7e+05 3 7.0200e+04 4 4.1841e+04 5 4.0421e+04 6 3273Se+04 IBA W 28 PCA - příklad - řešení v softwaru Statistica I * Zadání: Proveďte PCA na objemech 6 mozkových struktur u 833 subjektů. * Řešení: Statistics - Multivariate Exploratory Techniques - Principal Components & Classification Analysis vybrat proměnné y Principal Components and Classification Analysis: Data_neuro Quick Advanced V £3 M OK l^J Variables: Variables for analysis: 23.28 Supplementary variables: none Variable with active cases: none Grouping variable (labeling): none Code for active cases: Analysis based on Compute variances (#) Correlations O Covariances (#) as SS/(N-1) G as SSM Cancel J&l Opt ions Open Data SELECT CňSÍS 1 MD deletion (#) Casewise Q Mean substitution zvolit, zda se má počítat kovarianční či korelační matice Janoušová: Analýza a klasifikace dat IBA W 29 PCA - příklad - řešení v softwaru Statistica II Matice vlastních vektorů Factop Principal Components and Clarification Analysis Results: Data_neuro He. c- active vara:5 He. cf active caaea: B33 He . cf supplements:: y ví:; : j He. e= aupplementary caaea: 0 Eigenvalues: 1,65764 1,05575 ,930953 ,959919 ,916125 Number of factors : ě ^ Quality of representation : löö.ö X Quick j Variables | Cases | Descriptives | OK Factor coordinates of cases Eigenvalues Plot var. factor coordinates, 2D Plot case factor coordinates, 2D £3 Scree plot Cancel JJŽŽ3 Opt ions 1 \É By Group on cc tions (Data_neLiro) Variable Factor 1 Factor 2/ r Factor 3 Factor 4 FabsO Factor 6 Hippocampus volume {mm3} -22,52921 -33>tf81 12 852 -24 9019 -62,176> v -56,1444 Amygdala_volume (mm3) -19,8762 09.756 25 334 60 1821 174,1211 20 4766 Thalamus volume [mm3) 0,6579- ' -37.303 -261 504 20 9163 4,38+1 12jtm Pallidum_volume [mm3) -20 868 27J07 184 5947 -73,9145 34 4372 Putamen volume [mm3} -86 934 15,376 -55 5188 -27 4129 166 7655 Nucl_caud_volume (mm3) ^634,4294 -18,367 2,210 1,9177 1,7198 2,9026 Souřadnice subjektů v novém prostoru Case Factor coordinates of cases, based on covariances (Data_neuro) Factor 1 Factor 2 Factor 3 Factor 4 Factor 5 Factor 6 1 -541,681 -322,060 -90 545 94,230 -249,661 -27,353 2 -306 1 1 -508 246 423 531 -204 078 -40 595 -148,339 3 218.03 -473 620 -192.820 -163 206 -82 362 128,077 4 492 70 -535 503 267 883 -74,278 -56 033 -351 386 5 -346 39 -240,774 312 983 -106 921 -5,006 32 832 6 -123.10 -749,883 315 002 -241 681 63 288 -46 083 7 -1179,78 -76,816 150 773 321 967 -182 452 162 240 8 -321 21 -8 941 255 254 151 791 -36 504 192 658 Vlastní čísla Eigenvalues of covariance m£ Active variables only Value number Eigenvalue % Total variance 1 403677,0 55 45440 2 139067,1| 19,10409 3 70200 2 9 64363 4 41840,7 5,74779 5 40421,1 5 55277 6 32737 9 4,49732 Janoušová: Analýza a klasifikace dat IBA M 30 PCA - příklad - řešení v softwaru Statistica III Normalizace vlastních vektorů: - zkopírovat do Excelu („Copy with headers") - použití vzorce: =B3/ODMOCNINA(SUMA.ČTVERCŮ(B$3:B$8)) m A B C D E F G i Factor coordinates of the variables, based on correlations (Data_neuro' 2 Variable Factor 1 Factor 2 Factor 3 Factor 4 Factor 5 Factor 6 3 Hippocami -22,5292 -331,381 12,852 -24,9019 -62,1764 -56,1444 4 Amygdala -19 -139,756 25 334 60,1821 174,1211 20,4766 5 Thalamus_ 0.6579 -37,303 -261,504 20,9163 4,3841 12,7030 6 Pallidum^ -7.6336 -20,868 27,707 184,5947 -73,9145 34,4372 7 Putamenj -14,6603 -86,934 15,376 -55,5188 -27,4129 166,7655 S Nucl_caud 634,4294 -18,367 2 210 1.9177 1,7198 2,9026 9 10 -0,035459125 -0,33362 0,043506 -0,12174 -0,30926 -0,3103 11 -0,031283533 -0,37477 0,095616 0,294217 0,366059 0,11317 12 C.CC1C35499 -0,10003 -0,93693 0,102255 0,021306 0,070207 13 -0,01201473 -0,05596 0,104572 0,902443 -0,36764 0,190323 14 -0,023074151 -0,23312 0,05 3032 -0,27142 -0,13635 0,921631 15 0,993542011 -0,04925 0,003341 0,009375 0,003554 0,016042 MU Janoušová: Analýza a klasifikace dat |yj 31 PCA - příklad - řešení v softwaru Statistica IV Záložka Variables: Factor & variable correlations Plot var. factor coordinates, 2D Variable Factor-variable correlations (factor loadinc s), Factor 1 Factor 2 Factor 3 Hippocampus volume (mm3} -0 0655501 -0.964180 0,037394 Amygdala_volume (mm3) -0,084808 -0,596314 0,1OSO95 Thalamus_volume [mm3) 0,002430 -0,140597 -0,985620 Pallidum_volume [mm3) 0,037255 -0,101845 0,135217 Putamen_volume [mm3) -0,073621 -0,436566 0,077214 Nucl caud volume (mm3) 0,999556 -0,028938 0,003482 Z výsledků vyplývá, že: - 1. hlavní komponenta je nevíce korelovaná s objemem Nucleus caudatus - 2. hlavní komponenta je korelovaná s objemem hipokampu a také s objemem amygdaly a putamenu D c- Projection of the variables on the factor-plane (1x2) 800 700 600 500 400 300 200 ľ 100 a Putarr en vojpme (mm3) aia_vdnume (mm3) -200 Hippöä&ijnpusjyolume (mm 3) ^100 -500 Nucl caud volume (mm^) -100 0 100 200 300 400 500 600 700 800 Factor 1 : 55,45% Janoušová: Analýza a klasifikace dat IBA M 32 Metody varietního učení (manifold learning) MU Janoušová: Analýza a klasifikace dat |yj 33 Úvod - redukce dimenzionality • klasické metody redukce dimenzionality: - PCA (principal component analysis) - snaha o nalezení „podstruktury" (embedding) v datech tak, aby byl zachován rozptyl - MDS (multidimensional scaling) - snaha o nalezení „podstruktury" v datech tak, aby byly zachovány vzdálenosti mezi body; ekvivalentní s PCA při použití Euklidovské vzdálenosti Swiss roll • tyto klasické metody redukce dimenzionality nedokáží zachytit složité nelineární struktury -> metody varietního učení Tenenbaum et al. 2000, Science Janoušová: Analýza a klasifikace dat *L (^J Metody varietního učení metody pro nelineární redukci a reprezentaci dat manifold = „nadplocha" - čáry a kruhy jsou ID nadplochy, koule je příklad 2D nadplocha základní metody varietního učení: 1. ISOMAP (Tenenbaum et al. 2000) 2. Metoda lokálně lineárního vnoření = LLE (Roweis & Saul 2000) další metody varietního učení: Laplacian Eigenmaps, Sammon's Mapping, Kohonen Maps, Autoencoders, Gaussian process latent variable models, Curvilinear component analysis, Curvilinear Distance Analysis, Kernel Principal Component Analysis, Diffusion Maps, Hessian LLE, Modified LLE, Local Tangent Space Alignment, Local Multidimensional Scaling, Maximum Variance Unfolding, Data-Driven High Dimensional Scaling, Manifold Sculpting, RankVisu některé z manifold learning metod implementovány v mani.m demu (http://www.math.ucla.edu/~wittman/mani/index.htm MU Janoušová: Analýza a klasifikace dat *L (^J ISOMAP metoda • založena na MDS • ISOMAP = isometric feature mapping • snaha o zachování vnitřní geometrie dat, která je zachycena pomocí geodézních vzdáleností (geodesis distance) založených na hledání nejkratších cest v grafu s hranami spojujícími sousední datové body a b ^_ _ c Tenenbaum et al. 2000 Science, A Global Geometric Framework for Nonlinear Dimensionality Reduction MU Janoušová: Analýza a klasifikace dat ISOMAP metoda - algoritmus se 3 kroky i- 1. Vytvoření grafu spojujícího sousední objekty: • nejprve nutno vypočítat vzdálenosti D(xí,x;) mezi všemi objekty • poté dojde ke spojení objektů tak, že se y-tý objekt spojí s těmi objekty, jejichž vzdálenost je menší než e (v případě f-ISOMAP), nebo s jeho k nejbližšími sousedy (v případě /e-ISOMAP) 2. Výpočet geodézních vzdáleností Dg(xí,x;) mezi všemi objekty nalezením nej kratší cesty v grafu mezi danými objekty - iniciální nastavení Dg(xí,x;) závisí na tom, jestli jsou objekty spojené hranou či nikoliv: • pokud objekty spojeny hranou: Dg(xí,x;) = D(xí,x;) • pokud ne: Dg(xí,x;) = oo poté je pro každé k = 1,2,...,N nahrazena vzdálenost Dg(xí,x;) hodnotou min(DG(xj,x;) ,DG(xifxk) + DG(xifxk) ). 3. Aplikace nemetrického vícerozměrného škálování (MDS) na matici geodézních vzdáleností - tzn. transformace dat do Euklidovského prostoru tak, aby byly co nejlépe zachovány geodézní vzdálenosti. Tenenbaum et al. 2000 Science, A Global Geometrie Framework for Nonlinear Dimensionality Reduction MU Janoušová: Analýza a klasifikace dat J^J ISOMAP metoda - ukázka 1 Výsledek /MSOMAP algoritmu u 698 obrazů tváří a) A d) >s_ > d) O N O Q. ]E > Li □ "3" t ■a E i' fa. • B * fa;' a mi KLI * • 11 ♦ji ■ i—~ a: Interpolace podél os x a y v podprostoru obrazů tváří Výsledkem je redukce původních 4096 proměnných (obrazy měly rozměry 64 x 64 pixelů) na pouze tři komponenty směr osvětlení pravolevé natočení tváře Tenenbaum et al. 2000 Science, A Global Geometric Framework for Nonlinear Dimensionality Reduction Janoušová: Analýza a klasifikace dat ISOMAP metoda - ukázka 2 Výsledek ISOMAP algoritmu u obrazů ručně psaných číslic B Bottom loop articulation c o ed -i y r 03 c o2 J "a 3 5 5 rí 'J Interpolace podél osx a y v podprostoru obrazů číslic Tenenbaum et al. 2000 Science, A Global Geometrie Framework for Nonlinear Dimensionality Reduction Janoušová: Analýza a klasifikace dat IBA Metoda lokálně lineárního vnoření (LLE) )- • Locally Linear Embedding (LLE) • založena na zachování mapování sousedů (neighborhood-preserving mapping) • LLE rekonstruuje globální nelineární struktury z lokálních lineárních fitů Černě vyznačeno okolí (sousedi) jednoho bodu. Roweis & Saul 2000 Science, Nonlinear Dimensionality Reduction by Locally Linear Embedding Janoušová: Analýza a klasifikace dat LLE - algoritmus ° ° o (?) S&lůÉt neighbor* o •--<^--. o Map to embedded coordinates 1. Výběr k nejbližších sousedů. 2. Rekonstrukce objektů z jejich sousedů - cílem je nalezení vah Wy tak, aby rekonstrukční chyby byly co nejmenší, tzn. snažíme se minimalizovat výraz s(W) = Hi|xi — T,j Wij x;|2/ přičemž součet vah Wjj musí být roven 1; váhy jsou invariantní vůči rotaci, přeškálování a translaci objektů a jejich sousedů. 3. Mapování do „nadplochy" s nižší dimenzionalitou (lineární mapování - skládající se z translací, rotací a přeškálování) pomocí výpočtu vlastních vektorů Roweis & Saul 2000 Science, Nonlinear Dimensionality Reduction by Locally Linear Embedding Janoušová: Analýza a klasifikace dat J^J LLE-ukázka 1 Výsledek LLE algoritmu u obrazů tváří a> «co _> cd o 'n o Q. Roweis & Saul 2000 Science, Nonlinear Dimensionality Reduction by Locally Linear Embedding Janoušová: Analýza a klasifikace dat výraz tváře (Ml IBA LLE - ukázka 2 Výsledek LLE algoritmu u hodnocení počtu a výskytu slov v encyklopedii master image television ,íilm i image i academy paintings *gallcry a artists .artist tube. .radio colors • • light furniture decorativei fine** "painter scenes TwrUait LANDSCAPE, 'formal*™ ^fde^1011™ garden * florence • gUSS outsWr^f ^mqufi ■ elalwirateyarchiieci objects . . ^renaissance subject • » design • • classical reflected coniemporary ___1_______j _ j_________v -b london paris * medieval ages ITALIAN middle ITALY Roweis & Saul 2000 Science, Nonlinear Dimensionality Reduction by Locally Linear Embedding Janoušová: Analýza a klasifikace dat I BA Výhody a nevýhody ISOMAP a LLE • výhody a nevýhody ISOMAP: + zachovává globální strukturu dat + málo parametrů - citlivost k šumu - výpočetně náročné • výhody a nevýhody Locally Linear Embedding (LLE): + rychlý + jeden parametr + jednoduché operace lineární algebry - může zkreslit globální strukturu dat MU Janoušová: Analýza a klasifikace dat *L (^J Další práce * Laplacian Eigenmaps for Dimensionality Reduction and Data Representation (Belkin & Niyogi 2003): - snaha o zachování mapování sousedů jako u Locally Linear Embedding - podobný algoritmus jako LLE, ale používá se zde výpočet vlastních vektorů a vlastních čísel s využitím Laplaciánu grafu - souvislost s klastrováním - lokální přístup k redukci dimenzionality způsobuje přirozené klastrování dat (klastrování tedy nastává u Laplacian Eigenmaps a LLE, nenastává u ISOMAP, protože to je globální metoda) • Manifold Learning for Biomarker Discovery in MR Imaging (Wolz et al. 2010) - použití Laplacian eigenmaps u obrazů pacientů s Alzheimerovou chorobou (data ADNI) Janoušová: Analýza a klasifikace dat *L (^J 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" evropský sociální fond V ČR EVROPSKÁ UNIE INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ MINISTERSTVO ŠKOLSTVÍ, OPVzdělávání MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost MU Janoušová: Analýza a klasifikace dat |yj 46