Pokročilé metody analýzy v neurovědách IBA # RNDr. Eva Janoušová doc. RNDr. Ladislav Dušek, Dr. Jaro 2015 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 ij^J/ 2 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 ij^J Ú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" 4 10 > — 3 9 .3 8. .4 5. 13 o 12 • pacienti o 11 • kontroly j= 10 • u sí 9 - • o | 8 • £ 7 • E cu 6 O 5 • 4 '-1-1-1-1-' 1 2 3 4 5 6 Objem hipokampu MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovi vIM max D^x), Vij MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 6 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 l^J 7 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. 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 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. Janoušová, D Metriky pro určení vzdálenosti mezi 2 množinami objektů používající jejich pravděpodobnostní charakteristiky Chernoffova m., Bhattacharyyova m. atd. k: Pokročilé metody analýzy dat v neurovědách 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 MEZI DVĚMA SKUPINAMI OBJEKTŮ 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. 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. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách 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 \(Jt0/ 11 Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou interpretací DE(x1,x2) = Zn Oii - x2;): i=l geometrickou o E o -C U > o M o E E O) o 13 12 11 10 7 A 1 2 3 4 5 6 Objem hipokampu o -C U > o M O) o 13 12 11 10 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 m i2 Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou geometrickou interpretací geometrickým místem bodů s toutéž Euklidovou vzdáleností od daného boduje hyperkoule (ve dvourozměrném prostoru kruh) 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 IBA (g) 13 Hammingova (manhattanská) metrika • v AJ názvy: Manhattan distance, city-block distance, taxi driver distance Zn |x1£ — X2£| i=l • nižší výpočetní nároky než Euklidova metrika -> použití v úlohách s vysokou výpočetní náročností • geometrickým místem bodů s toutéž manhattanskou vzdáleností od daného bodu je hyperkrychle (ve dvourozměrném prostoru čtverec) MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 14 Hammingova (manhattanská) metrika • srovnání Hammingovy (manhattanské) metriky a Euklidovy metriky Hammingova (manhattanská) metrika * názvy v angličtině: Manhattan distance, city-block distance, taxi driver distance Zn |x1£ — X2£| i=l o E o -C O > o M o E E O) Iq o 13 12 11 10 J 2 3 4 5 6 Objem hipokampu o -C O > o M O) Iq o 13 12 11 10 1 2 3 4 5 6 Objem hipokampu • pacienti • kontroly • testovací subjekt Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 16 Minkovského metrika zobecněním Euklidovy a Hammingovy (manhattanské) metriky ^m(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(x1,x2) = lim DM(x1,x2) = maxlxií -x2i\ m->oo Vi Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Ji 17 Čebyševova metrika >- • odvozena z Minkovského metriky pro m -> oo Dc(x1,x2) = max|x1£ -x2i\ o E o -C O > o M o E E O) Iq o 13 12 11 10 J 2 3 4 5 6 Objem hipokampu o -C O > o M O) Iq o 13 12 11 10 1 2 3 4 5 6 Objem hipokampu • pacienti • kontroly • testovací subjekt Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 18 Čebyševova metrika • odvozena z Minkovského metriky pro m -> oo Dc(x1,x2) = max|x1£ -x2i\ VI • 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 ij^J/ 19 Srovnání metrik \NPe ;__1_____ Pc Pe Ph Čebyševova metrika Euklidova metrika Hammingova (manhattanská) metrika Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 20 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í A, = maXj Xj- - minj Xj-) či pomocí standardizace utj = Xlj^ Xj; i = l,...,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: A^m(X1'X2) — (Ef=l&i " lxli x2i I771)1/772 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(xi> xi) ~ V(xi ~~ X2)T " S 1 ■ (xx — x2) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách 21 Canberrská metrika relativizovaná varianta Hammingovy (manhattanské) metriky D (x x ) - Y" |Xlŕ~X2ŕl je vhodná pro proměnné s nezápornými hodnotami pokud se vyskytují nulové hodnoty: — pokud jsou obě hodnoty xlt a x2i 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é MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 22 Nelineární metrika pN(X1IX2) = < 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 MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ^jjj- 23 Typy metrik a konkrétní příklady MEZI DVĚMA OBJEKTY MEZI DVĚMA SKUPINAMI OBJEKTŮ 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. 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. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách Příklad Předpokládejme, že množina F obsahuje symboly {0,1, 2}, tj. k = 3 a vektory x a y jsou: x = (0, 1, 2,1, 2,1)T a y = (1, 0, 2,1, 0,1)T, p = 6. 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 ZZaij=6 i=0 j=0 MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách JMf 25 Hammingova metrika vzdálenosti k-l k-l i=0 7=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 A(x,y) = "0 1 0" 12 0 .1 0 1J 3 prvky mimo diagonálu dHQ(x,V) = 3 GÍWQ(x,y) = 3 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 26 Metriky pro určení podobnosti 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. Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 28 Skalární součin n ^(X1?X2) = Xl *X2 = T^l X\iX2i i=l Většinou pro vektory x1 a x2o stejné délce (např. a); záleží na úhlu, který svírají: úhel 0° úhel 90° úhel 180° Sss = a2 Sss =0 Sss= -a2 skalární součin invariantní vůči rotaci - absolutní orientace nepodstatná, důležitý pouze úhel skalární součin není invariantní vůči lineární transformaci (tzn. závisí na délce vektorů) odvození metriky vzdálenosti: A,(XPX2) = ^2-^(XPX2) MU ,-.*■»»., Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách \IM|/ 29 Metrika kosinové podobnosti ^cos (Xl 5 X2 ) — T X.1 .X.' kdellxi|| je norma (délka) vektoru Xj = skalární součin vektorů o jednotkové délce vhodná v případě, pokud je informativní pouze relativní hodnota příznaků hodnoty a^x^ x2) jsou rovny kosinu úhlu mezi oběma vektory úhel 0° úhel 90° úhel 180c 5=1 5=0 5=-l ucos -'cos ucos J- Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 30 Pearsonův korelační koeficient Pearsonův korelační koeficient Metrika kosinové podobnosti S PC (Xl 5 X2 ) — Xd\'Xd2 'dl ^cos(Xl'X2) — T Xl -X2 kde — (xji — XpXj2 — Xj, ■■■,xíp — xí) xdj jsou tzv. diferenční vektory také nabývá hodnot z intervalu odvození metriky vzdálenosti: l _ g (x1?X2) hodnoty se (díky dělení dvěma) vyskytují ^pc(x1,X2)= - 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 IMJ 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 koeficientů. (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^J/ 33 Obecné metriky-Hammingova metrika podobnosti s ho (x> y) = p - dho (x> y) HO 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 5HQ(x,y) = 6-3 = 3 A(x,y) = 0 1 0" 12 0 Ll 0 U 3 prvky mimo diagonálu GÍWQ(x,y) = 3 součet prvků na diagonále roven 3 Wx,y) = 6-3 = 3 'HQ Janoušová, Dušek: Pokročilé metody analýzy dat v neurovédách IBA m 34 Obecné metriky-Tanimotova metrika Srô(x,y) = n k-1 k-1 i=1 j=0 k-1 k-1 i=0 j=1 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é. x=0 y=0 (0,0) *'=1 7=1 y=l y=2 x=l x=2 (0,1) (0,2) n (1,0)/ (2,0) n x (1,2)X Za ■j (2,1)^2,2) _X 4 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 35 Obecné metriky-Tanimotova metrika - příklad i- Určete hodnoty Tanimotových podobnostísrQ(x,x), srQ(x, y) a sTO(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)\ Ze zadání je množina symbolů F = {0,1, 2), k = 3, p = 6. Kontingenční tabulky jsou: A(x, x) = 0 0 0 o<;'3N^ 0\2 A(x,y) = 0 1 0 1 2 0 1 0 1 A(x,z) = 0 0 1 2 0 1 2 0 0 Stq (x' x) mll-s_1 3 0 STo(x>y)= — „ =°»5 *m(x,z) =-= 0 5 + 4-3 5 + 2-1 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovédách IBA IM) 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-l k-l 51(x,y) = -í=!_ y) = A Xi false/0 true/1 A + B + C false/0 D true/1 B což je díky zjednodušení i dichotomická varianta metriky podle vztahu: sTQ(^y) = k-\ k-\ + X y a v 1=1 1=1 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 l^J 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 S**V>y>= A + B + c + D metriky: S1(x,y) = ^— Sokalův - Michenerův asociační koeficient k-i o / \ _ A + D dichotomická varianta SmK ,y)~ A + B + C + D střiky: S3(x,y) = ^- P MU Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách l^J 40 Další asociační koeficienty II Xi false/0 true/1 false/0 D C true/1 B A Diceův (Czekanowského) asociační koeficient Snr (x,y) =-=- c 2A + 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: 5JT(x,y) = SDC(x,y) = 1. Rogersův - Tanimotův asociační koeficient A + D A + D 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ž 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 41 A+B+C+D Asociační koeficienty - poznámka Xi false/0 true/1 false/0 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) = jB + Č 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 IMJ 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) = 1-Sx(x>y) Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^J/ 43 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 IMJ 45 Vzdálenost mezi skupinami objektů • 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 objektu si probereme v rámci shlukové analýzy na pnsti přednášce Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách ij^Jj 46 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 IMJ 47 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ÍxIcOi) =p(x|co2) 2. J > 0 3. J nabývá maxima, pokud jsou obě množiny disjunktní, tj. když ^ I p(x(ú1)-p(x(ú2)dx = 0 Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 48 Asociační matice Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IJMJ; 49 Asociační matice - Q mode analýza NxP MATICE r\i ro ^ro c c c c c c >cu >cu >cu E E E o o o Q. Q_ Q. objekt 1 objekt 2 objekt 3 objekt 4 objekt 5 objekt 6 Hodnoty proměnných pro jednotlivé objekty Výpočet metriky podobností/ vzdáleností Ľ asociační matice objekt 1 objekt 2 objekt 3 objekt 4 objekt 5 objekt 6 H (N 00 "šf LT) l£) +->+->+->+->+-> +-> ^ _^ _^ _^ _^ _^ (U (U (U (U (U (U 2ľ 2ľ 2ľ 2ľ 2ľ 2ľ o o o o o o Vzdálenost, podobnost, korelace, kovariance mezi objekty Janoušová, Dušek: Pokročilé metody analýzy dat v neurovědách IBA IMJ 50 Asociační matice - R mode analýza NxP matice h r\i m ^ro sro sro c c c c c c >0) >cu >cu E E E o o o L_ i_ i_ Q. Q. Q. objekt 1 objekt 2 objekt 3 objekt 4 objekt 5 objekt 6 Hodnoty proměnných pro jednotlivé objekty Výpočet metriky podobností/ vzdáleností Ľ asociační matice h rN ro ^ro sro sro c c c c c c >o> >cu >cu 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 IMJ 51 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 Bělehrad Berlín Brusel Bukurešť Budapešť Kodaň Dublin Hamburg Istanbul Kiev Londýn Madrid 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 IMJ 52 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 ij^J/ 53 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