ANALÝZA A KLASIFIKACE 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].[] 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í. 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í 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)