Analýza a klasifikace dat - přednáška 3 MU RNDr. Eva Janousova IBA » Podzim 2015 Typy klasifikátorů - podle principu klasifikace klasifikace pomocí diskriminačních funkcí: - diskriminační funkce určují míru příslušnosti k dané klasifikační třídě - pro danou třídu má daná diskriminační funkce nejvyšší hodnotu O ° o O O-K klasifikace pomocí vzdálenosti od etalonů klasif. tříd: - etalon = reprezentativní objekt(y) klasifikační třídy - počet etalonů klasif. třídy různý - od jednoho vzorku (např. centroidu) po úplný výčet všech objektů dané třídy (např. u klasif. pomocí metody průměrné vazby) tr-*o v A A A A o o \A A klasifikace pomocí hranic v obrazovém prostoru: - stanovení hranic (hraničních ploch) oddělujících klasifikační třídy Xn o 0 o, ,< o o/a /AAfA A A A A x. Janoušová: Analýza a klasifikace dat iba Poznámka • jednotlivé objekty je možno znázornit pomocí bodů 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 o 12 • pacienti | 11 • kontroly _^ _c 10 • u -r 9 • o | 8 • o 6 IZľ 05 • y| I_I_I_I_I_I 1 2 3 4 5 6 Objem hipokampu Janoušová: Analýza a klasifikaci ^ba ^ Metrika - vzdálenost Metrika D na X je funkce D: X x x —> R, kde R je množina reálných čísel taková, že: 3D0gR: -oo < D0< D(x,y) < +00, Vx,y g X D(x,x) = D0, Vx g X a D(x,y) = D(y,x), Vx,y g X (symetrie) D(x, y) = D0 když a jen když x = y (totožnost) D(x, z) < D(x, y) + D(y, z), Vx,y,z g X fzl nerovnost) Prostor X, ve kterém metrika D definována, nazýváme metrickým prostorem. Vzdálenost je hodnota určená podle metriky. Poznámka: zpravidla D0=0. MU Janoušová: Analýza a klasifikace dat (^J Metrika - podobnost Metrická míra podobnosti 5 na X je funkce 5: X x x —> R, taková, že: 3 50g R: -co < 5(x,y) < 50< +co, Vx,y g X 5(x,x) = 50, Vx g X a 5(x,y) = 5(y,x), Vx,y g X (symetrie) 5(x,y) = 50 když a jen když x = y (totožnost) S(x,y)-S(y,z) < [5(x,y) + 5(y,z)]-5(x,z), Vx,y,z g X Podobnost je hodnota určená podle metrické míry podobnosti. Poznámka: zpravidla 50=1 (ale neplatí to vždy, u některých metrik je maximální hodnota podobnosti jiná než 1) MU Janoušová: Analýza a klasifikace dat |yj 5 Metriky podobnosti vs. metriky vzdálenosti Vzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např.: 5« = S:= = c - D,, c > max D,, Vi,j MU Janoušová: Analýza a klasifikace dat (yj 6 Typy měr vzdálenosti (podobnosti) )- • podle typu proměnné (kvalitativní proměnné, kvantitativní proměnné) • podle počtu objektů, jejichž vztah hodnotíme - objekty (vektory), množiny objektů (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á: Analýza a klasifikace dat (^J 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. 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á: Analýza a klasifikace dat iba 8 Metriky pro určení vzdálenosti mezi dvěma objekty MU Janoušová: Analýza a klasifikace dat |yj g 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á: Analýza a klasifikace dat iba Nejpoužívanější metriky pro určení vzdálenosti mezi dvěma objekty s kvantitativními proměnnými Euklidova metrika Hammingova (manhattanská) metrika Minkovského metrika Čebyševova metrika Mahalanobisova metrika Canberrská metrika Janoušová: Analýza a klasifikace dat *jL ^Jgp ^ Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou geometrickou interpretací DE(x1,x2) = / (Xli - X2i): "1 = 1 o u > 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 [ 10 [ 8 pacienti kontroly testovací subjekt 2 3 4 5 6 Objem hipokampu Janoušová: Analýza a klasifikace dat 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) MU Janoušová: Analýza a klasifikace dat |yj 13 Hammingova (manhattanská) metrika • v AJ názvy: Manhattan distance, city-block distance, taxi driver distance DH(xlfx2) = ) |x1£ — x2í| "1=1 • nižší výpočetní nároky než Euklidova metrika -> použití v úlohách s vysokou výpočetní náročností MU Janoušová: Analýza a klasifikace dat |yj 14 Hammingova (manhattanská) metrika £>//(xi,x2) = / |Xii -x2í| "1=1 13 12 11 10 o u > o M o CD o J 12 3 4 5 6 Objem hipokampu o u ->■ > O M O E E CD Iq 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á: Analýza a klasifikace dat IBA M 15 Minkovského metrika • zobecněním Euklidovy a Hammingovy (manhattanské) metriky DM(xltx2) = \^iJxli-x2i\mj • 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(xl9x2) = lim DM(xl9x2) = maxlxii -x2i\ ?n->oo Vi MU s"*.} Janoušová: Analýza a klasifikace dat |yj 16 Čebyševova metrika )- • odvozena z Minkovského metriky pro m -> oo ^c(xi,x2) = maxlxii -x2i\ 13 13 O (_) > O M O 12 11 10 l o u > o M o 12 11 10 l pacienti kontroly testovací subjekt □ cu Iq o cu Iq o 1 2 3 4 5 6 Objem hipokampu 2 3 4 5 6 Objem hipokampu Janoušová: Analýza a klasifikace dat iba W 17 Čebyševova metrika • odvozena z Minkovského metriky pro m -> oo 0c(xi,x2) = maxlxii -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 MU Janoušová: Analýza a klasifikace dat |yj 18 Srovnání metrik Pc Pe Ph .. Čebyševova metrika .. Euklidova metrika ,.. Hammingova (manhattanská) metrika Janoušová: Analýza a klasifikace dat iba W 19 Srovnání metrik )- • pokud je potřeba použít „euklidovskou" metriku, ale s nižší výpočetní náročností, používá se v první řadě Hammingova nebo Čebyševova metrika • případně kombinace obou metrik: DA(xlfx2) = max(2DH/3; Dc) • geometrickým místem bodů s toutéž vzdáleností je pak ve dvourozměrném prostoru osmiúhelník MU Janoušová: Analýza a klasifikace dat |yj 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í 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) = Gf=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) hu ...... Janoušová: Analýza a klasifikace dat *|L |yj 21 Canberrská metrika relativizovaná varianta Hammingovy (manhattanské) metriky 0 t—r ^—'i = l |Xii| + |x2íl • vhodná pro proměnné s nezápornými hodnotami • pokud se vyskytují nulové hodnoty: - pokud jsou obě hodnoty 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 objekty 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á: Analýza a klasifikace dat *|L |yj 22 Příklad la I- Jsou dány dva vektory x1 = (0,001; 0,001)T a x2 = (0,01; 0,01)T. Předpokládejme, že se souřadnice prvního vektoru změní na = (0,002; 0,001)T. Jaká je Hammingova (manhattanská) a canberrská vzdálenost v obou případech a jaká je relativní změna vzdáleností, vyvolaná uvedenou modifikací? dH(x1,x2) = |0,001 - 0,01| + |0,001 - 0,01| = 0,009 + 0,009 = 0,018 dHlx'1,x2) = |0,002 - 0,01| + |0,001 - 0,01| = 0,008 + 0,009 = 0,017 , f -v |0,001-0,01| |0,001-0,01| 0,009 0,009 . 110 c a a^fx^x?) — ■-i—:-- +--—-- =----= 1,6364 lak i> lj |0,001| + |0,01| |0,001| + |0,01| 0,011 0,011 ' A r , >> |0,002-0,01| |0,001-0,01| 0,008 0,009 « AOAn dcA (x i, x2) = i-—-- +--—-- =--1--= 1,4849 lak i> lj |0,002| + |0,01| |0,001| + |0,01| 0,012 0,011 Relativní změny vzdáleností, určující citlivost té které metriky, které jsou způsobeny změnou hodnoty první souřadnice, jsou: ^ _ Mfí(xi,x2)-dfí(x/1,x2)| _ |0,018-0,017| _ 0,001 _ H dH(x1,x2) 0,018 0,018 ' ^ _ McA(xi,x2)-dCA(x/1,x2)| _ |1,6364-1,4849| _ ^ CA dcA(xi,x2) 1,6364 Ze získaných výsledků je zřejmé, že relativní změna vzdáleností je v případě canberrské metriky pro toto zadání téměř dvakrát větší. MU Janoušová: Analýza a klasifikace dat |yj 23 Příklad lb Nyní mějme dány dva vektory x1 = (1000; 1000)T a x2 = (100; 100)T a předpokládejme, že se souřadnice prvního vektoru změní na x\ = (1002; 1000)T. Jaká je Hammingova (manhattanská) a canberrská vzdálenost v obou případech a jaká je relativní změna vzdáleností, vyvolaná uvedenou modifikací? dH(x1,x2) = 11000 - 100| + 11000 - 100| = 900 + 900 = 1800 dHlx'1,x2) = |1002 - 100| + 11000 - 100| = 902 + 900 = 1802 , , v |1000-100| , |1000-100| 900 , 900 „ r^rA drAx^Xn) = t-r-t—7 + 7-r-t—i =-+-= 1,6364 lak i> lj |1000| + |100| |iooo| + |ioo| 1100 1100 ' , , , x |1002-100 , 11000-100 902 , 900 „ r^r-, drAx'^Xn) = 7-—-T + 7-——- = -+-= 1,6367 lak i> lj |1002| + |100| |1000| + |100| 1102 1100 Relativní změny vzdáleností, určující citlivost té které metriky, které jsou způsobeny změnou hodnoty první souřadnice, jsou: ^d _ Mfí(x1,x2)-dfí(x/1,x2)| _ |1800-1802| _ 2 _ H dH(x1,x2) 1800 1800 ' ^ _ McA(xi,x2)-dCA(x/1,x2)| _ |l,6364-l,6367| _ q QQQ^g CA dcA(xi,x2) 1,6364 Ze získaných výsledků je zřejmé, že citlivost canberrské metriky je v tomto případě radové nizsi. MU Janoušová: Analýza a klasifikace dat |yj 24 Nelineární metrika pN(X1,X2) = < O kdyžpE(x1,x2) D kde D je prahová hodnota a H je nějaká konstanta i když existují doporučení, jak volit obě hodnoty na základě statistických r(n/2) vlastností vektorového prostoru (např. pomocí H = ——= ), výhodnější je Dnynn volit obě hodnoty 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á: Analýza a klasifikace dat |yj 25 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á: Analýza a klasifikace dat iba W 26 Příklad Předpokládejme, že množina F obsahuje symboly {0,1, 2}, tj. k = 3a 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 i=0 j=0 Janoušová: Analýza a klasifikace dat 27 Hammingova metrika vzdálenosti DHQ(*>y) = Téllav z=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 dHQ(x,v) = 3 A(x, y) = 0 1 LI 1 0 2 0 0 1 3 prvky mimo diagonálu dHQ(*>v) = 3 Janoušová: Analýza a klasifikace dat iba W 28 Hammingova metrika vzdálenosti • pro k-2, kdy jsou hodnoty obou vektorů binární, se definiční vztah Hammingovy vzdálenosti transformuje na: p dhqb 0> y) = Z (*/+y t ~ 2x^) 7=1 kde třetí člen v závorce kompenzuje případ, kdy jsou hodnoty Xj i Vj rovny jedné a součet prvních členů v závorce je tím pádem roven dvěma, nicméně nastává shoda hodnot, která k celkové vzdálenosti nemůže přispět. • protože x, a y, nabývají hodnot pouze 0 a 1, můžeme také psát: p p dhqb y) = ZK~^ 7=1 MU Janoušová: Analýza a klasifikace dat |yj 29 Hammingova metrika vzdálenosti - příklad 2 Určete Hammingovu vzdálenost binárních vektorů x = (0,1,1, 0,1)T a y = (1,0,0, 0,1)T. Podle definičního principu (tzn. počet pozic, ve kterých se oba vektory liší): p Dle jiného vztahu: dHQB{\,y) = +yl-2x,yl) = = (0+1-2-0-1) + (1+0-2-1-0) + (1+0-2-1-0) + (0+0 - 2 • 0 • 0) + (1+1 - 2 -1 • 1) = 3 P Dle dalšího vztahu: dHQB(x,y) = ^(xi -yt)2 = i=\ = (0-l)2 + (1-0)2 + (l-0)2+ (0-0)2+ (l-l)2 =1 + 1 + 1 + 0 + 0 = 3 p Dle posledního vztahu: dHQB(x,y) = ^\xt -yi i=\ = |0-l| + |l-0| + |l-0| + |0-0 + 1 = 1 + 1 + 1 + 0 + 0 = 3 -1 IBA IMI 30 Hammingova metrika vzdálenosti V případě bipolárních vektorů, kdy jednotlivé složky ^ p vektorů nabývají hodnot +1 a -1, je Hammingova vzdálenost určena vztahem: ^hqp (*,y) = V '=1 J Příklad 3: Určete Hammingovu vzdálenost bipolárních vektorů x = (l, 1,1,-1, l)Ta y = (1,-1,1,-1,-1)1 Podle definičního principu (tzn. počet pozic, ve kterých se liší): dHQP(x,y) = 2 Z kontingenční matice (součet prvků mimo hlavní diagonálu): A(x,y) = |^ Pomocí vztahu: d u ) = 5-((M) + (l•(-!)) + (!-1) + ((-!)• (-!)) + (!• (-1)))= S-Q-l + 1 + 1-1) = 5-1 = 2 HU Janoušová: Analýza a klasifikace dat *|L (yj 3^ Metriky pro určení podobnosti mezi dvěma objekty Janoušová: Analýza a klasifikace dat 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á: Analýza a klasifikace dat iba W 33 Skalární součin n ^jj(X1'X2) ~~ Xl *X2 ~~ ^ltXliX2i i=\ 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 =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,(X1?X2) = ^2-^(X19X2) MU Janoušová: Analýza a klasifikace dat |yj 34 Metrika kosinové podobnosti ^cos (Xl 5 X2 ) - T Xl -X2 kde ||xí|| je norma (délka) vektoru x, = 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 180ť 5 = 1 5 = 0 5 = -1 ucos ucos ucos Janoušová: Analýza a klasifikace dat *jL |yj 35 Pearsonův korelační koeficient Pearsonův korelační koeficient Metrika kosinové podobnosti S PC (Xl 5 X2 ) — T Xdl'Xd2 "dl 'dl ^cos (Xl 5 X2 ) - T Xl -X2 kde = (xn — Xi, x^2 — Xj, ■■■, Xjp — x^) xdi jsou tzv. diferenční vektory také nabývá hodnot z intervalu <-l;l> odvození metriky vzdálenosti: ^Vc(Xl> X2) — ^_^Pc(Xl'X2) -> hodnoty se (díky dělení dvěma) vyskytují v intervalu (0;1) -> používá se např. při analýze dat genové exprese Janoušová: Analýza a klasifikace dat iba W 36 Tanimotova metrika podobnosti ST (Xj, x2) — t Xl X2 2 xl + x2 Xl X2 Přičteme-li a odečteme-li ve jmenovateli výraz x1Tx2 a podělíme-li čitatele i jmenovatele zlomku toutéž hodnotou, dostaneme ST(x],x2) - 1 (Xl-X2)r(Xl-X2) 1+ t Xl X2 Tanimotova podobnost vektorů x2 a x2 je nepřímo úměrná kvadrátu Euklidovy vzdálenosti vektorů x2 a x2 vztažené k jejich skalárnímu součinu. Pokud skalární součin považujeme za míru korelace obou vektorů, můžeme formulovat výše uvedený vztah tak, že ST(x1/x2) je nepřímo úměrná kvadrátu Euklidovy vzdálenosti podělené velikostí jejich korelace, což znamená, že je korelaci, jako míře podobnosti přímo úměrná. Janoušová: Analýza a klasifikace dat (|^) 37 „Bezejmenná" metrika podobnosti 5fc(x1,x2) -1 DE(xvx2) + Vzdálenost podle metriky je rovna jedné, když x1 = x2 a svého minima (tj. Sc(xl,x2)= -1) nabývá, když x1 = -x2. MU Janoušová: Analýza a klasifikace dat |yj 38 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á: Analýza a klasifikace dat iba W 39 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.) MU Janoušová: Analýza a klasifikace dat |yj 40 Obecné metriky - Hammingova metrika podobnosti sHQ(^y) = p-DHo(^y) HQ Příklad: x = (0, 1, 2, 1, 2, 1)T y = (1, 0, 2,1, 0,1)T liší se ve 3 souřadnicích dHQ(*>V) = 3 shoda ve 3 souřadnicích sHQ(x,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á: Analýza a klasifikace dat iba W 41 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é. x=0 x=l x=2 y=0 (0,0) i=l j=l y=l y=2 (1,0) (2,0) n X (0,1) (0,2) w(i,ir\(i,2)4 (2,1)\(2,2) n Xa v_4 -— Janoušová: Analýza a klasifikace dat W 42 Obecné metriky -Tanimotova metrika - příklad Určete hodnoty Tanimotových podobností srQ(x,x), srQ(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 symbolu F = {0,1, 2}, k = 3, p = 6. Kontingenční tabulky jsou: A(x, x) = "1 0 0] o< 0 '3S0 t-_-^J 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 ■?ro(x»y)= . ■ „ =°>5 Sro(x,z) =-= ° 5+4-3 5 + 2-1 Janoušová: Analýza a klasifikace dat iba M 43 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-\ k-i 5, (x,y) = -«=!— S2(x,y)= P p-a oo některé z nich používají i shodu s nulovými hodnotami: k-i P Janoušová: Analýza a klasifikace dat *jL (yj 44 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á: Analýza a klasifikace dat *|L |yj 45 Jaccardův-Tanimotův asociační koeficient S,r(x,y) = A A + B + C Xi false/0 true/1 false/0 D true/1 B což je díky zjednodušení i dichotomická varianta metriky podle vztahu: STQ(*,y) = k-l k-1 + X y a.. i=l i=l Tento vztah se dominantně používá v ekologických studiích. Janoušová: Analýza a klasifikace dat jjjjp 45 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 ii SRR(x,y)= A + B + c + D metriky: ^(x,y) = ^— Sokalův - Michenerův asociační koeficient k-i n / \ _ A + D dichotomická varianta ^jaa *sm{X'J)-A + B + C + D metriky: S^,y) = ^— MU Janoušová: Analýza a klasifikace dat |yj 47 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 , 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, g / ._A + D — (B + C) pokud se příznaky pouze neshodují; hodnoty 0, když ha\ >JJ ^ + 2? + C + .D je počet shod a neshod v rovnováze;+1 v případě úplné shody všech příznaků Janoušová: Analýza a klasifikace dat *|L |yj 43 Asociační koeficienty - poznámka Xi false/O true/1 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 D (x, y) = B + C Euklidova metrika DH(x,y) = jB + C Pearsonův korelační koeficient AD-B-C -SI(A + B)-(C + D)-(A + C)-(B + D) Janoušová: Analýza a klasifikace dat iba W 49 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í: Dx(x,y) = l-Sx(x,y) MU Janoušová: Analýza a klasifikace dat |yj 50 Metriky pro určení vzdálenosti mezi dvěma skupinami objektů Janoušová: Analýza a klasifikace dat 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) objektů či „vzdáleností" jednoho objektu z každé skupiny - použitelné při shlukování • zavedeme funkci, která ke každé dvojici skupin objektů (Q, C) přiřazuje číslo D(Cj, Cj), které podobně jako míry podobnosti či nepodobnosti (metriky) jednotlivých objektů musí splňovat minimálně podmínky: (51) D(c„Cj)>0 (52) D(C„ Cj) = D(q, C,) (53) D(q, Q) = maxuD(Cj/ 0) (pro míry podobnosti) (S3') D(Cj, Cj) = 0 pro všechna i (pro míry vzdálenosti) MU Janoušová: Analýza a klasifikace dat |yj 52 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á: Analýza a klasifikace dat iba W 53 Nejpoužívanější metriky pro určení vzdálenosti mezi dvěma množinami objektů Metoda nejbližšího souseda Metoda k nejbližších sousedů Metoda nejvzdálenějšího souseda Metoda průměrné vazby Wardova metoda Janoušová: Analýza a klasifikace dat *jL 54 Metoda nejbližšího souseda je-li d libovolná míra nepodobnosti (vzdálenosti) dvou objektů a^a cůj jsou libovolné skupiny objektů, potom metoda nejbližšího souseda definuje mezi skupinami cúi a cúj vzdálenost DNN{coi,(oj) = rnmd(x ,x ) a a □ □ xpgcol I„Effl, h j □ pacienti A kontroly O testovací subjekt -> testovací subjekt zařadíme do třídy, ze které je jeho nejbližší soused x1 výhody a nevýhody použití této metody pro klasifikaci: žádné předpoklady o rozložení - citlivé na odlehlé hodnoty - zpravidla nevhodné při nevyvážených počtech objektů ve skupinách iba W 55 Metoda k nejbližších sousedů zobecněním metody nebližšího souseda definována vztahem D^ico^co^ = mm^d(xp,xq\ tzn. vzdálenost dvou xr,&a> J shluků je definována součtem nejkratších vzdáleností mezi objekty obou skupin a a a □ pacienti A kontroly O testovací subjekt -> testovací subjekt zařadíme do třídy, která převažuje mezi jeho k nejbližšími sousedy i- Xl • výhody a nevýhody použití této metody pro klasifikaci: žádné předpoklady o rozložení + méně citlivé na odlehlé hodnoty - zpravidla nevhodné při nevyvážených počtech objektů ve skupinách l ^ Metoda nejvzdálenějšího souseda opačný princip než metoda nejbližšího souseda: dfh(q,q) = maxd(xD,xa) pozn.: pro klasifikaci je obtížně použitelná pozn. 2: je možné zobecnění i pro více nejvzdálenějších sousedů k DFNk(Ci,Ci) = max^d(x x ), MU s"*.} Janoušová: Analýza a klasifikace dat ^ ^ Centroidová metoda • vychází z výpočtu centroidů pro jednotlivé skupiny • při klasifikaci: zařazení objektu do skupiny s nejbližším centroidem □ pacienti A kontroly O testovací subjekt + centroid pacientů + centroid kontrol • výhody a nevýhody použití této metody pro klasifikaci: žádné předpoklady o rozložení méně citlivé na odlehlé hodnoty než metoda nejbližšího souseda + nebývá problém při nevyvážených počtech objektů ve skupinách Metoda průměrné vazby \- • vzdálenost dvou tříd je průměrná vzdálenost mezi všemi objekty těchto tříd • při klasifikaci: zařazení subjektu do skupiny s nejmenší průměrnou vzdálenosti od všech objektů dané skupiny □ pacienti A kontroly O testovací subjekt • výhody a nevýhody použití této metody pro klasifikaci: žádné předpoklady o rozložení méně citlivé na odlehlé hodnoty než metoda nejbližšího souseda + nebývá problém při nevyvážených počtech objektů ve skupinách - časově náročnější než centroidová metoda při větším počtu objektů l j^j Wardova metoda • vzdálenost mezi třídami (shluky) je definována přírůstkem součtu čtverců odchylek mezi těžištěm a objekty shluku vytvořeného z obou uvažovaných shluků d a Cj oproti součtu čtverců odchylek mezi objekty a těžišti v obou shlucích d a Cr • pozn. (při použití Wardovy metody pro shlukování): Metoda má tendenci vytvářet shluky zhruba stejné velikosti, tedy odstraňovat shluky malé, resp. velké. • pozn. 2: pro klasifikaci se používá zřídka MU Janoušová: Analýza a klasifikace dat |yj 60 Příklad 2 Bylo provedeno měření objemu hipokampu a mozkových komor (v cm3) u 3 "2 12" "5 7" pacientů se schizofrenií a 3 kontrol: XD = 4 10 »xH — 3 9 .3 8 . .4 5. Určete, zda testovací subjekt x = [3,5 9] patří do skupiny pacientů či kontrolních subjektů pomocí různých metod klasifikace podle minimální vzdálenosti. o E o u > o _^ M O E E O 13 12 11 10 9 8 7 6 5 4 pacienti kontroly testovací subjekt 2 3 4 5 Objem hipokampu Janoušová: Analýza a klasifikace dat iba W 61 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á: Analýza a klasifikace dat iba W 62 Metriky založené na pstních charakteristikách Klasifikační třídy (množiny objektů se společnými charakteristikami) nemusí být definovány jen výčtem objektů, ale i vymezením obecnějších vlastností: • definicí hranic oddělujících část obrazového prostoru náležející dané klasifikační třídě • diskriminační funkcí • pravděpodobnostními charakteristikami výskytu objektů v dané třídě • atd. MU Janoušová: Analýza a klasifikace dat |yj 63 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 objektů 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 ^(xoDj) •p(x(ů2)dx = 0 -oo f(Xl) f(Xl) f(Xl) (Jak vidíme, není mezi vlastnostmi pravděpodobnostních metrik uvedena trojúhelníková nerovnost, jejíž splnění by se zajišťovalo velmi obtížně.) iba W 64 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á: Analýza a klasifikace dat iba W 65 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 66