Analýza a klasifikace dat přednáška 3 MU RNDr. Eva Janousova IBA » Podzim 2014 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 0+. 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) ^A 0 0 v A A+" A A A A A klasifikace pomocí hranic v obrazovém prostoru: - stanovení hranic (hraničních ploch) oddělujících klasifikační třídy o ° o o o+ o • <>,' ✓'A o O/ ✓'A A+A A A A A Janoušová: Analýza a klasifikace dat IBA Ml 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 > x# — 3 9 .3 8. .4 5. 13 o > O M O) O 12 11 10 9 8 7 6 5 2 3 4 5 Objem hipokampu • pacienti • kontroly Janoušová: Analýza a klasifikace dat IBA m 3 Metrika - vzdálenost Metrika p na X je funkce p: X x X —» R, kde R je množina reálných čísel, taková, že: 3p0eR: -oo < p0< p(x,y) < +00, Vx,y g X p(x,x) = p0, Vx g X a p(x,y) = p(y,x), Vx,y g X (symetrie) p(x, y) = p0 když a jen když x = y (totožnost) p(x, z) < p(x, y) + p(y, z), Vx,y,z g X (A nerovnost) Prostor X, ve kterém metrika p definována, nazýváme metrickým prostorem. Vzdálenost je hodnota určená podle metriky. Poznámka: zpravidla p0=0. Janoušová: Analýza a klasifikac Metrika - podobnost Metrická míra podobnosti s na X je funkce p: X x X -» R, taková, že: 3s0e R: -qo < s(x,y) < s0< +qo, Vx,y g X s(x,x) = s0, Vx g X a s(x,y) = s(y,x), Vx,y g X (symetrie) s(x,y) = s0 když a jen když x = y (totožnost) s(x,y).s(y,z) < [s(x,y) + s(y,z)].s(x,z), Vx,y,z g X Podobnost je hodnota určená podle metrické míry podobnosti. MU Janoušová: Analýza a klasifikace d 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ř. Sij = l/Pij S„ = 1/(1+ Pii) sn = c - pjj, c > max p,, Vij Janoušová: Analýza a klasifikace dat *jL [^J.. 5 Typy měr vzdálenosti (podobnosti) i- • dle typu proměnné (kvalitativní proměnné, kvantitativní proměnné) • dle objektů, jejichž vztah hodnotíme - obrazy (vektory), množiny obrazů (vektorů), rozdělení • 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ě nelze doporučit vhodnou metriku pro danou situaci Janoušová: Analýza a klasifika ;J^J Metriky pro určení vzdálenosti mezi dvěma obrazy s kvantitativními proměnnými Janoušová: Analýza a klasifikace dat 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á: Analýza a klasifikace dat ^ Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou interpretací DE(x1,x2) = Zn Oii - x2;): i=l geometrickou 13 12 11 o E 10 o -C U 9 > o 8 M o E 7 E aj -Q O 6 2 3 4 5 Objem hipokampu o > O M O (D o 13 12 11 10 1 2 3 4 5 Objem hipokampu pacienti kontroly testovací subjekt IBA W io Euklidova metrika zřejmě nejpoužívanější metrika s velmi názornou interpretací geometrickou DE(x1,x2) = Zn (xii - x2iy i=l 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í? čtverec euklidovské vzdálenosti (lépe se počítá než euklidovská vzdálenost) je mírou nepodobnosti, ale není metrikou Janoušová: Analýza a klasifikace dat IBA IMJ 11 Hammingova (manhattanská) metrika • v AJ názvy: Manhattan distance, city-block distance, taxi driver distance Zn |Xl£ -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 boduje hyperkrychle (ve dvourozměrném prostoru čtverec) MU Janoušová: Analýza a klasifikace dat *|L ^j ^2 Hammingova (manhattanská) metrika názvy v angličtině: Manhattan distance, city-block distance, taxi driver distance Di Z11 |Xl£ -X2£| i=l o E o -C O > o M o E E aj Iq o 13 12 11 10 J 2 3 4 5 Objem hipokampu o > O M (1> Iq o 13 12 11 10 pacienti kontroly testovací subjekt 1 2 3 4 5 Objem hipokampu IBA IMJ 13 Minkovského metrika zobecněním Euklidovy a Hammingovy (manhattanské) metriky l/m £>m(xi,x2) = ixii -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á: Analýza a klasifikac Čebyševova metrika >- • odvozena z Minkovského metriky pro m -> oo Z}c(xlfx2) = max|x1£ - x2i| E O) Iq o 13 12 11 O E io o o > o M O E ..1 2 3 4 5 Objem hipokampu o > o M O) 13 12 11 ° 10 _q o pacienti kontroly testovací subjekt 1 2 3 4 5 Objem hipokampu IBA IMJ 15 Čebyševova metrika odvozena z Minkovského metriky pro m -> oo Z}c(xlfx2) = rnaxlxii - x2i| Ví 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á: Analýza a klasifikace dat *jL .. ^6 Srovnání metrik \NPe ;__1_____ Pc Pe Ph Čebyševova metrika Euklidova metrika Hammingova (manhattanská) metrika Janoušová: Analýza a klasifikace dat IBA IMJ 17 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 • lepším přiblížením je kombinace obou metrik DA(xlrx2) = max(2DH/3; Dc) • geometrickým místem bodů s toutéž vzdáleností pak tvoří ve dvourozměrném prostoru osmiúhelník Janoušová: Analýza a klasifikace dat *jL .. ^8 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 Uij =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: JWxi,x2) = (zuai ■ \xu -x2in1/m 3. začleněním 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(x1-x2)r-S-1-(x1-x2) MU ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjjj ^9 Canberrská metrika relativizovaná varianta Hammingovy (manhattanské) metriky [2i IX1É — X' ^Ci4(Xi,X2) = > T—j ^1=1 |X!i| + |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é Janoušová: Analýza a klasifikace dat *jL .. 20 Příklad la I- Jsou dány dva vektory x2 = (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 x\ = (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 dH(x'1,x2) = |0,002 - 0,01| + |0,001 - 0,01| = 0,008 + 0,009 = 0,017 A , "\ |0,001-0,01| , |0,001-0,01| 0,009 , 0,009 . ^ r a flr4CXi,x2) = --—-- +--—-- =----= 1,6364 la\ ľ lj |0,001| + |0,01| |0,001| + |0,01| 0,011 0,011 A (v< v \ |0,002-0,01| , |0,001-0,01| 0,008 , 0,009 . AQAQ drA (x i, x2) = --—-■ +--—-- =----= 1,4849 la\ l> lj |o,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: ^ _ |dfí(x1,x2)-dfí(x^1,x2)| _ |0,018-0,017| _ 0,001 _ Q H dH(xi,x2) 0,018 0,018 ' ^ _ |dc^(x1,x2)-dc^(x^1,x2)| _ |1,6364-1,4849| _ q H dc^l(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ší. „ , . ., .... mmm 1 r Janousova: Analýza a klasifikace dat 21 Příklad lb I- 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 dH(x'1,x2) = |1002 - 100| + 11000 - 100| = 902 + 900 = 1802 , , . IlOOO-lOOl , IlOOO-lOOl 900 900 drAw>X-2J — ',-r-;-r + ;-r~,-: —----— 1,6364 la\ ľ lj |1000| + |100| |1000| + |100| 1100 1100 A (v< v \ 11002-1001 , 11000-1001 902 900 drA\X> i,x2) = --—-: +--—-- =----= 1,6367 lak l> 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 = |dfí(x1,x2)-dfí(x^1,x2)| = |1800-1802| _ 2 _ H dH(xi,x2) 1800 1800 ' ^ _ |dc^(xi,x2)-dc^(x^,x2)| _ |1,6364-1,6367| _ q qqq^o H dc^l(xi,x2) 1,6364 Ze získaných výsledků je zřejmé, že citlivost canberrské metriky je v tomto případě řádově nižší. ^ Janousova: Analýza a klasifikace dat (^jj - 22 Nelineární metrika PisiO^ľ^) — 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 vlastností vektorového prostoru (viz vzorec níže), výhodnější je volit obě hodnoty na základě expertní analýzy řešeného problému r(n/2) H = ve vztahu může figurovat jakákoliv metrika vzdálenosti, nejen Euklidova metrika Janoušová: Analýza a klasifikace dat *jL .. 23 Deterministické metriky pro určení vzdálenosti mezi dvěma množinami obrazů Janoušová: Analýza a klasifikace dat Podobnost a vzdálenost mezi třídami * podobnost mezi třídami dána: - „podobností" jednoho obrazu s jedním či více obrazy jedné třídy (skupin, shluků) - použitelné při klasifikaci - „podobností" skupin obrazů či „podobností" jednoho obrazu z každé skupiny -použitelné při shlukování * zavedeme funkci, která ke každé dvojici skupin obrazů (Q, C) přiřazuje číslo D(Cj, C), které podobně jako míry podobnosti či nepodobnosti (metriky) jednotlivých obrazů musí splňovat minimálně podmínky: (si) D(ci,q)>o (52) D(q,q) = D(q,q) (53) D(q, q) = maXj jD(q, q) (pro míry podobnosti) (S3') D(q, q) = 0 pro všechna i (pro míry vzdálenosti) Janoušová: Analýza a klasifikace dat *jL .. 25 Nejpoužívanější metriky pro určení vzdálenosti mezi dvěma množinami obrazů 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 d; Metoda nejbližšího souseda • je-li d libovolná míra nepodobnosti (vzdálenosti) dvou obrazů a q a q jsou libovolné skupiny obrazů, potom metoda nejbližšího souseda definuje mezi skupinami q a q vzdálenost DNN(q,q) = mind(xD,xa) xpeCi xqeCj □ pacienti A kontroly O testovací subjekt • pozn. (při použití metody nejbližšího souseda pro shlukování): Při použití této metody se mohou vyskytovat v jednom shluku často i poměrně vzdálené obrazy. Tzn. metoda nejbližšího souseda může generovat shluky protáhlého tvaru. MU ,-.*■»»., Janoušová: Analýza a klasifikac Metoda k nejbližších sousedu • zobecněním metody nebližšího souseda k • definována vztahem DNNk(Cj,Cj) = min V d(xD,xQ), tzn. vzdálenost dvou xpeCi " XqGCj shluků je definována součtem nejkratších vzdáleností mezi obrazy obou skupin A A □ pacienti A kontroly O testovací subjekt pozn. (při použití metody k nejbližších sousedů pro shlukování): Při shlukování částečně potlačuje generování řetězcových struktur. MU o--., (Mi 28 Janoušová: Analýza a klasifikace dat IBA Metoda nejvzdálenějšího souseda • pozn. (při použití metody nejvzdálenějšího souseda pro shlukování): Generování protáhlých struktur tato metoda potlačuje, naopak vede ke tvorbě nevelkých kompaktních shluků. • pozn. 2: pro klasifikaci je obtížně použitelná • pozn. 3: je možné zobecnění i pro více nejvzdálenějších sousedů k Janoušová: Analýza a klasifikace dat IBA IM) 29 Centroidová metoda • vychází z výpočtu centroidů pro jednotlivé skupiny • při klasifikaci: zařazení subjektu do skupiny s nejbližším centroidem A □ pacienti A kontroly O testovací subjekt + centroid pacientů + centroid kontrol Janoušová: Analýza a klasifikace dat IBA IMJ 30 Metoda průměrné vazby • vzdálenost dvou tříd Q a Cj je průměrná vzdálenost mezi všemi obrazy tříd C,a q • při klasifikaci: zařazení subjektu do skupiny s nejmenší průměrnou vzdálenosti od všech obrazů dané skupiny □ pacienti A kontroly O testovací subjekt MU Janoušová: Analýza a klasifikace dat 31 Wardova metoda • vzdálenost mezi třídami (shluky) je definována přírůstkem součtu čtverců odchylek mezi těžištěm a obrazy shluku vytvořeného z obou uvažovaných shluků Cj a C)- oproti součtu čtverců odchylek mezi obrazy a těžišti v obou shlucích q a Cy • 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 je obtížně použitelná Janoušová: Analýza a klasifikace dat *|L ^j 32 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 > — 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 > O "m 8 13 12 11 10 9 • pacienti • kontroly • testovací subjekt o; O 7 6 5 4 2 3 4 5 Objem hipokampu Janoušová: Analýza a klasifikace dat IBA IMJ 33 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" — -;- lvi 11 n i o i Lno i v w o r\ w i_ o i v i , ur v^ueidvdiii ÍOndvCR EVROPSKÁ UNIE MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost evropský sociální MINISTERSTVO ŠKOLSTVÍ, OP Vzdělávání INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Janoušová: Analýza a klasifikace dat