© Institut biostatistiky a analýz
Pokročilé metody analýzy dat
v neurovědách
RNDr. Eva Koriťáková, Ph.D.
doc. RNDr. Ladislav Dušek, Dr.
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Blok 3
Podobnosti a vzdálenosti ve
vícerozměrném prostoru
2
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Osnova
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
3
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Úvod do metrik podobností
a vzdáleností
4
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Poznámka
• jednotlivé objekty je možno znázornit pomocí bodu v p-rozměrném
prostoru (p je počet proměnných)
5
𝐗 𝐷 =
2 12
4 10
3 8
, 𝐗 𝐻 =
5 7
3 9
4 5
pacienti
kontroly
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objem hipokampu
Objemmozkovýchkomor
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
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
6
• Metriky podobnosti objektu x1 od objektu x2 – označení: S(x1,x2)
• pozn.: podobnost objektu od sebe samého je maximální 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(xi,xj) = 1/ D(xi,xj)
S(xi,xj) = 1/(1+ D(xi,xj))
S(xi,xj) = c - D(xi,xj), c  max D(xi,xj), i,j
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy měr vzdálenosti (podobnosti)
7
• 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,...)
• 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)
• obecně bohužel není možné dopředu doporučit vhodnou metriku pro
danou situaci
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
8
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY MEZI DVĚMA SKUPINAMI OBJEKTŮ
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metriky pro určení vzdálenosti
mezi dvěma objekty
9
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
10
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, 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
11
• Euklidova metrika
• Hammingova (manhattanská) metrika
• Minkovského metrika
• Čebyševova metrika
• Mahalanobisova metrika
• Canberrská metrika
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 12
• zřejmě nejpoužívanější metrika s velmi názornou geometrickou
interpretací
𝐷 𝐸 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛
x1𝑖 − x2𝑖
2
Euklidova metrika
pacienti
kontroly
testovací subjekt
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 13
• zřejmě nejpoužívanější metrika s velmi názornou geometrickou
interpretací
𝐷 𝐸 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛
x1𝑖 − x2𝑖
2
Euklidova metrika
• geometrickým místem bodů s toutéž Euklidovou vzdáleností od daného
bodu je 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)
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 14
• v AJ názvy: Manhattan distance, city-block distance, taxi driver distance
𝐷 𝐻 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛
x1𝑖 − x2𝑖
Hammingova (manhattanská) metrika
• nižší výpočetní nároky než Euklidova metrika → použití v úlohách
s vysokou výpočetní náročností
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 15
• srovnání Hammingovy (manhattanské) metriky a Euklidovy metriky
Hammingova (manhattanská) metrika
A B
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 16
Hammingova (manhattanská) metrika
𝐷 𝐻 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛
x1𝑖 − x2𝑖
pacienti
kontroly
testovací subjekt
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
• geometrickým místem bodů s toutéž manhattanskou vzdáleností od
daného bodu je hyperkrychle (ve dvourozměrném prostoru čtverec)
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 17
• zobecněním Euklidovy a Hammingovy (manhattanské) metriky
𝐷 𝑀 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛
x1𝑖 − x2𝑖
𝑚
Τ1 𝑚
Minkovského metrika
• Euklidova metrika pro 𝑚 = 2, Hammingova (manhattanská) metrika pro
𝑚 = 1
• volba 𝑚 závisí na tom, jak moc chceme váhovat velké rozdíly mezi
proměnnými (čím větší 𝑚 , tím větší váha na velké rozdíly mezi
proměnnými)
• pro 𝑚 → ∞ metrika konverguje k Čebyševově metrice
𝐷 𝐶 𝐱1, 𝐱2 = lim
𝑚→∞
𝐷 𝑀 𝐱1, 𝐱2 = max
∀𝒊
x1𝑖 − x2𝑖
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 18
• odvozena z Minkovského metriky pro 𝑚 → ∞
𝐷 𝐶 𝐱1, 𝐱2 = max
∀𝒊
x1𝑖 − x2𝑖
Čebyševova metrika
pacienti
kontroly
testovací subjekt
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
1 2 3 4 5 6
4
5
6
7
8
9
10
11
12
13
Objemmozkovýchkomor
Objem hipokampu
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 19
• odvozena z Minkovského metriky pro 𝑚 → ∞
𝐷 𝐶 𝐱1, 𝐱2 = max
∀𝒊
x1𝑖 − x2𝑖
Čebyševova metrika
• 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
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 20
Srovnání metrik
ρC ... Čebyševova metrika
ρE ... Euklidova metrika
ρH ... Hammingova (manhattanská) metrika
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 21
• relativizovaná varianta Hammingovy (manhattanské) metriky
𝐷 𝐶𝐴 𝐱1, 𝐱2 = ෍
𝑖=1
𝑛 x1𝑖 − x2𝑖
x1𝑖 + x2𝑖
Canberrská metrika
• je vhodná pro proměnné s nezápornými hodnotami
• pokud se vyskytují nulové hodnoty:
– pokud jsou obě hodnoty x1𝑖 a x2𝑖 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é
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 22
• 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
Nevýhody metrik
• ř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í i = maxj xij - minj xij) či pomocí
standardizace u𝑖𝑗 =
x 𝑖𝑗−തx 𝑗
𝜎 𝑗
; 𝑖 = 1, … , 𝑛; 𝑗 = 1, … , 𝑝 ; kde 𝑛 je počet
subjektů a 𝑝 je počet proměnných
2. váhování:
‐ např. Minkovského váhovaná metrika: 𝐷 𝑊𝑀 𝐱1, 𝐱2 = ሺσ𝑖=1
𝑛
𝑎𝑖 ∙ ȁx1𝑖 −
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):
𝐷 𝑀𝐴 𝐱1, 𝐱2 = 𝐱1 − 𝐱2
𝑇 ∙ 𝐒−1 ∙ 𝐱1 − 𝐱2
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 23
Nelineární metrika






D),(kdyžH
D),(když0
),(
21E
21E
21N
xx
xx
xx
• 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
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
24
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Příklad
25
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 = (1, 0, 2, 1, 0, 1)T
Kontingenční matice A(x,y) je:
Součet hodnot všech prvků matice A(x,y) je roven délce p obou vektorů,
tj. v našem případě:











101
021
010
),( yxA
 

2
0i
2
0j
ij 6a
Spočtěte vzdálenost obou vektorů.
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Hammingova metrika vzdálenosti
26
• definována počtem pozic, v nichž se oba vektory liší







1
0
1
0
),(
k
i
k
ji
j
ijHQ aD yx
• tzn. je dána součtem všech prvků matice A, které leží mimo hlavní diagonálu.
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
Příklad:
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
dHQ(x,y) = 3
liší se ve 3 souřadnicích
𝐀 𝐱, 𝐲 =
0 1 0
1 2 0
1 0 1
𝐀 𝐱, 𝐲 =
0 1 0
1 2 0
1 0 1
dHQ(x,y) = 3
3 prvky mimo diagonálu
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metriky pro určení podobnosti
mezi dvěma objekty
27
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
28
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Skalární součin
29


n
i
ii
T
ss xxS
1
212121 .),( xxxx
Většinou pro vektory x1 a x2 o stejné délce (např. a); záleží na úhlu, který svírají:
úhel 0° úhel 90° úhel 180°
Sss = a2 Sss = -a2Sss = 0
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:
),(),( 21
2
21 xxxx ssss SaD 
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metrika kosinové podobnosti
30
21
21
21cos
.
.
),(
xx
xx
xx
T
S 
kde je norma (délka) vektoru xi
= skalární součin vektorů o jednotkové délce
vhodná v případě, pokud je informativní pouze relativní hodnota příznaků
hodnoty cos(x1, x2) jsou rovny kosinu úhlu mezi oběma vektory
ix
úhel 0° úhel 90° úhel 180°
Scos = 1 Scos = -1Scos = 0
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Pearsonův korelační koeficient
31
21
21
21cos
.
.
),(
xx
xx
xx
T
S 
Metrika kosinové podobnostiPearsonův korelační koeficient
21
21
21
.
.
),(
dd
d
T
d
PCS
xx
xx
xx 
kde 𝐱 𝑑𝑖 = x 𝑖1 − തx 𝑖, x 𝑖2 − തx 𝑖, … , x 𝑖𝑝 − തx 𝑖
𝑇
𝐱 𝑑𝑖 jsou tzv. diferenční vektory
také nabývá hodnot z intervalu -1;1
odvození metriky vzdálenosti:
2
),(1
),( 21
21
xx
xx PC
PC
S
D


→ hodnoty se (díky dělení dvěma) vyskytují
v intervalu 0;1
→ používá se např. při analýze dat genové exprese
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
32
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metriky pro určení podobnosti 2 objektů s kvalitativními prom.
33
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.)
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
𝐀 𝐱, 𝐲 =
0 1 0
1 2 0
1 0 1
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
34
Obecné metriky – Hammingova metrika podobnosti
),(),( yxyx HQHQ DpS 
Příklad:
dHQ(x,y) = 3
liší se ve 3 souřadnicích
dHQ(x,y) = 3
3 prvky mimo diagonálu
sHQ(x,y) = 6 – 3 = 3 sHQ(x,y) = 6 – 3 = 3
x = (0, 1, 2, 1, 2, 1)T
y = (1, 0, 2, 1, 0, 1)T
𝐀 𝐱, 𝐲 =
0 1 0
1 2 0
1 0 1
shoda ve 3 souřadnicích součet prvků na diagonále roven 3
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 35
Obecné metriky – Tanimotova metrika
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é.






1k
1i
1k
0j
ijx an 





1k
0i
1k
1j
ijy an













 1
1
1
1
1
1
),( k
i
k
j
ijyx
k
i
ii
TQ
ann
a
nnn
n
S
YXYX
YX
yx
x=0
x=1
x=2
y=0 y=1 y=2
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 36
Obecné metriky – Tanimotova metrika – příklad
Určete hodnoty Tanimotových podobností sTQ(x,x), sTQ(x,y) a sTQ(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 symbolů F = {0, 1, 2}, k = 3, p = 6.
Kontingenční tabulky jsou:











200
030
001
),( xxA











002
102
100
),( zxA
1
555
5
),( 

xxTQs 5,0
345
3
),( 

yxTQs 0
125
0
),( 

zxTQs











101
021
010
),( yxA
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 37
• definovány pomocí různých prvků kontingenční matice A(x,y)
Další obecné metriky
• některé z nich používají pouze počet shodných pozic
v obou vektorech (ovšem s nenulovými hodnotami):
• některé z nich používají i shodu s nulovými hodnotami:
p
a
S
k
i
ii



1
1
1 ),( yx
00
1
1
2 ),(
ap
a
S
k
i
ii





yx
p
a
S
k
i
ii



1
0
3 ),( yx
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 38
Asociační koeficienty
A - u obou objektů sledovaný jev nastal (obě odpovídající si proměnné mají
hodnotu true, resp.1) – pozitivní shoda;
B - u objektu xi jev nastal (xik = true), zatímco u objektu xj nikoliv (xjk = false, resp.0);
C - u objektu xi jev nenastal (xik = false), zatímco u objektu xj ano (xjk = true);
D - sledovaný jev nenastal ani u jednoho z objektů (obě odpovídající si
proměnné mají hodnotu false, resp. 0) – negativní shoda.
A
D
B
C
Při výpočtu podobnosti dvou objektů sledujeme, kolikrát pro všechny souřadnice
obou vektorů xj a xj 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)
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 39
Jaccardův – Tanimotův asociační koeficient
což je díky zjednodušení i dichotomická varianta metriky podle vztahu:
CBA
A
SJT

),( yx









 1
1
1
1
1
1
),( k
i
k
i
ijyx
k
i
ii
TQ
ann
a
S yx
Tento vztah se dominantně používá v ekologických studiích.
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 40
Další asociační koeficienty I
DCBA
A
SRR

),( yx
dichotomická varianta
metriky:
p
a
S
k
i
ii



1
1
1 ),( yx
Russelův – Raoův asociační koeficient
Sokalův – Michenerův asociační koeficient
DCBA
DA
SSM


),( yx dichotomická varianta
metriky:
p
a
S
k
i
ii



1
0
3 ),( yx
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 41
Další asociační koeficienty II
Diceův (Czekanowského) asociační koeficient
)()(
2
2
2
),(
CABA
A
CBA
A
SDC



yx
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
)()()(2
),(
DCBACB
DA
CBDA
DA
SRT





yx
Hamanův asociační koeficient
DCBA
CBDA
SHA



)(
),( yx
nabývá na rozdíl od všech dříve uvedených
koeficientů hodnot z intervalu -1, 1. Hodnoty -1,
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ů
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 42
Asociační koeficienty – poznámka
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
Euklidova metrika
Pearsonův korelační koeficient
CBDH ),( yx
CBDH ),( yx
)()()()(
),(
DBCADCBA
CBDA
SPC


yx
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 43
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í:
),(1),( yxyx XX SD 
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 44
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
• ‘minkowski’ – 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é)
• ‘jaccard’ – 1 mínus Jaccardův koeficient
• lze případně nadefinovat i jinou metriku
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metriky pro určení vzdálenosti
mezi dvěma skupinami objektů
45
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
46
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách 47
• vzdálenost mezi skupinami dána:
Vzdálenost mezi skupinami objektů
• 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
– „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í
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Typy metrik a konkrétní příklady
48
Metriky pro určení vzdálenosti mezi
2 objekty s kvantitativními proměnnými
Deterministické metriky pro určení
vzdálenosti mezi 2 množinami objektů
MEZI DVĚMA OBJEKTY
Metriky pro určení podobnosti 2 objektů
s kvantitativními proměnnými
Metriky pro určení podobnosti 2 objektů
s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 objekty s kvalitativními proměnnými
Metriky pro určení vzdálenosti mezi
2 množinami objektů používající jejich
pravděpodobnostní charakteristiky
Euklidova m., Hammingova (manhattanská) m.,
Minkovského m., Čebyševova m., Mahalanobisova m.,
Canberrská m.
Skalární součin, m. kosinové podobnosti, Pearsonův
korelační koeficient, Tanimotova m.
Hammingova m.
Chernoffova m., Bhattacharyyova m. atd.
Tanimotova m., Jaccardův-Tanimotův a.k., RusselůvRaovův
a.k., Sokalův-Michenerův a.k., Dicův k.,
Rogersův-Tanimotův k., Hamanův k.
Metoda nejbližšího souseda, k nejbližších
sousedů, nejvzdálenějšího souseda, centroidová
metoda, m. průměrné vazby, Wardova metoda
MEZI DVĚMA SKUPINAMI OBJEKTŮ
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Metriky založené na pstních charakteristikách
49
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:
3. J nabývá maxima, pokud jsou obě množiny
disjunktní, tj. když
1. J = 0, pokud jsou hustoty pravděpodobnosti
obou množin identické, tj. když
p(x|1) = p(x|2)
2. J > 0



 0)ω()ω( 2 xxx 1 dpp
x1
f(x1)
x1
x2
x1
f(x1)
x1
f(x1)
x1
x2
x1
x2
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Asociační matice
50
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
proměnná1
proměnná2
proměnná3
objekt 1
objekt 2
objekt 3
objekt 4
objekt 5
objekt 6
Asociační matice – Q mode analýza
51
Hodnoty proměnných pro jednotlivé objekty
NxP MATICE ASOCIAČNÍ MATICE
Výpočet metriky
podobností/
vzdáleností
Vzdálenost, podobnost, korelace,
kovariance mezi objekty
objekt 1
objekt 2
objekt 3
objekt 4
objekt 5
objekt 6
objekt1
objekt2
objekt3
objekt4
objekt5
objekt6
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Asociační matice – R mode analýza
52
Hodnoty proměnných pro jednotlivé objekty
NxP MATICE ASOCIAČNÍ MATICE
Výpočet metriky
podobností/
vzdáleností
proměnná1
proměnná2
proměnná3
proměnná1
proměnná2
proměnná3
proměnná 1
proměnná 2
proměnná 3
Vzdálenost, podobnost, korelace,
kovariance mezi proměnnými
objekt 1
objekt 2
objekt 3
objekt 4
objekt 5
objekt 6
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
Asociační matice – ukázka
53
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
Vzdálenost měst v mapě
není ničím jiným než
maticí vzdálenosti v 2D
prostoru
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
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
54
• 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ů
Koriťáková, Dušek: Pokročilé metody analýzy dat v neurovědách
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“
55