ANALÝZA A KLASIFIKACE BIOMEDICÍNSKÝCH DAT prof. Ing. Jiří Holčík, CSc. III. PŘÍZNAKOVÁ KLASIFIKACE - ÚVOD Příznakový popis Příznakový obraz x zpracovávaných dat je vyjádřen n-rozměrným (sloupcovým) vektorem hodnot x[i], i=1,2,…,n příznakových proměnných (veličin) charakterizujících vlastnosti těchto dat, tj. platí x=(x[1],x[2],…,x[n])^T. 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é Příznakový popis 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 Při vhodném výběru příznakových veličin je podobnost signálů 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 Příznakový klasifikátor 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 Příznakový klasifikátor þ 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 þ 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 þ Obrazový prostor je rozhodovacím pravidlem rozdělen na R disjunktních prostorů R[r], r=1,…,R, přičemž každá podmnožina R[r] 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. Klasifikace podle diskriminačních funkcí 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í þ hranice klasifikačních tříd definujeme pomocí R skalárních funkcí g[1](x), g[2](x),…, g[R](x) takových , že pro obraz x z podmnožiny R[r] pro všechna r platí g[r](x) > g[s](x), pro s =1,2,…,R a r ≠ s þ funkce g[r](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 Klasifikace podle diskriminačních funkcí þ hranice mezi dvěma sousedními podmnožinami R[r] a R[s] je určena průmětem průsečíku funkcí g[r](x) a g[s](x), definovaného rovnicí g[r](x) = g[s](x), do obrazového prostoru. Blokové schéma klasifikátoru pomocí diskriminačních funkcí Blokové schéma klasifikátoru pomocí diskriminačních funkcí þ u dichotomického klasifikátoru (dvě třídy) je ω = sign (g[1](x) – g[2](x)) Klasifikace podle diskriminačních funkcí þ nejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar g[r](x) = a[r0] + a[r1]x[1 ]+ a[r2]x[2 ]+…+ a[rn]x[n] [ ]kde a[r0] je práh diskriminační funkce posouvající počátek souřadného systému a a[ri] jsou váhové koeficienty i-tého příznaku x[i] þ lineárně separabilní[ ]třídy Klasifikace podle diskriminačních funkcí þ zobrazíme původní n-rozměrný obrazový prostor X^n nelineární transformací Φ: X^n → X^m do nového m-rozměrného prostoru X^m, 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) Klasifikace podle minimální vzdálenosti þ reprezentativní obrazy klasifikačních tříd - etalony þ je-li v obrazovém prostoru zadáno R poloh etalonů vektory x[1E], x[2E],…, x[RE], zařadí klasifikátor podle minimální vzdálenosti klasifikovaný obraz x do té třídy, jejíž etalon má od bodu x minimální vzdálenost. Rozhodovací pravidlo je určeno vztahem Klasifikace podle minimální vzdálenosti þ uvažme případ dvou tříd reprezentovaných etalony x[1E ]= (x[11E], x[12E]) a x[2E ]= (x[21E], x[22E]) ve dvoupříznakovém euklidovském prostoru; þ vzdálenost mezi obrazem x[ ]= (x[1],x[2]) a libovolným z obou etalonů je pak definována þ hledáme menší z obou vzdáleností, tj. min[s=1,2]v(x[sE],x), ale také min[s=1,2]v^2(x[sE],x); Klasifikace podle minimální vzdálenosti Klasifikace podle minimální vzdálenosti þ diskriminační kuželové plochy se protínají v parabole a její průmět do obrazové roviny je přímka definovaná vztahem x[1](x[11E ]- x[21E ]) + x[2](x[12E ]- x[22E ]) - (x^2[12E ]+ x^2[11E] - x^2[21E ]- x^2[22E ])/2 = 0 Tato hraniční přímka mezi klasifikačními třídami je vždy kolmá na spojnici obou etalonů a tuto spojnici půlí ß klasifikátor pracující na základě kritéria minimální vzdálenosti je ekvivalentní lineárnímu klasifikátoru s diskriminačními funkcemi. Klasifikace podle minimální vzdálenosti þ Klasifikace podle minimální vzdálenosti s třídami reprezentovanými více etalony je ekvivalentní klasifikaci podle diskriminační funkce s po částech lineární hraniční plochou Určení diskriminačních funkcí ze statistických vlastností množiny obrazů Základní pojmy a předpoklady þ 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. [þ ]ztrátová funkce l([r]|w[s]) udává ztrátu při chybné klasifikaci obrazu ze třídy [s][ ]do třídy[ ]w[r.] þ matice ztrátových funkcí þ střední ztráta J(a) udává průměrnou ztrátu při chybné klasifikaci obrazu x Kritérium minimální střední ztráty þ pokud se soustředíme na obrazy pouze ze třídy w[s], je střední ztráta dána průměrnou hodnotou z (d(x,a)|w[s]) vzhledem ke všem obrazům ze třídy [s],[ ]tj. kde p(x|w[s]) je podmíněná hustota pravděpodobnosti výskytu obrazu x ve třídě [s] Kritérium minimální střední ztráty þ Celková střední ztráta J(a) je průměrná hodnota ze ztrát J[s](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([s]|x) je podmíněná pravděpodobnost, že daný obraz patří do třídy [s] (tzv. aposteriorní pravděpodobnost třídy [s]. 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 ([r]|w[s]) konstantní pro všechny obrazy z [s],[ ]je dále Kritérium minimální střední ztráty [þ ]Označíme-li ztrátu při klasifikaci obrazu x do třídy [r] [ ] [ ] tak po dosazení dostaneme Úloha nalezení minima celkové střední ztráty se tak převedla na minimalizaci funkce L[x]([r]). Optimální rozhodovací pravidlo d(x,a*) podle kritéria minimální celkové střední ztráty je 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 Kritérium minimální střední ztráty Dichotomický klasifikátor Celková střední ztráta v případě dvou tříd je 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 [1], 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 [2].[] Kritérium minimální pravděpodobnosti chybného rozhodnutí Díky obtížnému stanovení hodnot ztrátových funkcí ([r]|w[s]) 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í. Kritérium minimální pravděpodobnosti chybného rozhodnutí 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í V případě dichotomického klasifikátoru je diskriminační funkce A věrohodnostní poměr je potom 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 L[x](ω[r]) lze použít a s jednotkovými ztrátovými funkcemi je KRITÉRIUM MAXIMÁLNÍ APOSTERIORNÍ PRAVDĚPODOBNOSTI þ 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. g[r](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Í 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 KRITÉRIUM MAXIMÁLNÍ PRAVDĚPODOBNOSTI (MINIMAX) þ V případě dichotomie je věrohodnostní poměr þ Pokud jsou ceny správného rozhodnutí nulové, tj. l([1]|w[1]) = ([2]|w[2]) = 0, je þ Obraz je zařazen do třídy [1], 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)