Pokročilé metody analýzy dat v neurovědách IBA # RNDr. Eva Janoušová doc. RNDr. Ladislav Dušek, Dr. Jaro 2016 Blok 3 Podobnosti a vzdálenosti ve vícerozměrném prostoru Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA ^ ^ Osnova i- 1. Úvod do metrik podobností a vzdáleností 2. Metriky pro určení vzdálenosti mezi dvěma objekty 3. Metriky pro určení podobnosti mezi dvěma objekty 4. Metriky pro určení vzdálenosti mezi dvěma skupinami objektů 5. Asociační matice Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^JJ Úvod do metrik podobností a vzdáleností Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 4 Poznámka • jednotlivé objekty je možno znázornit pomocí bodu v p-rozměrném prostoru (p je počet proměnných) "2 12" "5 7" XD = 4 10 > 3 9 .3 8. .4 5. 13 £ 12 • • pacienti | 11 • kontroly _c 10 • u -r 9 • o | 8 • o 6 IZľ 05 • A I_I_I_I_I_I 1 2 3 4 5 6 Objem hipokampu MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ W Metriky podobnosti vs. metriky vzdálenosti • Metriky vzdálenosti objektu x1 od objektu x2 - označení: D(x1,x2) • pozn.: vzdálenost objektu od sebe samého je 0 - tzn. D(x1/x1)=0 • Metriky podobnosti objektu x1 od objektu x2 - označení: 5(x1,x2) • pozn.: podobnost objektu od sebe samého je maximálni hodnota podobnosti pro danou metriku (zpravidla hodnota 1, ale neplatí to vždy) • Metriky vzdálenosti mohou být různými transformacemi převedeny na metriky podobnosti (a obráceně), např.: S(x]fx) = 1/ D(x]fx) S(x,x) = 1/(1+ D(x,x)) S(x]fx) = c - Díx^Xj), c > max D^Xj), Vij MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! ^ Typy měr vzdálenosti (podobnosti) )- • podle typu proměnné (kvalitativní proměnné, kvantitativní proměnné) • podle objektů, jejichž vztah hodnotíme - obrazy (vektory), množiny obrazů (vektorů) • deterministické (nepravděpodobností) vs. pravděpodobností míry • výběr konkrétní metriky závisí na: - výpočetních nárocích - charakteru rozložení dat - dosažení optimálních výsledků (klasifikační chyba, ztráta,...) • obecně bohužel není možné dopředu doporučit vhodnou metriku pro danou situaci • chybný výběr metriky může vést k chybných závěrům analýzy (stejně jako v klasické statistické analýze výběr nevhodného testu) MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. MEZI DVĚMA SKUPINAMI OBJEKTU Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými 2 množinami objektů používající jejich Hammingova m. pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Wl 8 Metriky pro určení vzdálenosti mezi dvěma objekty Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými Hammingova m. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. MEZI DVĚMA SKUPINAMI OBJEKTU Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 10 Nejpoužívanější metriky pro určení vzdálenosti mezi dvěma obrazy s kvantitativními proměnnými Euklidova metrika Hammingova (manhattanská) metrika Minkovského metrika Čebyševova metrika Mahalanobisova metrika Canberrská metrika Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách 11 Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou geometrickou interpretací DE(xlfx2) = / (Xli - X2i): "1 = 1 o > O M O CU la O 13 h 12 11 10 A 2 3 4 5 6 Objem hipokampu o > O M O CD la O 13 h 12 11 l 10 l 8 pacienti kontroly testovací subjekt 1 2 3 4 5 6 Objem hipokampu Janoušová, Dušek: Pokročilé metody analýzy dat v neurovédách IBA W 12 Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou geometrickou interpretací DE(xlfx2) = / (Xli - X2i): "1 = 1 geometrickým místem bodů s toutéž Euklidovou vzdáleností od daného boduje povrch hyperkoule (ve dvourozměrném prostoru kružnice) dává větší důraz na větší rozdíly mezi souřadnicemi žádoucí nebo nežádoucí? občas se používá čtverec euklidovské vzdálenosti, protože se lépe počítá než euklidovská vzdálenost (není to ale pravá metrika vzdálenosti) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 13 Hammingova (manhattanská) metrika • v AJ názvy: Manhattan distance, city-block distance, taxi driver distance DH(xlfx2) = ) |x1£ -x2i\ "1=1 • nižší výpočetní nároky než Euklidova metrika -> použití v úlohách s vysokou výpočetní náročností Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- I^J 14 Hammingova (manhattanská) metrika Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA ^ 15 Hammingova (manhattanská) metrika £>//(xi,x2) = > |xlř -x2i\ "1=1 13 12 11 10 o u > O M O cu Iq o J 1 2 3 4 5 6 Objem hipokampu o u ->■ > o M O E E cu o 13 12 11 10 2 3 4 5 6 Objem hipokampu pacienti kontroly testovací subjekt geometrickým místem bodů s toutéž manhattanskou vzdáleností od daného bodu je hyperkrychle (ve dvourozměrném prostoru čtverec) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA M) 16 Minkovského metrika zobecněním Euklidovy a Hammingovy (manhattanské) metriky níl x l/m. dm(Xi,x2) = Q] |Xlí-x2ír) Euklidova metrika pro m = 2, Hammingova (manhattanská) metrika pro m = 1 volba m závisí na tom, jak moc chceme váhovat velké rozdíly mezi proměnnými (čím větší m, tím větší váha na velké rozdíly mezi proměnnými) pro m -> oo metrika konverguje k Čebyševově metrice Dc(xlfx2) = lim DM(xlfx2) = maxlxii -x2i\ m->oo Vi Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 17 Čebyševova metrika )- • odvozena z Minkovského metriky pro m -> oo ^c(xi,x2) = max|x1£ -x2i\ 13 h 13 h O -C U > O M O 12 11 l 10 l 8 J O (_) > O M O 12 11 ľ 10 l 8 pacienti kontroly testovací subjekt cu Iq o cu Iq o 1 2 3 4 5 6 Objem hipokampu 1 2 3 4 5 6 Objem hipokampu Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 18 Čebyševova metrika • odvozena z Minkovského metriky pro m -> oo 0c(xi,x2) = max|x1£ -x2i\ • používá se ve výpočetně kriticky náročných případech, kdy je pracnost výpočtu pomocí Euklidovy metriky nepřijatelná • geometrickým místem bodů s toutéž Čebyševovou vzdáleností od daného bodu je hyperkrychle (ve dvourozměrném prostoru čtverec), ale jinak orientovaná než v případě Hammingovy (manhattanské) vzdálenosti Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- I^J 19 Srovnání metrik i pc... Čebyševova metrika pE... Euklidova metrika pH ... Hammingova (manhattanská) metrika MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ll^l.l 20 Canberrská metrika relativizovaná varianta Hammingovy (manhattanské) metriky nn |x1£ -x2£| ^(xi,x2) = > t—-r ^—n=i Ixiil + |x2íl je vhodná pro proměnné s nezápornými hodnotami pokud se vyskytují nulové hodnoty: - pokud jsou obě hodnoty xlt a x2j nulové, potom předpokládáme, že hodnota zlomku je nulová - je-li jenom jedna hodnota nulová, pak je zlomek roven 1 bez ohledu na velikost druhé hodnoty - někdy se nulové hodnoty nahrazují malým kladným číslem (menším než nejmenší naměřené hodnoty) velice citlivá na malé změny souřadnic, pokud se oba obrazy nacházejí v blízkosti počátku souřadnicové soustavy; naopak méně citlivá na změny hodnot proměnných, pokud jsou tyto hodnoty velké Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 21 Nevýhody metrik )- • je nesmyslné vytvářet součet rozdílů veličin s různým fyzikálním rozměrem, a tudíž často s velmi rozdílným rozsahem • při začlenění korelovaných veličin se zvyšuje jejich vliv na výslednou hodnotu • řešení: 1. transformace proměnných: vztažení k nějakému vyrovnávacímu faktoru (střední hodnotě, směrodatné odchylce, rozpětí As = maXj Xj. - minj x^) či pomocí standardizace utj =^^-; i = 1,... ,n;j = 1,... ,p; kde n je počet subjektů a p je počet proměnných 2. váhování: např. Minkovského váhovaná metrika: *Wxi,x2) = (E?=1ař ■ |xlř -x2ř|m)1/m 3. začlenění kovarianční matice do výpočtu: začleněním inverze kovarianční matice získáváme Mahalanobisovu metriku (což je Euklidova metrika váhovaná inverzí kovarianční matice): DMA(xlfx2) = V(xi-x2)7-S-1-(x1-x2) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! ^2 Nelineární metrika Pn(^1'^2 ) — O kdyžpE(x1,x2) D kde D je prahová hodnota a H je nějaká konstanta obě hodnoty se zpravidla volí na základě expertní analýzy řešeného problému ve vztahu může figurovat jakákoliv metrika vzdálenosti, nejen Euklidova metrika Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA m 23 Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými Hammingova m. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. MEZI DVĚMA SKUPINAMI OBJEKTU Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 24 Příklad Předpokládejme, že množina F obsahuje symboly {0,1, 2}, tj. k = 3 a vektory x a y jsou následující 6-prvkové vektory (tj. p = 6): x = (0, 1, 2,1, 2,1)T y = (l, 0, 2,1, 0,1)T Spočtěte vzdálenost obou vektorů. Kontingenční matice A(x,y) je: 0 1 0 A(x,y) = 1 2 0 1 0 1 Součet hodnot všech prvků matice A(x,y) je roven délce p obou vektorů, tj. v našem případě: 2 2 i=0 j=0 MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách iba W 25 Hammingova metrika vzdálenosti k-i k-i i=0 y=0 • definována počtem pozic, v nichž se oba vektory liší • tzn. je dána součtem všech prvků matice A, které leží mimo hlavní diagonálu. Příklad: x = (0, 1, 2, 1, 2, 1)T y = (l, 0, 2, 1, 0, 1)T liší se ve 3 souřadnicích X2 ) ~~ T Xl -X2 T kde = (xn — Xi, x£2 — Xi,..., Xjp — x^) xdi jsou tzv. diferenční vektory také nabývá hodnot z intervalu <-l;l> odvození metriky vzdálenosti: l — Spc(xl,X2) hodnoty se (díky dělení dvěma) vyskytují ^pc(xľx2)= I v intervalu (0;1) ^ -> používá se např. při analýze dat genové exprese Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 31 Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými Hammingova m. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. MEZI DVĚMA SKUPINAMI OBJEKTU Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 32 Metriky pro určení podobnosti 2 objektů s kvalitativními prom 1. případy obecné 2. případy s dichotomickými příznaky, pro které je definována celá řady tzv. asociačních koeficientu. (Asociační koeficienty až na výjimky nabývají hodnot z intervalu (0,1), hodnoty 1 v případě shody vektorů, 0 pro případ nepodobnosti.) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 33 Obecné metriky - Hammingova metrika podobnosti HQ Příklad: x = (0, 1, 2,1, 2,1)T y=(l, 0, 2,1, 0,1)T liší se ve 3 souřadnicích shoda ve 3 souřadnicích Wx>Y) = 6-3 = 3 A(x, y) = 0 1 0" 12 0 LI 0 1J 3 prvky mimo diagonálu dhq(*>v) = 3 součet prvků na diagonále roven 3 sHQ(x,y) = 6-3 = 3 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 34 Obecné metriky-Tanimotova metrika Sre(x,y) = n k-1 k-1 nx = 2.2.ai i=1 j=0 Pro výpočet Tanimotovy podobnosti dvou vektorů s kvalitativními příznaky jsou použity všechny páry složek srovnávaných vektorů, kromě těch, jejichž hodnoty jsou obě nulové. y=0 y=l y=2 x=0 x=l ,2) Žla, x=2 U Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách 35 Obecné metriky-Tanimotova metrika - příklad Určete hodnoty Tanimotových podobností srQ(x,x), sTQ(x,y) a srQ(x,z), když: x = (0,1, 2,1, 2,1)T a y = (1, 0, 2,1, 0,1)T a z = (2, 0, 0, 0, 0, 2)T. Ze zadání je množina symbolu F = {0,1, 2}, k = 3, p = 6. Kontingenční tabulky jsou: A(x, x) - A(x,y) = 0 1 0 1 2 0 1 0 1 A(x,z) = 0 0 1 2 0 1 2 0 0 3 0 sT0(x>y) = -—r-r = °>5 sT0(\,z)^-= 0 5+4-3 5 + 2-1 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovédách IBA m 36 Další obecné metriky definovány pomocí různých prvků kontingenční matice A(x,y) některé z nich používají pouze počet shodných pozic v obou vektorech (ovšem s nenulovými hodnotami): k-i k-i ^(x,y) = ^— SJx,y)= " P p-a oo některé z nich používají i shodu s nulovými hodnotami: k-i P Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 37 Asociační koeficienty Xi false/O true/1 false/O D C true/1 B A A - u obou objektů sledovaný jev nastal (obě odpovídající si proměnné mají hodnotu true, resp.l) - pozitivníshoda; B - u objektu x. jev nastal (xjk = true), zatímco u objektu x. nikoliv (xjk = falše, resp.O); C - u objektu x. jev nenastal (xjk = falše), zatímco u objektu x. ano (xjk = true); D - sledovaný jev nenastal ani u jednoho z objektů (obě odpovídající si proměnné mají hodnotu falše, resp. 0) - negativní shoda. Při výpočtu podobnosti dvou objektů sledujeme, kolikrát pro všechny souřadnice obou vektorů x. a x. nastaly případy shody či neshody: • A+D určuje celkový počet shod • B+C celkový počet neshod • A+B+C+D = p (tj. celk. počet souřadnic obou vektorů - tzn. počet proměnných) MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 38 Jaccardův-Tanimotův asociační koeficient S,r(x,y) = A Xi false/O true/1 A + B + C false/O D true/1 B m. což je díky zjednodušení i dichotomická varianta metriky podle vztahu SVe(x,y) = n X + n y Tento vztah se dominantně používá v ekologických studiích. MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 39 Další asociační koeficienty I Xi false/0 true/1 false/0 D C true/1 B A Russelův - Raoův asociační koeficient k-i A dichotomická varianta Srr (x> ľ) = TT^TT^ľň metriky: Sx (x, y) = A+B+C+D p Sokalův - Michenerův asociační koeficient k-i A + dichotomická varianta ^4au A + B + C + D metriky: Qí / \ _ . - UILMULUM IIUI\d Vdlldllld _ *SM^y)-—^—^-7: metrjkv. SJx,y)=i=° P MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 40 Další asociační koeficienty II x, false/0 true/1 false/0 D C true/1 B A Diceův (Czekanowského) asociační koeficient 2A 2A DC 2Ä + B + c (a + B) + (a + c) V případě Jaccardova a Diceova koeficientu pokud nastane úplná negativní shoda (tzn. A = B = C =0), pak často: SJT(x,y) = SDC(x,y) = 1. Rogersův - Tanimotův asociační koeficient o r x a+D a+D sRT(^y) = a + D + 2-(B + c) (B + c) + (a + B + c + D) Hamanův asociační koeficient nabývá na rozdíl od všech dříve uvedených koeficientů hodnot z intervalu (-1,1). Hodnoty-1, _ , , a + D-(B + c) pokud se příznaky pouze neshodují; hodnoty 0, když ha\ >jJ ^ + 2? + C + Z) je počet shod a neshod v rovnováze;+1 v případě úplné shody všech příznaků Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^ Asociační koeficienty - poznámka Xi false/O true/1 Xi false/O D C true/1 B A Na základě četností A až D lze pro případ binárních příznaků vytvářet i zajímavé vztahy pro již dříve uvedené míry: Hammingova metrika £) (x, y) = B + C Euklidova metrika DH{x,y) = 4B + Č Pearsonův korelační koeficient AD-BC -SI(A + B)-(C + D)-(A + C)-(B + D) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 42 Výpočet vzdáleností z asociačních koeficientů Z asociačních koeficientů, které vyjadřují míru podobnosti, lze jednoduše odvodit i míry nepodobnosti (vzdálenosti) pomocí: £>x(x,y) = l-Sx(x,y) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 43 Výpočet vzdáleností v Matlabu Funkce: • pdist (vzdálenost mezi páry objektů matice X či páry proměnných matice XT) • pdist2 (vzdálenost mezi maticemi X a Y) Výběr metrik vzdáleností u obou těchto funkcí: • 'euclidean' - Euklidova vzdálenost • 'squaredeuclidean' - čtverec Euklidovy vzdálenosti • 'seuclidean' - standardizovaná Euklidova vzdálenost • 'cityblock' - Hammingova (manhattanská) vzdálenost • 'minkowskľ - Minkovského vzdálenost • 'chebychev' - Čebyševova vzdálenost • 'mahalanobis' - Mahalanobisova vzdálenost • 'cosine' - 1 mínus kosinová podobnost • 'correlation' - 1 mínus Pearsonův korelační koeficient • 'spearman' - 1 mínus Spearmanův korelační koeficient • 'hamming' - Hamminova vzdálenost (pro kvalitativní proměnné) • 'jaccarď - 1 mínus Jaccardův koeficient • lze případně nadefinovat i jinou metriku Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^BÄ ^! 44 Metriky pro určení vzdálenosti mezi dvěma skupinami objektů Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY MEZI DVĚMA SKUPINAMI OBJEKTU Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými Hammingova m. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 46 Vzdálenost mezi skupinami objektů i- • vzdálenost mezi skupinami dána: - „vzdáleností" jednoho objektu s jedním či více objekty jedné skupiny (třídy) - použitelné při klasifikaci - „vzdáleností" skupin (třídy, shluku) obrazů či „vzdáleností" jednoho obrazu z každé skupiny - použitelné při shlukování • jednotlivé deterministické metriky pro určení vzdálenosti mezi dvěma množinami objektů si probereme v rámci shlukové analýzy na příští přednášce Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 47 Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY MEZI DVĚMA SKUPINAMI OBJEKTU Metriky pro určení vzdálenosti mezi 2 objekty s kvantitativními proměnnými Euklidova m., Hammingova (manhattanská) m., Minkovského m., Čebyševova m., Mahalanobisova m., Canberrská m. Metriky pro určení vzdálenosti mezi 2 objekty s kvalitativními proměnnými Hammingova m. Metriky pro určení podobnosti 2 objektů s kvantitativními proměnnými Skalární součin, m. kosinové podobnosti, Pearsonův korelační koeficient, Tanimotova m. Metriky pro určení podobnosti 2 objektů s kvalitativními proměnnými Tanimotova m., Jaccardův-Tanimotův a.k., Russelův-Raovův a.k., Sokalův-Michenerův a.k., Dicův k., Rogersův-Tanimotův k., Hamanův k. Deterministické metriky pro určení vzdálenosti mezi 2 množinami objektů Metoda nejbližšího souseda, k nejbližších sousedů, nejvzdálenějšího souseda, centroidová metoda, m. průměrné vazby, Wardova metoda Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 48 Metriky založené na pstních charakteristikách Základní myšlenkou je využití pravděpodobnosti způsobené chyby při klasifikaci (tzn. zařazení objektu do skupiny). Čím více se hustoty pravděpodobnosti výskytu obrazů x v jednotlivých množinách překrývají, tím je větší pravděpodobnost chyby. Tzn. tyto metriky splňují následující vlastnosti: 1. J = 0, pokud jsou hustoty pravděpodobnosti obou množin identické, tj. když PÍxIcOí) =p(x|co2) 2. J > 0 3. J nabývá maxima, pokud jsou obě množiny disjunktní, tj. když °2 p(x(ú1) -p(x(ú2)dx = 0 -oo f(Xl) f(Xl) f(Xl) xl xi Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 49 Asociační matice Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- I^J 50 Asociační matice - Q mode analýza NxP MATICE ASOCIAČNÍ MATICE h r\j m v03 sfU sfO C C C C C C > +-» _^ _^ _^ _^ _^ _^ O) (L) >CL) >CL> >(D E E E o o o Q. Q. Q. proměnná 1 proměnná 2 proměnná 3 Vzdálenost, podobnost, korelace, kovariance mezi proměnnými Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 52 Asociační matice - ukázka Vzdálenost měst v mapě není ničím jiným než maticí vzdálenosti v 2D prostoru Vzdálenost v km Barcelona,^ ■c 2 .c oj m Berlín V Brusely Bukurešť \ 1 Budapešť Kodaň Dublin Hamburg Istanbul Kiev Londýn Madrid :J Barcelona 0 1528 1497 1062 1968 1498 1757 1469 1471 2230 2391 1137 504 Bělehrad 1528 0 999 1372 447 316 1327 2145 1229 809 976 1688 2026 Berlín 1497 999 0 651 1293 689 354 1315 254 1735 1204 929 1867 Brusel 1062 1372 651 0 1769 1131 766 773 489 2178 1836 318 1314 Bukurešť 1968 447 1293 1769 0 639 1571 2534 1544 445 744 2088 2469 Budapešť 1498 316 689 1131 639 0 1011 1894 927 1064 894 1450 1975 Kodaň 1757 1327 354 766 1571 1011 0 1238 287 2017 1326 955 2071 Dublin 1469 2145 1315 773 2534 1894 1238 0 1073 2950 2513 462 1449 Hamburg 1471 1229 254 489 1544 927 287 1073 0 1983 1440 720 1785 Istanbul 2230 809 1735 2178 445 1064 2017 2950 1983 0 1052 2496 2734 Kiev 2391 976 1204 1836 744 894 1326 2513 1440 1052 0 2131 2859 Londýn 1137 1688 929 318 2088 1450 955 462 720 2496 2131 0 1263 Madrid 504 2026 1867 1314 2469 1975 2071 1449 1785 2734 2859 1263 0 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA W 53 Asociační matice - shrnutí • Typická asociační matice je čtvercová matice • Typická asociační matice je symetrická kolem diagonály - Ve speciálních případech existují i asymetrické asociační matice • Diagonála obsahuje: - 0 (v případě vzdáleností) - identitu objektu se sebou samým (v případě podobnosti, obvykle 1 nebo 100%) • Asociační matice může být spočtena mezi objekty (Q mode analýza) nebo mezi proměnnými (R mode analýza) • Asociační matice mohou být jak vstupem do vícerozměrných analýz, tak vstupem pro klasické jednorozměrné statistické výpočty, kdy základní jednotkou není jeden objekt, ale podobnost/vzdálenost dvojice objektů Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- I^J 54 Poděkování Příprava výukových materiálů předmětu „DSAN02 Pokročilé metody analýzy dat v neurovědách" byla finančně podporována prostředky projektu FRMU č. MUNI/FR/0260/2014 „Pokročilé metody analýzy dat v neurovědách jako nový předmět na LF MU" Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- I^J 55