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 II. PŘÍZNAKOVÁ KLASIFIKACE - ÚVOD levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍZNAKOVÝ POPIS þPříznakový obraz x zpracovávaných dat je vyjádřen n-rozměrným (sloupcovým) vektorem hodnot xi, i=1,2,…,n příznakových proměnných (veličin) charakterizujících vlastnosti těchto dat, tj. platí þx=(x1,x2,…,xn)T. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍZNAKOVÝ POPIS þPříznakové proměnné mohou popisovat kvantitativní i kvalitativní vlastnosti souboru dat. Jejich hodnoty nazýváme příznaky. þ þPodle definičního oboru rozlišujeme proměnné: èspojité ènespojité, diskrétní, vyjmenovatelné èlogické, binární, alternativní, dichotomické þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þVrchol každého příznakového vektoru (obrazu) představuje bod n-rozměrného prostoru X n, který nazýváme obrazovým prostorem. þObrazový prostor je definován kartézským součinem definičních oborů všech příznakovým proměnných, tzn. že jej tvoří všechny možné obrazy zpracovávaného souboru dat. PŘÍZNAKOVÝ POPIS levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þPři vhodném výběru příznakových veličin je podobnost objektů (je popisujících dat) z jedné klasifikační třídy vyjádřena blízkostí jejich obrazů v obrazovém prostoru. þVymezení klasifikační třídy: èetalony - charakteristické reprezentativní obrazy èhranice èdiskriminační funkce 2_1 PŘÍZNAKOVÝ POPIS levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þ þPříznakový klasifikátor je stroj s tolika vstupy, kolik je příznaků a s jedním diskrétním výstupem, který udává třídu, do které klasifikátor zařadil rozpoznávaný obraz. þωr = d(x) þd(x) je skalární funkce vektorového argumentu x, kterou nazýváme rozhodovací pravidlo klasifikátoru; þωr je identifikátor klasifikační třídy 2_2 PŘÍZNAKOVÝ KLASIFIKÁTOR levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þ þdeterministický a nedeterministický þs pevným a proměnným počtem příznaků þbez učení a s učením PŘÍZNAKOVÝ KLASIFIKÁTOR levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þ þdeterministický a nedeterministický þs pevným a proměnným počtem příznaků þbez učení a s učením þ þ Nadále se nějaký čas věnujme deterministickým klasifikátorům s pevným počtem příznaků. PŘÍZNAKOVÝ KLASIFIKÁTOR levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þObrazový prostor je rozhodovacím pravidlem rozdělen na R disjunktních prostorů Rr, r=1,…,R, přičemž každá podmnožina Rr obsahuje ty obrazy x, pro které je ωr = d(x). þNávrh rozhodovacího pravidla je základním problémem návrhu klasifikátoru. 2_1 PŘÍZNAKOVÝ KLASIFIKÁTOR levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þDISKRIMINAČNÍ ANALÝZA þ þtýká se obecně vztahu mezi kategoriální proměnnou a množinou vzájemně vázaných příznakových proměnných. þKonkrétně, předpokládejme že existuje konečný počet, řekněme R, různých a priori známých populací, kategorií, tříd nebo skupin, které označujeme ωr, r=1,…,R a úkolem diskriminační analýzy je nalézt vztah, na základě kterého pro daný vektor příznaků popisujících konkrétní objekt tomuto vektoru přiřadíme hodnotu ωr. KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 2_3 KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þhranice klasifikačních tříd definujeme pomocí R skalárních funkcí g1(x), g2(x),…, gR(x) takových , že pro obraz x z podmnožiny Rr pro všechna r platí þgr(x) > gs(x), pro s =1,2,…,R a r ≠ s þfunkce gr(x) mohou vyjadřovat např. míru výskytu obrazu x patřícího do r-té klasifikační třídy v daném místě obrazového prostoru – nazýváme je diskriminační funkce levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ þ þhranice mezi dvěma sousedními podmnožinami Rr a Rs je určena průmětem průsečíku funkcí gr(x) a gs(x), definovaného rovnicí gr(x) = gs(x), do obrazového prostoru. 2_3 KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz BLOKOVÉ SCHÉMA KLASIFIKÁTORU POMOCÍ DISKRIMINAČNÍCH FUNKCÍ þ þ 2_5 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz BLOKOVÉ SCHÉMA KLASIFIKÁTORU POMOCÍ DISKRIMINAČNÍCH FUNKCÍ þ þ þu dichotomického klasifikátoru (dvě třídy) je þω = sign (g1(x) – g2(x)) 2_8 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þnejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar þgr(x) = ar0 + ar1x1 + ar2x2 +…+ arnxn þ kde ar0 je práh diskriminační funkce posouvající počátek souřadného systému a ari jsou váhové koeficienty i-tého příznaku xi þlineárně separabilní třídy 2_1 2_7 obr roviny.bmp levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þnejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar þgr(x) = ar0 + ar1x1 + ar2x2 +…+ arnxn þ kde ar0 je práh diskriminační funkce posouvající počátek souřadného systému a ari jsou váhové koeficienty i-tého příznaku xi þlineárně separabilní třídy 2_1 2_7 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þnejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar þgr(x) = ar0 + ar1x1 + ar2x2 +…+ arnxn þ kde ar0 je práh diskriminační funkce posouvající počátek souřadného systému a ari jsou váhové koeficienty i-tého příznaku xi þlineárně separabilní třídy 2_1 2_7 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þnejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar þgr(x) = ar0 + ar1x1 + ar2x2 +…+ arnxn þ kde ar0 je práh diskriminační funkce posouvající počátek souřadného systému a ari jsou váhové koeficienty i-tého příznaku xi þlineárně separabilní třídy 2_1 2_7 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þzobrazíme původní n-rozměrný obrazový prostor Xn nelineární transformací Φ: Xn → Xm do nového m-rozměrného prostoru Xm, obecně je m≠n, tak, aby v novém prostoru byly klasifikační třídy lineárně separabilní a v novém prostoru použijeme lineární klasifikátor (Φ převodník) LINEÁRNĚ NESEPARABILNÍ TŘÍDY þzachováme původní obrazový prostor a zvolíme nelineární diskriminační funkci èdefinovanou obecně èsloženou po částech z lineárních úseků 2_9 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þBAYESŮV KLASIFIKÁTOR þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þBAYESŮV KLASIFIKÁTOR þ þpři řešení praktických úloh je třeba předpokládat, že obrazy signálů jsou ovlivněny víceméně náhodnými fluktuacemi zdroje signálu, v přenosové cestě, při předzpracování i analýze, které se nepodaří zcela eliminovat. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ þ þ þBAYESŮV KLASIFIKÁTOR þ þ þP(ωr|x) je aposteriorní podmíněná pravděpodobnost zatřídění obrazového vektoru x do třídy ωr; þp(x|ωr) je podmíněná hustota pravděpodobnosti obrazů x ve třídě ωr; þP(ωr) je apriorní pravděpodobnost třídy ωr; þp(x) je hustota pravděpodobnosti rozložení všech obrazů x v celém obrazovém prostoru. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZÁKLADNÍ POJMY A PŘEDPOKLADY þztrátová funkce l(wr|ws) udává ztrátu při chybné klasifikaci obrazu ze třídy ws do třídy wr. þmatice ztrátových funkcí þ þ þ þ þstřední ztráta J(a) udává průměrnou ztrátu při chybné klasifikaci obrazu x levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY þpokud se soustředíme na obrazy pouze ze třídy ws, je střední ztráta dána průměrnou hodnotou z l(d(x,a)|ws) vzhledem ke všem obrazům ze třídy ws, tj. þ þ kde p(x|ws) je podmíněná hustota pravděpodobnosti výskytu obrazu x ve třídě ws levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY þCelková střední ztráta J(a) je průměrná hodnota ze ztrát Js(a) þ þ þ þnebo podle Bayesova vzorce ( P(ωs|x).p(x) = p(x|ωs).P(ωs) ) þ þ þ kde p(x) je hustota pravděpodobnosti výskytu obrazu x v celém obrazovém prostoru a P(ws|x) je podmíněná pravděpodobnost, že daný obraz patří do třídy ws (tzv. aposteriorní pravděpodobnost třídy ws. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY þNávrh optimálního klasifikátoru, který by minimalizoval střední ztrátu, spočívá v nalezení takové množiny parametrů rozhodovacího pravidla a*, že platí þ þDosadíme-li za J(a) z předchozího vztahu, je þ þ þJe-li ztrátová funkce l(wr|ws) konstantní pro všechny obrazy z ws, je dále þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY þOznačíme-li ztrátu při klasifikaci obrazu x do třídy wr þ þ þtak po dosazení dostaneme þ þ þÚloha nalezení minima celkové střední ztráty se tak převedla na minimalizaci funkce Lx(wr). Optimální rozhodovací pravidlo d(x,a*) podle kritéria minimální celkové střední ztráty je þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY þChceme-li využít principu diskriminačních funkcí þ þ þDiskriminační funkci optimálního klasifikátoru podle kritéria minimální chyby pak definujeme þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY DICHOTOMICKÝ KLASIFIKÁTOR þCelková střední ztráta v případě dvou tříd je 2_14 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ STŘEDNÍ ZTRÁTY DICHOTOMICKÝ KLASIFIKÁTOR þDiskriminační funkce pro dichotomický klasifikátor bude þ þ þ þ þPoložíme-li tento výraz nule dostaneme vztah pro hraniční plochu dichotomického klasifikátoru, ze kterého můžeme určit poměr hustot pravděpodobnosti výskytu obrazu x v každé z obou klasifikačních tříd - věrohodnostní poměr þ þ þObraz x zařadíme do třídy w1, když je věrohodnostní poměr větší než výraz na pravé straně, je-li menší pak obraz x zařadíme do třídy w2. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz VĚROHODNOSTNÍ POMĚR I. þSumarizuje veškerou informaci získanou experimentem. þPravděpodobnost, že jev (data) nastane za daných podmínek (hypotéza) děleno pravděpodobností, že stejný jev nastane za jiných podmínek. Podmínky jsou vzájemně se vylučující. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz VĚROHODNOSTNÍ POMĚR II. þVěrohodnostní poměr (likelihood ratio) LR udává podíl pravděpodobnosti, že se vyskytne nějaký jev A za určité podmínky (jev B), k pravděpodobnosti, že se jev A vyskytne, když podmínka neplatí (jev nonB). Má-li například pacient náhlou ztrátu paměti (jev A), chceme znát věrohodnostní poměr výskytu jevu A v případě, že má mozkový nádor (jev B), tj. podíl pravděpodobnosti, s jakou ztráta paměti vzniká při nádoru mozku, k pravděpodobnosti, s jakou vzniká v ostatních případech . Věrohodnostní poměr je tedy podíl podmíněných pravděpodobností levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MINIMÁLNÍ PRAVDĚPODOBNOSTI CHYBNÉHO ROZHODNUTÍ þDíky obtížnému stanovení hodnot ztrátových funkcí l(wr|ws) se kritérium minimální chyby zjednodušuje použitím jednotkových ztrátových funkcí definovaných þ þ þMatice jednotkových ztrátových funkcí má pak tvar þ þ þ þ þa celková ztráta je þ þ þcož je hodnota pravděpodobnosti chybného rozhodnutí. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þDosadíme-li hodnoty jednotkových ztrátových funkcí do vztahu pro ztrátu při klasifikaci obrazu do chybné třídy þ þ þa s využitím Bayesova vztahu þ þ þp(x) nezávisí na klasifikační třídě a tedy neovlivňuje výběr minima. þDiskriminační funkci tedy můžeme určit jako KRITÉRIUM MINIMÁLNÍ PRAVDĚPODOBNOSTI CHYBNÉHO ROZHODNUTÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þV případě dichotomického klasifikátoru je diskriminační funkce þ þ þA věrohodnostní poměr je potom KRITÉRIUM MINIMÁLNÍ PRAVDĚPODOBNOSTI CHYBNÉHO ROZHODNUTÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MAXIMÁLNÍ APOSTERIORNÍ PRAVDĚPODOBNOSTI þModifikujeme-li vztah pro ztrátu při chybné klasifikaci obrazu podle Bayesova vztahu ( P(ωs|x).p(x) = p(x|ωs).P(ωs) ) platí þ þ þ þHustota pravděpodobnosti p(x) nezávisí na klasifikační třídě a tedy místo Lx(ωr) lze použít þ þ þ þ a s jednotkovými ztrátovými funkcemi je þ þ þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMinimum ztráty L‘x(ωr) je právě tehdy, když P(ωr|x) je maximální. Tzn. že jako diskriminační funkci můžeme zvolit právě hodnotu aposteriorní pravděpodobnosti třídy ωr, tj. þgr(x) = P(ωr|x) þPro případ dichotomického klasifikátoru je diskriminační funkce þg(x) = P(ω1|x) - P(ω2|x) = 0. þ Z toho plyne, že hranicí mezi třídami určuje vztah þP(ω1|x) = P(ω2|x) þnebo þ þ þPodle tohoto kritéria zatřídíme obraz do té třídy, jejíž aposteriorní pravděpodobnost je při výskytu obrazu x větší. KRITÉRIUM MAXIMÁLNÍ APOSTERIORNÍ PRAVDĚPODOBNOSTI levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KRITÉRIUM MAXIMÁLNÍ PRAVDĚPODOBNOSTI (MINIMAX) þNeznáme-li apriorní pravděpodobnosti všech tříd, předpokládáme rovnoměrné rozložení (pravděpodobnost všech tříd je táž (P(ωs) = = P(ω) =1/R). Potom celková střední ztráta þ þ þ dosáhne minima, když þ þ þ þDiskriminační funkci lze jako v předchozích případech definovat jako levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þV případě dichotomie je věrohodnostní poměr þ þ þ þPokud jsou ceny správného rozhodnutí nulové, tj. l(w1|w1) = l(w2|w2) = 0, je þ þ þ þObraz je zařazen do třídy w1, když je věrohodnostní poměr než poměr cen ztrát chybných zatřídění. Jsou-li obě ceny stejné, je obraz zařazen do té třídy, pro kterou je hodnota p(x|ωs) větší. KRITÉRIUM MAXIMÁLNÍ PRAVDĚPODOBNOSTI (MINIMAX) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 2_15 KRITÉRIUM MAXIMÁLNÍ PRAVDĚPODOBNOSTI (MINIMAX) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þpro obor Matematická biologie þje podporována projektem ESF þč. CZ.1.07/2.2.00/07.0318 þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU