Analýza a klasifikace dat přednáška 6 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 3-rozmerný prostor x2* O ° O 0 °+0 O / o o SA y A A^.A A /A A A A A 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) MU ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjj\ 3 Fisherova lineární diskriminace (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 (maximalizace vzdálenosti skupin a minimalizace variability uvnitř skupin o o+ /Ä Ah A A /A A A A O pacienti A kontroly + centroid pacientů + centroid kontrol O O Qfr OQfr A—A- projekce 1 předpoklad: vícerozměrné normální rozdělení u jednotlivých skupin Janoušová: Analýza a klasifikace dat IBA Ml Metoda podpůrných vektorů (SVM) Princip: Proložení klasifikační hranice (nadroviny) tak, aby byla v co největší vzdálenosti od subjektů z obou tříd. direction 2 Varianty SVM (support vectore machine) metody: • Lineární SVM - oproti LDA nevyžaduje normalitu dat. • Nelineární SVM - využití jader (např. polynomiální nebo radiální bázová funkce) k transformaci do prostoru, kde je možné subjekty oddělit lineárně. Janoušová: Analýza a klasifikace d; Nelineární SVM • 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í MU ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjjj g Nelineární SVM - ukázka 2 1.5 i 0.5 >P 0 -0.5 -1 -1.5 o o $ ° $o £ o o g o o O ^ 0 o O o__° (->° o o C •. • lo I w o (9 • • • \ o o o o cP 0 -1.5 -1 -0.5 0 0.5 1 1.5 dvourozměrný prostor s oddělovací hranicí ve tvaru + x22 < 1 tatáž situace zobrazená do trojrozměrného prostoru (xi2/ x22/ V2x1x2) - kruhová hranice se stane lineární Janoušová: Analýza a klasifikace dat /BA IMJ 7 Nelineární SVM - ukázka 3 lineární oddělení obou tri d zde není možné X. umělé zvySení počtu dimenzí (zde o x.) I pozice elementů jedné třídy jsou změněny podél nové dimenze lineární oddělení obou tříd pomocí ■roviny Janoušová: Analýza a klasifikace dat IBA Ml 8 Lineární SVM • Proložení klasifikační hranice (nadroviny) tak, aby byla v co největší vzdálenosti od subjektů z obou tříd -> tzn. aby byl okolo hranice co nejširší pruh bez bodů • Na popis hranice (nadroviny) stačí pouze nejbližší body, kterých je obvykle málo a nazývají se podpůrné vektory (support vectors) MU ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjjj g Lineární SVM - lineárně separabilní třídy hranice: h(x) = w7x + w0 = O (kde w a w0 je orientace a poloha hranice) klasifikace subjektu x do třídy cúd, resp. cúh) bude dána tím, jestli je výraz wTx + w0 větší, resp. menší, než 0 vzdálenost jakéhokoliv bodu od klasifikační „ ^ n x2' hranice je: d = |wTx+w0| l|w|| kde ||w|| je velikost vektoru w pro nejbližší bod xt ze třídy ú)D zvolíme hodnotu výrazu wTXi + w0 rovnu +1 a pro nejbližší bod Xy ze třídy ú)H zvolíme hodnota výrazu wTXj + w0 rovnu — 1 pak na každé straně od dělící přímky mame toleranční pásmo o sirce —r, ve l|w|| kterém se nenachází žádný bod Janoušová: Analýza a klasifikace dat IBA IMJ io Lineární SVM - lineárně separabilní třídy Pro všechny body z trénovací množiny platí: wTx + w0 > 1 pro všechna x z cúd, wTx + w0<—1 pro všechna x z a)H, což můžeme stručněji zapsat jako_ ôXk(wTxk + w0) > 1, pro k=l,N, kde 8XR = 1 pro xk ze třídy cúd a 8XR = -1 pro xfc ze třídy cúh hledáme takové hodnoty w a w0, aby byla celková šířka tolerančního pásma co největší l|w|| ||w|| ||w|| hledat maximum funkce -r-r je to stejné, jako hledat minimum funkce a l|w||J J ,J 2 toto minimum se nezmění, když kladnou hodnotu v čitateli umocníme na druhou (což nám zjednoduší výpočty), takže dostáváme následující kriteriální funkci, jejíž hodnotu se snažíme minimalizovat: J(w,w0) = l|w|| -> řešení pomocí metody Lagrangeova součinitele Janoušová: Analýza a klasifikace dat IBA IMJ li Lineární SVM - lineárně neseparabilní třídy zavedeme relaxační proměnné 0 vyjadřující, jak moc každý bod porušuje podmínku 5xfe(wTxfc + w0) > 1 3 situace: 1. obraz leží vně pásma a je správně klasifikován: %k = 0 2. obraz leží uvnitř pásma a je správně klasifikován (body s čtverečky): 0 < š;k < 1 3. obraz leží na opačné straně hranice a je chybně klasifikován (body s kolečky): ffc = 0 podmínky jsou pak ve tvaru 5xk(wTxfc +w0) > 1 - ffe Janoušová: Analýza a klasifikace d, Lineární SVM - lineárně neseparabilní třídy • když chceme najít hranici poskytující co nejrobustnější klasifikaci, musíme se snažit: — maximalizovat šířku tolerančního pásma — minimalizovat počet subjektů z trénovací množiny, které leží v tolerančním pásmu nebojsou dokonce špatně klasifikovány (tj. těch, pro které 0) • to můžeme vyjádřit jako minimalizaci kriteriální funkce: N k=l kde C vyjadřuje poměr vlivu obou členů kriteriální funkce řešíme opět pomocí metody Lagrangeova součinitele Janoušová: Analýza a klasifikace dat IBA (g) 13 Lineární SVM - metoda Lagrangeova součinitele i- • Zavedeme vektor Lagrangeových součinitelů X= [XlfX2,XN], kde Afc > 0, a pomocí nich vyjádříme optimalizovanou funkci jako: L(w,w0,š,A, \i) II 112 N N N w x™1 x™1 x™1 = + C 2j ^ " Zj [^(wTxfc + W0) - 1 + f/c] - 2j ták k=l k=l k=l • za podmínek \k[ôXk(wTxk + w0) - 1 + 0, pro k = 1, ...,N. • tuto Lagrangeovu funkci zderivujeme podle proměnných w, w0 a ^ a derivace položíme rovny nule -> po dalších úpravách dostaneme: -> patrné, že pro výpočet orientace hranice důležité jen ty body, pro které platí Xk > 0 (takovým bodům říkáme podpůrné vektory a jen na nich závisí umístění a orientace dělící přímky) MU -t Příklad I- Příklad: Bylo provedeno měření objemu hipokampu a mozkových komor (v cm3) u 3 pacientů se schizofrenií a 3 kontrol: XD = "2 12" "5 7" 4 10 > — 3 9 .3 8. .4 5. Určete, zda testovací subjekt x0 = [3,5 9] patří do skupiny pacientů či kontrolních subjektů pomocí metody podpůrných vektorů. o > O M O cu 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 15 Příklad - řešení pro parametr C = 1 * výsledkem jsou hodnoty X = [o,^, 1,^, 1, oj > podpůrnými vektory jsou tedy body x2, x3, x4 a x5, protože jim příslušející A2, A3, A4 a As jsou nenulové. Vypočítáme orientaci hranice: 6 111 1 w = £ A Afc xfc = -x2 + x3 - -x4 - x5 = - [4J + g] - - [5] - [3] fc = l "-1/2" 1/2 . • Pokud zvolíme takový xk, pro který platí 0 < Ak < C, tak podle vztahu + M/c — £ mus' být > 0 a odtud podle vztahu \ik^k = 0 plyne, že f;k = 0. Vzorec se tak zjednoduší na ôXk(wTxk + w0) = 1. Tedy například prox2 (0 w0 = 1 — 2 2J LlOJ hranice je tedy dána rovnicí: wTx + wo — [— ^ \] x — 2 MU ^'■»«., Janoušová: Analýza a klasifikace dat *|L ^j ^6 Příklad - řešení pro parametr C = 1 * hranice je dána rovnicí: wTx + w0 = ^ x — 2 12r O 11 h 10 h 9h o £ 8 7h O O pacienti kontroly testovací subjekt ■ dělící přímka ■hranice tolerančního pásma pacienti - podpůrný vektor s ^ = 0 kontroly - podpůrný vektor s t, = 0 pacienti - podpůrný vektor s t, > 0 kontroly - podpůrný vektor s Č, > 0 2.5 3.5 objem hipokampu 4.5 Janoušová: Analýza a klasifikace dat IBA IMJ 17 Příklad - řešení pro parametr C = 1 můžeme klasifikovat subjekt x = [3,5 9]: w x + w0 = -\ ±][3^5]-2 = -1,75 + 4,5-2 = 0.75 protože 0,75 > 0, testovací subjekt bude zařazen do třídy pacientů ověříme, že natrénovaný klasifikátor zařadí subjekty z trénovací množiny tak, jak to odpovídá situaci na obrázku; tj. správně subjekty xlf x2,x3,x4 a x6 a chybně subjekt x5: w xx + w0 = w x2 + w0 = wTx3 + w0 = w1 x4 + w0 = w x5 + w0 = w1 x6 + w0 = 1 lip" \ 10 1 lip" 2 2JI5J -2 = -1,5 + 4-2 = 0,5 -2 = -2,5 + 3,5-2 = -1 - 2 = -1,5 + 4,5 - 2 = 1 - 2 = -2 + 2,5 - 2 = -1,5 Janoušová: Analýza a klasifikace dat IBA IMJ 18 Příklad - řešení pro parametr C = 10 i- • výsledkem jsou hodnoty X = [0, 3,6371, 8,7629, 2,0371, 10, 0,3629] • podpůrnými vektory jsou tedy body x2,x3,x4,x5 a x6 , protože jim příslušející A2, A3, A4, As a A6 jsou nenulové. Vypočítáme orientaci hranice: 6 w = ^ XkSXk xk = 3,6371x2 + 8,7629x3 - 2,0371x4 - 10x5 - 0,3629x6 k=i = 3,6371 [^J + 8,7629 Q - 2,0371 g] - 10 [^] - 0,3629 [J] = [_4/5l .2/5 J • Polohu dělící přímky určíme opět ze ôXk(wTxk + w0) = 1. Tedy například prox2 (0 < A2 = 3,6371 < C = 10): t ľ 4 21 r 41 4 1 WTx2+W0 = l =* W0 = l-[-- -j[10] = l-- = - T ľ 4 21 1 • hranice je tedy dána rovnicí: w x + w0 = — - -x + - L 5 5J 5 MU ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjjj ^9 Příklad - řešení pro parametr C = 10 T [ 4 2"| l * hranice je tedy dána rovnicí: wlx + w0 = — - -x + - L 5 5J 5 12r O 11 h 10 h ° 9 o Ji E Jr 8 o 7h 6h 2.5 3 3.5 objem hipokarnpu o o pacienti kontroly testovací subjekt ■dělící přímka ■hranice tolerančního pásma pacienti - podpůrný vektor s £ = 0 kontroly - podpůrný vektor s £ = 0 kontroly - podpůrný vektor s £ > 0 4 4.5 5 Janoušová: Analýza a klasifikace dat IBA IMJ 20 Příklad - řešení pro parametr C = 10 můžeme klasifikovat subjekt x = [3,5 9]: w x + w0 = 4 21 r3 51 1 "5 šJ I 9 ] + 5 = _2'8 + 3'6 + °'2 = 1 protože 1 > 0, testovací subjekt bude zařazen do třídy pacientů ověříme, že natrénovaný klasifikátor zařadí subjekty z trénovací množiny tak, jak to odpovídá situaci na obrázku; tj. správně subjekty xlf x2,x3,x4 a x6 a chybně subjekt x5: wTx1 + w0 = w 4 2lr2i 1 8 24 1 17 ľ 4 21 r 41 1 16 20 1 5 x2+w0 = [-- j[ioj+_ = __ + _ + _ = _=i w x3 + w0 = w1 x4 + w0 = w x5 + w0 = 5 4 2 2| p" 5. ■5" 1 _ 12 16 1 _ 5 _ 8J + 5 = ~T + T + 5 = 5 = 1 1 20 14 1 5 = - —+ — + - = -- =-1 5 5J L7J 5 5 5 5 5 4 21 i-3-i 1 _ 12 18 1 _ 7 _ "5 5JkJ + 5 = "T + T + 5 = 5 = 1'4 4 2lr4i 1 16 10 1 5 Příklad - srovnání výsledků pro C = 1 a C = 10 c = 1: C = 10: 12r 0 10- 2 pacienti kontroly testovací subjekt ■dělící přímka ■hranicetolerančního pásma pacienti - podpůrný vektor s \ - O kontroly - podpůrný vektor s ŕj = O pacienti - podpůrný vektor s \ > O kontroly - podpůrný vektor s \ > O 2.5 3.5 objem hipokampu 4.5 12 10 ° 9 E 3 pacienti kontroly testovací subjekt ■dělící přímka ■hranice tolerančního pásma pacienti - podpůrný vektor s % = O kontroly - podpůrný vektor s \ = 0 kontroly - podpůrný vektor s \ > 0 3.5 objem hipokampu Janoušová: Analýza a klasifikace dat IBA IMJ 22 Další metody klasifikace MU -t !Sr W 23 Typy klasifikátorů 1. Podle reprezentace vstupních dat: - příznakové klasifikátory: paralelní x sekvenční - strukturální (syntaktické) klasifikátory - kombinované klasifikátory 2. Podle jednoznačnosti zařazení do skupin: - deterministické klasifikátory - pravděpodobnostní klasifikátory 3. Podle typů klasifikačních a učících algoritmů: - parametrické klasifikátory - neparametrické klasifikátory 4. Podle způsobu učení: - učení s učitelem: dokonalým x nedokonalým - učení bez učitele 5. Podle podle principu klasifikace: - klasifikace pomocí diskriminačních funkcí - klasifikace pomocí vzdálenosti od etalonů klasifikačních tříd - klasifikace pomocí hranic v obrazovém prostoru Janoušová: Analýza a klasifikace dat *|L 24 Typy klasifikátorů - podle reprezentace vstupních dat • příznakové - vstupní data vyjádřena vektorem hodnot jednotlivých proměnných (příznaků): - paralelní - zpracování vektoru jako celku (např. Bayesův klasifikátor) - sekvenční - zpracování (občas i měření) proměnných postupně (např. klasifikační stromy) B C D E 1 id vek pohlaví výska vaha 11 38 Z 164 45 36 M 167 90 ij 26 Z ITS 70 • strukturální (syntaktické) - vstupní data popsána relačními strukturami • kombinované-jednotlivá primitiva doplněna příznakovým popisem Janoušová: Analýza a klasifikace dat Sekvenční klasifikace - motivace • až dosud (bayesovské klasifikátory, klasifikátory s diskriminační hranicí, s minimální vzdáleností,...) - pevný konstantní počet příznaků • kolik a jaké proměnných? - málo proměnných - možná chyba klasifikace; - moc proměnných - možná nepřiměřená pracnost, vysoké náklady; - použít proměnné, které nesou co nejvíce informace o klasifikační úloze; • sekvenční klasifikace - kompromis mezi velikostí klasifikační chyby a cenou určení příznaků - klasifikace na základě klasifikačního stromu - klasifikace s rostoucím počtem proměnných, přičemž okamžik ukončení klasifikační procedury stanoví klasifikátor sám podle předem daného kritéria pro kvalitu rozhodnutí (tj. na základě vlastností klasifikačních tříd, resp. objektů v nich) Janoušová: Analýza a klasifikace dat *|L ^jjyjjj 26 Klasifikační (rozhodovací) stromy a lesy Princip: Postupné rozdělování data set u do skupin podle hodnot jednotlivých proměnných. r Zmenšený hipokampus r Zvětšené komory V. Zmenšená amygdala Pacient Kontrola Pacient Kontrola Klasifikační lesy - použití více klasifikačních stromů ke klasifikaci. Janoušová: Analýza a klasifikace dat IBA IMJ 27 Klasifikace s rostoucím počtem proměnných Waldovo kritérium: - p(x1; x2, Xj | (jo1) a p(x1; x2, Xj|ca)2) jsou i-rozměrné hustoty pravděpodobnosti (tzn. dané prvními i proměnnými) výskytu objektu x = (x^ x2,x^ v i-tém klasifikačním kroku v třídách a u)2 - A a B jsou konstanty (0 A, pak se objekt x zařadí do třídy b)1 a proces se ukončí 3. je Aj g (B,A), přidáme další proměnnou (příznak) xi+1 a proces se opakuje Modifikované Waldovo kritérium - 2 možnosti: - po určitém počtu kroků se sekvenční výpočet přeruší a dokončí se na základě nějakého rozhodnutí vycházejícího z nějakého kritéria založeného na pevném počtu příznaků — zavedení proměnných hranic A(i) a B(i) ReedOVO kritérium Janoušová: Analýza a klasifikace dat *|L 28 Srovnání původního a modifikovaného Waldova kritéria 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" — -;- i vi 11 \j i o i Lnu 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