logo-IBA logo-MU © Institut biostatistiky a analýz INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. logo-IBA logo-MU © Institut biostatistiky a analýz IV. KLASIFIKACE PODLE MINIMÁLNÍ VZDÁLENOSTI levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIPY KLASIFIKACE þpomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě; þpomocí definice hranic mezi jednotlivými třídami a logických pravidel; þpomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd; þpomocí ztotožnění s etalony; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIPY KLASIFIKACE þpomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě; þpomocí definice hranic mezi jednotlivými třídami a logických pravidel; þpomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd; þpomocí ztotožnění s etalony; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz METRIKA - VZDÁLENOST þMetrika ρ na X je funkce ρ: X × X ® R, kde R je množina reálných čísel, taková, že: þ$ρ0ÎR: -¥ < ρ0 £ ρ(x,y) < +¥, "x,y Î X þρ(x,x) = ρ0, "x Î X þa þρ(x,y) = ρ(y,x), "x,y Î X. (symetrie) þKdyž dále þρ(x, y) = ρ0 když a jen když x = y (totožnost) èa ρ(x, z) £ ρ(x, y) + ρ(y, z), "x,y,z Î X. (D nerovnost) þ þProstor X, ve kterém metrika ρ definována, nazýváme metrickým prostorem. þVzdálenost je hodnota určená podle metriky. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz METRIKA PODOBNOSTI - PODOBNOST þMetrická míra podobnosti s na X je funkce s: X × X ® R, kde R je množina reálných čísel, taková, že: þ$s0ÎR: -¥ < s(x,y) £ s0< +¥, "x,y Î X þs(x,x) = s0, "x Î X þa þs(x,y) = s(y,x), "x,y Î X. (symetrie) þKdyž dále þs(x,y) = s0 když a jen když x = y (totožnost) èa s(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY PODOBNOSTI VS. NEPODOBNOSTI þVzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. þsij = 1/ρij þ þsij = 1/(1+ ρij) þ þsij = c - ρij, c ³ max ρij, "i,j þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY PODOBNOSTI VS. NEPODOBNOSTI þVzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. þsij = 1/ρij þs(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X þsij = 1/(1+ ρij) þ þsij = c - ρij, c ³ max ρij, "i,j þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY PODOBNOSTI VS. NEPODOBNOSTI þVzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. þsij = 1/ρij þs(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X þsij = 1/(1+ ρij) þ þsij = c - ρij, c ³ max ρij, "i,j þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY PODOBNOSTI VS. NEPODOBNOSTI þVzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. þsij = 1/ρij þs(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X þsij = 1/(1+ ρij) þs(x,y).s(y,z) £ [s(x,y) + s(y,z) - s(x,y).s(y,z)].s(x,z), "x,y,z Î X þsij = c - ρij, c ³ max ρij, "i,j þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY PODOBNOSTI VS. NEPODOBNOSTI þVzdálenostní míry (míry nepodobnosti) mohou být transformovány na podobnostní míry různými transformacemi, např. þsij = 1/ρij þs(x,y).s(y,z) £ [s(x,y) + s(y,z)].s(x,z), "x,y,z Î X þsij = 1/(1+ ρij) þs(x,y).s(y,z) £ [s(x,y) + s(y,z) - s(x,y).s(y,z)].s(x,z), "x,y,z Î X þsij = c - ρij, c ³ max ρij, "i,j þs(x,z) ³ s(x,y) + s(y,z) - c levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TYPY MĚR VZDÁLENOSTI (PODOBNOSTI) þdle typu příznaků (numerické hodnoty, nominální či ordinální hodnoty, binární hodnoty); þdle objektů, jejichž vztah hodnotíme – obrazy (vektory), množiny obrazů (vektorů), rozdělení þdeterministické (nepravděpodobnostní) vs. pravděpodobnostní míry levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MÍRY VZDÁLENOSTI þobecné poznámky: þvýběr konkrétní metriky závisí na použití þ kritéria: èoptimální výsledky (klasifikační chyby, ztráta, …) èvýpočetní nároky ècharakter rozložení dat þobecně nelze doporučit vhodnou metriku pro určité standardní situace levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMETRIKY PRO URČENÍ VZDÁLENOSTI MEZI DVĚMA OBRAZY þS KVANTITATIVNÍMI PŘÍZNAKY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz EUKLIDOVA METRIKA þmetrika zřejmě s nejnázornější geometrickou interpretaci þ þ þ þgeometrickým místem bodů s toutéž Euklidovou vzdáleností od daného bodu je hyperkoule (kruh ve dvourozměrném prostoru); þdává větší důraz na větší rozdíly mezi souřadnicemi (žádoucí nebo nežádoucí? – volba i podle toho, jak chceme zdůrazňovat rozdíly mezi jednotlivými souřadnicemi) þčtverec euklidovské vzdálenosti (lépe se počítá) je stále mírou nepodobnosti, ale není metrikou levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz EUKLIDOVA METRIKA þmetrika zřejmě s nejnázornější geometrickou interpretaci þ þ þ þSokalova metrika levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz HAMMINGOVA METRIKA þ(metrika Manhattan, manhattanská metrika, city-block m., taxi driver m. – taxikářská metrika) Bild:Manhattan distance.svg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz HAMMINGOVA METRIKA þ(metrika Manhattan, manhattanská metrika, city-block m., taxi driver m. – taxikářská metrika) þ þ þ þgeometrickým místem bodů ve dvou rozměrném prostoru je kosočtverec; þnižší výpočetní nároky než E.m. Þ použití v úlohách s vysokou výpočetní pracností þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz MINKOVSKÉHO METRIKA þzobecnění Euklidovy a Hammingovy metriky; þvolba m záleží na míře důrazu – čím větší m, tím větší váha na velké rozdíly mezi příznaky, þ pro m®¥ metrika konverguje k Čebyševově metrice levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ČEBYŠEVOVA METRIKA þpoužívá se ve výpočetně kriticky náročných případech, kdy je pracnost výpočtu dle euklidovsky orientovaných metrik nepřijatelná; þgeometrickým místem bodů s toutéž Čebyševovou vzdáleností od daného bodu je hyperkrychle (čtverec ve dvourozměrném prostoru) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SROVNÁNÍ GEOMETRICKÝCH MÍST levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ČEBYŠEVOVA METRIKA þpokud je třeba použít „euklidovskou“ metriku, ale s nižší výpočetní pracností, používá se v první řadě Hammingova nebo Čebyševova metrika; þlepším přiblížením je kombinace obou metrik þ þ (ve dvourozměrném prostoru tvoří geometrické místo bodů o téže vzdálenosti osmiúhelník) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz NEVÝHODY METRIK þje nesmyslné vytvářet součet rozdílů veličin s různým fyzikálním rozměrem; þpři začlenění korelovaných veličin se zvyšuje jejich vliv na výslednou hodnotu; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz NEVÝHODY METRIK þje nesmyslné vytvářet součet rozdílů veličin s různým fyzikálním rozměrem; þpři začlenění korelovaných veličin se zvyšuje jejich vliv na výslednou hodnotu; þJak si poradit ? þtransformace proměnných – vztažením k nějakému vyrovnávacímu faktoru – střední hodnotě, směrodatné odchylce, normě þ , rozpětí Di = maxj xij - minj xij, þ resp. standardizací þ , i = 1, …, n; j = 1, …, K. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz NEVÝHODY METRIK þje nesmyslné vytvářet součet rozdílů veličin s různým fyzikálním rozměrem; þpři začlenění korelovaných veličin se zvyšuje jejich vliv na výslednou hodnotu; þJak si poradit ? þváhováním; např. Minkovského váhovaná metrika þ þ transformace pomocí váhových koeficientů je maticově þu = CT.x, þ kde koeficienty transformační matice C jsou dány þcii = ai, pro i = 1, …, n; þcij = 0, pro i ¹ j. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz NEVÝHODY METRIK þje nesmyslné vytvářet součet rozdílů veličin s různým fyzikálním rozměrem; þpři začlenění korelovaných veličin se zvyšuje jejich vliv na výslednou hodnotu; þJak si poradit ? þS takovým vyjádřením transformace příznakových proměnných je váhovaná Euklidova metrika definována vztahem þ þPokud jsou složky transformovaného obrazu dány lineární kombinací více složek původního obrazu, není ani matice C, ani matice C.CT čistě diagonální. þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KVADRATICKÁ VZDÁLENOST þvhodný výběr matice Q je inverzní matice kovariance uvnitř množiny obrazů; þpak se to jmenuje Mahalanobisova metrika levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz CANBERRSKÁ METRIKA þrelativizovaná varianta Hammingovy metriky þ þ þje vhodná pro proměnné s nezápornými hodnotami èpokud jsou obě hodnoty x1i a x2i nulové, potom předpokládáme, že hodnota zlomku je nulová; èje-li jenom jedna hodnota nulová, pak je zlomek roven jedné, nezávisle na velikosti druhé hodnoty; èněkdy se nulové hodnoty nahrazují malým kladným číslem (menším, než nejmenší naměřené hodnoty); levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz CANBERRSKÁ METRIKA þrelativizovaná varianta Hammingovy metriky þ þ þcanberrská metrika je velice citlivá na malé změny souřadnic, pokud se oba obrazy nacházejí v blízkosti počátku souřadnicové soustavy. Naopak je méně citlivá na změny hodnot příznaků, pokud jsou tyto hodnoty velké. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þJsou dány dva vektory x1 = (0,001; 0,001)T a x2 = (0,01; 0,01)T. Předpokládejme, že souřadnice prvního z vektorů se změní na x´1 (0,002; 0,001)T. Jaká je Hammingova a canberrská vzdálenost v obou případech a jaká je relativní změna vzdáleností, vyvolaná uvedenou modifikací? þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD - ŘEŠENÍ þ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; þ þ þ þ þRelativní změny vzdáleností, určující citlivost té které metriky, které jsou způsobeny změnou hodnoty první souřadnice, jsou þ þ þ þ þ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í o poznání větší. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þNyní mějme dány vektory x1 = (1000; 1000)T a x2 = (100; 100)T a předpokládejme, že dojde ke změně první souřadnice vektoru x1 na x´1 = (1002; 1000)T. Jaká je Hammingova a canberrská vzdálenost pro tyto vektory a jaká je relativní změna vzdáleností, vyvolaná uvedenou modifikací? levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD - ŘEŠENÍ þdH(x1,x2) = |1000-100| + |1000-100| = 900 + 900 = 1800; þdH(x´1,x2) = |1002-100| + |1000-100| = 902 + 900 = 1802; þ þ þ þ þRelativní změny vzdáleností způsobených změnou hodnoty první souřadnice pak v tomto případě jsou þ þ þ þ þJak je zřejmé, citlivost canberrské metriky je v tomto případě řádově menší. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz NELINEÁRNÍ VZDÁLENOST þkde D je prahová hodnota a H je nějaká konstanta. þUvádí se, že dobrý výběr hodnot H a D by měl splňovat vztah þ þ þkdyž D splňuje nestrannost a konzistenční podmínku Parzenova odhadu, především DnN®¥ a D®0, když N®¥ (N je počet obrazů v množině) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMETRIKY PRO URČENÍ PODOBNOSTI MEZI DVĚMA OBRAZY þS KVANTITATIVNÍMI PŘÍZNAKY levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SKALÁRNÍ SOUČIN þVe většině případů je skalární součin jako míra podobnosti použit pro vektory x1 a x2 o stejné délce, např. a. V těch případech jsou horní, resp. dolní mez skalárního součinu a2, resp. –a2 a hodnoty skalárního součinu v tom případě závisí výhradně na úhlu, který oba vektory svírají. Hodnoty a2 nabývá, pokud oba vektory svírají nulový úhel, hodnoty –a2, pokud úhel mezi nimi je 180° a nulové hodnoty, pokud jsou oba vektory na sebe kolmé. skalární součin je tedy invariantní vůči rotaci (jejich absolutní orientace není podstatná, důležitý je pouze úhel mezi nimi), nikoliv však vůči lineární transformaci (závisí na délce vektorů). þZe skalárního součinu vektorů o délce a je možné odvodit i metriku vzdálenosti podle vztahu þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz METRIKA KOSINOVÉ PODOBNOSTI þ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 scos(x1, x2) jsou rovny kosinu úhlu mezi oběma vektory. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PEARSONŮV KORELAČNÍ KOEFICIENT þkde xdi = (xi1 - , xi2 - , …, xin - )T, xij představují j-tou souřadnici vektoru xi a je střední hodnota určená ze souřadnic vektoru xi ( ). Vektory xdi se nazývají diferenční vektory. Podobně jako v případě kosinové podobnosti, nabývá Pearsonův korelační koeficient hodnot z intervalu á-1;1ñ, rozdíl vůči kosinové míře podobnosti je ten, že určuje vztah nikoliv vektorů x1 a x2, nýbrž jejich diferenčních variant. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PEARSONŮV KORELAČNÍ KOEFICIENT þjejí hodnoty se, díky dělení dvěma, vyskytují v intervalu á0;1ñ. þTato metrika se používá např. při analýze dat genové exprese. þ I z hodnot Pearsonova korelačního koeficientu lze určit vzdálenost obou vektorů pomocí metriky levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TANIMOTOVA METRIKA PODOBNOSTI þ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 þ Tanimotova podobnost vektorů x1 a x2 je nepřímo úměrná kvadrátu Euklidovy vzdálenosti vektorů x1 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 σT(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á. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz „BEZEJMENNÁ“ METRIKA PODOBNOSTI þVzdálenost podle metriky je rovna jedné, þkdyž x1 = x2 þa svého minima (tj. = -1) nabývá, þkdyž x1 = -x2. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þoboru Matematická biologie þje podporována projektem ESF þč. CZ.1.07/2.2.00/28.0043 þ„INTERDISCIPLINÁRNÍ ROZVOJ STUDIJNÍHO OBORU MATEMATICKÁ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU