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 III. 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 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 è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 MINIMÁLNÍ VZDÁLENOSTI þ þ þreprezentativní obrazy klasifikačních tříd - etalony þje-li v obrazovém prostoru zadáno R poloh etalonů vektory x1E, x2E,…, xRE, 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 þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE MINIMÁLNÍ VZDÁLENOSTI þ þ þuvažme případ dvou tříd reprezentovaných etalony x1E = (x11E, x12E) a x2E = (x21E, x22E) ve dvoupříznakovém euklidovském prostoru; þvzdálenost mezi obrazem x = (x1,x2) a libovolným z obou etalonů je pak definována þ þ þhledáme menší z obou vzdáleností, tj. mins=1,2v(xsE,x), ale také mins=1,2v2(xsE,x); levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE PODLE MINIMÁLNÍ VZDÁLENOSTI þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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 þx1(x11E - x21E ) + x2(x12E - x22E ) - (x212E + x211E - x221E - x222E )/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. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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 2_13