Analýza a klasifikace dat -
přednáška 4
MU
RNDr. Eva Janousova
IBA »
Podzim 2015
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-K
tr-*o
o    o \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
Xn
o 0 o, ,<
0   °*o •<>,/
o o/A
/AAfA A A   A A
x.
Janoušová: Analýza a klasifikace dat
IBA
Motivace
2-rozmerný prostor
3-rozmerný prostor
x2A
O   ° O
0    0+0   O / O 0/A
/A A   A A
A
x.
X,
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) = wTx + 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 (^J
Souvislost klasifikace pomocí diskriminačních funkcí s klasifikací pomocí hranic
Hranice mezi dvěma sousedními třídami ud1 a co2 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) = gx(x) -g2(x) = 0
např. u Bayesova klasifikátoru: h(x) = P(a)D\x) — P(cúh\x) = 0
g(x)
hraniční bod
MU ,......
Janoušová: Analýza a klasifikace dat ^JJ
Souvislost klasifikace podle minimální vzdálenosti s klasifikací pomocí hranic
•   zařazení objektu x do té třídy, jejíž etalon má od bodu x minimální
vzdálenost-tzn. d(x) =
= mm
•   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:
= ^(XSlE~XlÝ +(Xs2E~X2)2
Kx^x) =
*sE X
•   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) = mm((xslE - x, f + (xs2E - x2 f ) =
v s v s v s
miníx2 + x\- 2\xsXExx + xs2Ex2 - (x2slE
MU s"*.}
Janoušová: Analýza a klasifikace dat |yj 5
Souvislost klasifikace podle minimální vzdálenosti s klasifikací pomocí hranic
• 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 + x2iie " 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í
• souvislost s klasifikací podle diskriminačních funkcí jdu qjfc
Souvislost jednotlivých principů klasifikace - shrnutí
• 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.
MU
Janoušová: Analýza a klasifikace dat (^J
Lineární separabilita
a)
b)
c)
o o
0 0
X,
Xn
0   0 •
o   o  o 0 /
o • °/
x.
O   « °
o o,' o o /• 1
O ' •
x,
lineárně separabilní úloha
lineárně neseparabilní
úloha lineárně separované klasifikační třídy
nelineárně separabilní úloha
MU
Janoušová: Analýza a klasifikace dat |yj 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
o y
o
JO
O O/
o/
2.   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
Janoušová: Analýza a klasifikace dat
IBA
Lineárně neseparabilnítřídy-souvislost klasifikace dle minimální vzdálenosti s klasifikací pomocí hranic
x2 i
VaDÄLEMOSTl Xie A tfjjg
KRALICE PODLE MlUIMALUl V%DÁl.EklOSTI He«U ETALON
xle * *ae -7
Klasifikace podle minimální vzdálenosti střídami reprezentovanými více etalony je „ekvivalentní" klasifikaci s po částech lineární hraniční plochou
MU
Janoušová: Analýza a klasifikace dat |yj 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 cor 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   |yj \\
Metody stanovení klasifikačních hranic
i-
• Fisherova lineární diskriminace (FLDA)
• Algoritmus podpůrných vektorů
• Metoda nejmenších čtverců
• Perceptron
MU ,.....t
Janoušová: Analýza a klasifikace dat (^j 12
Metody stanovení klasifikačních hranic
Fisherova lineární diskriminace (FLDA)
MU
Janoušová: Analýza a klasifikace dat |yj 13
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
x1
O O Qfr OGft /^SM4 A -A-
projekce 1
předpoklad: vícerozměrné normální rozdělení u jednotlivých skupin
MU
Janoušová: Analýza a klasifikace dat |yj 14
Fisherova lineární diskriminace - princip
O pacienti
A kontroly
+ centroid pacientů
+ centroid kontrol
x1
O O (OSE cx&z^a&fr A-A-
projekce 1
podstatou FLDAtedy projekce do 1-D prostoru tak, že chceme:
maximalizovat vzdálenost skupin
minimalizovat variabilitu uvnitř skupin
Fisherovo diskriminační kritérium je tedy ve tvaru: J(w) =
4 + 4
kde a jsou rozptyly uvnitř třídy pacientů resp. kontrol po projekci do 1-D prostoru a Y d a Y h Jsou projekce centroidu třídy pacientů resp. kontrol
Janoušová: Analýza a klasifikace dat
IBA
W 15
Projekce do 1-D prostoru
xi
• bod X; reprezentuje í-tý subjekt
• Yi je projekce bodu xt
• w je váhový vektor udávající směr 1-D prostoru
MU
Janoušová: Analýza a klasifikace dat |yj 16
Projekce do 1-D prostoru
)-
• projekce centroidů skupiny pacientů a kontrolních subjektů:
xd = [—2-í=iX£i   — Li=1Xi2   "'   —Li=1XiV\     yD = wlxD
• výpočet rozptylu uvnitř třídy pacientů po projekci do 1-D prostoru:
s2o = ^ffiOr, - y.)2 = ^^(w^ - w%)2 = -i^CwTfc - xD))2
= wT (-J^^iCx; - xD)(xř - xD)T) w = wT Sdw
• analogicky výpočet rozptylu uvnitř třídy kontrol po projekci do 1-D prostoru: s# = ••• = wTSHw
MU
Janoušová: Analýza a klasifikace dat |yj 17
Fisherovo diskriminační kritérium - rozepsání
(v —v ^2
Fisherovo diskriminační kritérium: J(w) =
sd + sh
rozepsání součtu rozptylů uvnitř jednotlivých tříd po transformaci do 1-D prostoru (tzn. rozepsání jmenovatele Fisherova diskr. kritéria):
SB + sh — wTSDw + wTSHw = wT(SD + SH)w = wTSww,
kde     je suma čtverců variability uvnitř skupin a lze ji vypočítat jako:     = SD + SH
v obecném případě (při nevyvážených počtech subjektů ve skupinách) -
vazena suma čtverců variability uvnitř skupin: =-----
(nD+nH-2)
rozepsání rozdílu centroidů promítnutých do 1-D prostoru (tzn. rozepsání čitatele Fisherova diskr. kritéria):
(Yd ~ Yh)2 = (wTxD - wTxH)2 = (wT(xD - xH))2 = wT(xD - xH)(xD - xH)Tw = wTSBw, kde SB je suma čtverců variability mezi skupinami
(Jd-Yh)2 wTSfíw
Fisherovo diskr. kritérium lze tedy vyjádřit jako: J(w) =
Janoušová: Analýza a klasifikace dat     *jL (yj
Fisherovo diskriminační kritérium - maximalizace
Fisherovo diskriminační kriterium: J(w) =   7   7   = —~-
SD + SH W1 Svi/W
Chceme maximalizovat J(w), proto J(w) zderivujeme a položíme výraz roven 0:
d
J(w) = 0
dw
(čJw wtsfíw) wTs^w ~ wTsfíw wTS^w^
(wTS^w)2
(2Sfíw)wTSM/w — wTSfíw(2S^w)
= 0
(wTS^w)2 ° (wTSfíw)SM/w = (wTSM/w)Sfíw
u vektoru w nás nezajímá jeho modul (tzn. velikost), jen jeho směr, proto můžeme pominout skalární členy wTS#w a wTSwW, čímž dostáváme:
Janoušová: Analýza a klasifikace dat     *|L   |yj ig
Fisherovo diskriminační kritérium - maximalizace
Sww ~ SRw
B
protože SBw = (xD - xH)(xD - xH)Tw = (xD - xH) • a, kde a je nějaký skalár -> SBw 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)
Janoušová: Analýza a klasifikace dat
IBA
M 20
Fisherova LDA-výpočet hranice
O   ° O
°   °+o o/
/a a,.a a
/a a a
ooc» cx&z^a&fr A-A-
projekce 1
O pacienti
A kontroly
+ centroid pacientů
+ centroid kontrol
hranice je dána: wrx — ý = 0, kde ý je průmět hraničního bodu v 1-D prostoru a lze ho vypočítat jako: ý =
Yd+Yh
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ů
1h # 21
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	• —	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
E o
u
> o
_^
M
O
E E
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
W 22
Příklad - řešení
	"2	12"		"5	7"
XD =	4	10		3	9
	.3	8.		.4	5.
£:ř4 $ s°=s«=[-i "/i -=1« *
[4 7]
MU V4>-W
A   W 23
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"
evropský
sociální
fond V ČR   EVROPSKÁ UNIE
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
MINISTERSTVO ŠKOLSTVÍ, OPVzdělávání MLÁDEŽE A TĚLOVÝCHOVY      pro konkurenceschopnost
MU
Janoušová: Analýza a klasifikace dat |yj 24