Analýza a klasifikace dat přednáška 5 MU RNDr. Eva Janousova IBA » Podzim 2014 Typy klasifikátorů - podle principu klasifikace klasifikace pomocí diskriminačních funkcí: - diskriminační funkce určují míru příslušnosti k dané klasifikační třídě - pro danou třídu má daná diskriminační funkce nejvyšší hodnotu klasifikace pomocí vzdálenosti od etalonů klasif. tříd: - etalon = reprezentativní objekt(y) klasifikační třídy - počet etalonů klasif. třídy různý - od jednoho vzorku (např. centroidu) po úplný výčet všech objektů dané třídy (např. u klasif. pomocí metody průměrné vazby) 0 0 o 0+. tr-*o o o \A A A A A a A klasifikace pomocí hranic v obrazovém prostoru: - stanovení hranic (hraničních ploch) oddělujících klasifikační třídy o ° o O 0+ o • <>,' ✓'A o 0/ ✓'A A+A A A A A Janoušová: Analýza a klasifikace dat IBA Motivace 2-rozmerný prostor x2* O ° O 0 °+0 O / o o SA /A A^.A A /A A A A A 3-rozmerný prostor o O/ o o o o Hranice je nadplocha o rozměru o jedna menší než je rozměr prostoru • ve 2-rozměrném prostoru je hranicí křivka (v lineárním případě přímka) • v 3-rozměrném prostoru plocha (v lineárním případě rovina) Hranice je tedy dána rovnicí: h(x) = w7x + w0 = 0 Výpočet hranice různými metodami (např. Fisherova LDA, SVM apod.-viz dále) Janoušová: Analýza a klasifikace dat IBA IMJ 3 Souvislost klasifikace pomocí diskriminačních funkcí s klasifikací pomocí hranic i Hranice mezi dvěma sousedními podmnožinami ^ a 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, tzn.: h(x) = g^x) -g2(x) = 0 např. u Bayesova klasifikátoru: h(x) = P(cúd\x) — P(cúh\x) = 0 hraniční bod Janoušová: Analýza a klasifikace dat IBA Ml Souvislost klasifikace podle minimální vzdálenosti s klasifikací pomocí hranic i • zařazení objektu x do té třídy, jejíž etalon má od bodu x minimální vzdálenost -tzn. d(x) = XrE"X = mm X^"X v případě dvou tříd reprezentovaných etalony x1E= (x11E, x12E) a x2E= (x21E, x22E) ve dvoupříznakovém euklidovském prostoru je vzdálenost mezi obrazem x= (x^) a libovolným z obou etalonů definována: X ~Xl) +(X,2£-X2)' hledáme menší z obou vzdáleností, tj. mins=12v(xsE,x), tzn. mins=12v2(xsE,x) min v(xsE, x) « min v2 (xsE, x) = min((xslE - x, f + (xs2E -x2)2) = Vs Vs Vs sLEXl+ Xs2£X2 (Xsl£ +xL)/2]) Janoušová: Analýza a klasifikace dat /ba Ml Souvislost klasifikace podle minimální vzdálenosti s klasifikací pomocí hranic ÉfŠM) FfcjSsgéfc, CUÍELOVÝClt ploch • 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 ^HE ~ ^IlE ~ ^22E )/^ = ^ • tato hraniční přímka mezi klasifikačními třídami je vždy kolmá na spojnici obou etalonů a tuto spojnici půlí • souvislost s klasifikací podle diskriminačních funkcí Iba Souvislost jednotlivých principů klasifikace - shrnutí i • Hranice mezi klasifikačními třídami jsou dány průmětem diskriminačních funkcí do obrazového prostoru. • Klasifikace podle minimální vzdálenosti definuje hranici, která je kolmá na spojnici etalonů klasifikačních tříd a půlí ji. • Princip klasifikace dle minimální vzdálenosti vede buď přímo, nebo prostřednictvím využití metrik podobnosti k definici diskriminačních funkcí a ty dle prvního ze zde uvedených pravidel k určení hranic mezi klasifikačními třídami. Janoušová: Analýza a klasifika ;J^J Lineární separabilita lineárně separabilní úloha lineárně neseparabilní úloha lineárně separované klasifikační třídy nelineárně separabilní úloha Janoušová: Analýza a klasifikace dat IBA IMJ 8 Lineárně neseparabilní třídy - způsoby řešení 1. zachováme původní obrazový prostor a zvolíme nelineární hranici: a) definovanou obecně • o o o o b) složenou po částech z lineárních úseků • o o o o / oy'm o o o o/ o/ zobrazíme původní p-rozměrný obrazový prostor nelineární transformací do nového m-rozměrného prostoru tak, aby v novém prostoru byly klasifikační třídy lineárně separabilní o o o o o o o o/ o o o o Janoušová: Analýza a klasifikace dat IBA IMJ Lineárně neseparabilnítřídy-souvislost klasifikace dle minimální vzdálenosti s klasifikací pomocí hranic t HRAUIC6 FD&tE" VÄDÄLEMO&TI Hesel emt-OWY X1B KRAVUCE PODLE MlUIMALUl VXDÄLEUOSTl ME*U ETALON x1e * *ae -7 xC2) Klasifikace podle minimální vzdálenosti střídami reprezentovanými více etalony je „ekvivalentní" klasifikaci s po částech lineární hraniční plochou Janoušová: Analýza a klasifikace dat IBA IMJ 10 Klasifikace s více třídami 1. klasifikace „jedna versus zbytek'' R-l hranice oddělí jednu klasifikační třídu od všech dalších 2. klasifikace „jedna versus jedna" R(R-l)/2 binárních hranic mezi každými dvěma třídami • problematickým úsekům se můžeme vyhnout použitím diskriminačních funkcí (do r-té třídy u>r zařadíme obraz x za předpokladu, že gr(x) > gs(x) pro Vr^s) -> klasifikační hranice je průmět průsečíku gr(x) = gs(x) do obrazového prostoru - takto definovaný klasifikační prostor je vždy spojitý a konvexní Janoušová: Analýza a klasifikace dat *|L ^jjyjjj ^1 Metody stanovení klasifikačních hranic >- • Fisherova lineární diskriminace (FLDA) • Algoritmus podpůrných vektorů • Metoda nejmenších čtverců • Perceptron mu ,..>.,, Janoušová: Analýza a klasifikace dat *™ 12 Metody stanovení klasifikačních hranic i- • Fisherova lineární diskriminace (FLDA) Alonritmi iq nnrl ° • Pprce Janoušová: Analýza a klasifikace dat *jL [^|.. ^3 Fisherova lineární diskriminace jiný název: Fisherova lineární diskriminační analýza (FLDA) použití pro lineární klasifikaci princip: transformace do jednorozměrného prostoru tak, aby se třídy od sebe maximálně oddělily O pacienti A kontroly + centroid pacientů + centroid kontrol ✓ xi O O Qfr OQfr /W^+ A—A- projekce 1 předpoklad: vícerozměrné normální rozdělení u jednotlivých skupin mu ,-.*■»»., Janoušová: Analýza a klasifikac Fisherova lineární diskriminace - princip O pacienti A kontroly + centroid pacientů + centroid kontrol ✓ xi o o S#w má tedy směr (xD — xH) a jeho modul a nás nezajímá, proto: Sww ~ (xD - xH) z čehož vypočteme váhový vektor w jako: w ~ S^1 (xD - xH) hranice je pak dána: wrx — ý = 0, kde ý je průmět hraničního bodu v 1-D prostoru a lze ho vypočítat jako: ý = Yd+Jh pokud chceme zařadit nový subjekt x0 do jedné z daných tříd, jeho průmět do 1-D prostoru (y0 = wTx0) srovnáme s průmětem hraničního bodu ý: > Pokud y0 < ý (přičemž yH < y), subjekt zařadíme do skupiny kontrolních subjektů > Pokud y0 > ý (přičemž yH < y), subjekt zařadíme do skupiny pacientů mu ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjjj 20 Příklad Příklad: Bylo provedeno měření objemu hipokampu a mozkových komor (v "2 12" "5 7" cm3) u 3 pacientů se schizofrenií a 3 kontrol: XD = 4 10 > x# — 3 9 .3 8. .4 5. Určete, zda testovací subjekt x0 = [3,5 9] patří do skupiny pacientů či kontrolních subjektů pomocí Fisherovy lineární diskriminace. o > O M O o; O 13 12 11 10 9 8 7 6 5 4 2 3 4 5 Objem hipokampu • pacienti • kontroly • testovací subjekt Janoušová: Analýza a klasifikace dat IBA IMJ 21 Příprava nových učebních materiálů pro obor Matematická biologie je podporována projektem OPVK č. CZ. 1.07/2.2.00/28.0043 „Interdisciplinární rozvoj studijního oboru Matematická biologie" — -;- lvi 11 n i o i Lno i v w o r\ w i_ o i v i , ur v^ueidvdiii ÍOndvCR EVROPSKÁ UNIE MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost evropský sociální MINISTERSTVO ŠKOLSTVÍ, OP Vzdělávání INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ Janoušová: Analýza a klasifikace dat