ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc.
INVESTICE ROZVOJE VZDĚLÁVÁNÍ © Institut DO biostatistiky a analýz
IV. LINEÁRNÍ KLASIFIKACE
© Institut biostatistiky a analýz
PRINCIPY KLASIFIKACE ;
pomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě;
;
pomocí definice hranic mezi jednotlivými třídami a logických pravidel;
;
pomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd;
;
pomocí ztotožnění s etalony;
© Institut biostatistiky a analýz
LINEÁRNÍ SEPARABILITA
lineárně separabilní úloha
lineárně neseparabilní úloha lineárně separované klasifikační třídy
nelineárně separabilní úloha
© Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA PRINCIP
nejjednodušší realizace hraniční plochy je lineární funkcí y(x) = wTx + w0 w je váhový vektor, w0 je práh; x ∈ ω1, když y(x) ≥ 0 x ∈ ω2, když y(x) < 0 rovnice hranice je y(x) = wTx + w0 = 0 ((n-1)-rozměrná nadplocha (nadrovina) v nrozměrném prostoru © Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA ZÁKLADNÍ VLASTNOSTI
zápis v jiném (kompaktnějším) tvaru:
~ = (w , w ) a ~ x0=1 a pak w x = (x0, x) 0 z toho
~ T .~ y( x ) = w x
© Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA ZÁKLADNÍ VLASTNOSTI
;
pro xA, xB na hraniční přímce je y(xA)= y(xB)= 0; proto je i wT(xA-xB)=0 ⇒ vektor w je ortogonální (kolmý) k hraniční přímce;
;
je-li x na hraniční přímce, je y(x)= 0 a tak normálová vzdálenost počátku od hraniční přímky je dána vztahem T
w0 w x =− w w
© Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA ZÁKLADNÍ VLASTNOSTI
© Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA ZÁKLADNÍ VLASTNOSTI
y(x) udává kolmou vzdálenost d bodu x od hraniční přímky (je-li x⊥ ortogonální projekce x na hranici tak, že
w x = x⊥ + d w vynásobením obou stran wT, přičtením w0 a s použitím y(x) = wTx + w0 a y(x⊥) = wTx⊥ + w0 = 0, dostaneme y( x) d= w © Institut biostatistiky a analýz
ÚLOHA S VÍCE TŘÍDAMI ;
kombinace více tříd (problém?): Î klasifikace
„jedna versus zbytek“
R-1 hranice oddělí jednu klasifikační třídu od všech dalších Î klasifikace
„jedna versus jedna“
R(R-1)/2 binárních hranic mezi každými dvěma třídami
© Institut biostatistiky a analýz
ÚLOHA S VÍCE TŘÍDAMI ;
jak se vyhnout „problémům“? zavedením principu diskriminační funkce gr(x) = wrTx + wr0 do r-té třídy ωr zařadíme obraz x za předpokladu, že gr(x) > gs(x) pro ∀ r≠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í
© Institut biostatistiky a analýz
METODY STANOVENÍ KLASIFIKAČNÍCH HRANIC ;
metoda nejmenších čtverců
;
perceptron (neuron)
;
Fisherova lineární diskriminace
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ ;
minimalizace součtu čtverců chybové funkce;
;
mějme cílový (klasifikační) vektor vyjádřen binárním kódem 1 z R (t = (0,0,0,1,0)T)
;
každá je třída ωr popsána lineární funkcí gr(x) = wrTx + wr0, kde r = 1, …,R;
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ sumární popis těchto reprezentací je ~T~ g( x ) = W .x ~T kde W je matice, jejíž r-tý sloupec zahrnuje n+1 dimenzionální vektor T T ~ ~ w r = (w 0, w r ) a x = (x0, x ) hodnota x na vstupu je zařazena do třídy, pro ~ T .~ níž je gr ( x ) = w r x největší;
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ pokud máme učební množinu vyjádřenou {xi,ti}, i=1,…,n a i-tý řádek matice T obsahuje vektor tiT a ~ X v matici je i-tý řádek ~ x iT, pak funkce součtu čtverců chyb je T ~ ~ 1 ~ ~ ~ En ( W ) = Tr X.W − T X.W − T 2 ~ Derivací podle W , kterou položíme rovno nule dostáváme ~ ~ T ~ −1 ~ T ~ℑ W = (X X) X T = X T ~ ~ kde X ℑ je tzv. pseudoinverzní matice k matici X . Diskriminační funkce pak jsou ve tvaru
{(
)(
)}
~ ~ ~ g( x ) = W T .x = T T ( X ℑ )T .~ x
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ
© Institut biostatistiky a analýz
PERCEPTRON MODEL NEURONU
© Institut biostatistiky a analýz
MODEL NEURONU
vstup
výstup
d
∑ xi w i < T
0
k =1 d
∑ xi w i ≥ T
1
k =1
n
n
i =1
i =0
ξ = ∑ wi xi − θ = ∑ wi xi Lineární model neuronu s prahem © Institut biostatistiky a analýz
PERCEPTRON ;
předpokládejme, že w*Tx > 0 pro ∀x∈ω1 w*Tx < 0 pro ∀x∈ω2
;
snažíme se o nalezení extrému ztrátové funkce perceptronu
J( w ) = ∑ (δ x w T x )
(S)
x∈Y
;
Y je podmnožina učební množiny, jejíž obrazy byly chybně klasifikovány s daným nastavením váhového vektoru w; hodnoty proměnné δx jsou stanoveny tak, že δx =-1 pro x∈ω1 a δx =1 pro x∈ω2.
;
součet (S) je zřejmě vždycky nezáporný a roven nule pokud Y je prázdná množina.
;
je to funkce spojitá a po částech lineární (gradient není definován
ve chvíli, kdy se mění počet chybně klasifikovaných vektorů x)
© Institut biostatistiky a analýz
PERCEPTRON algoritmus výpočtu w* (gradientní metoda): w ( t + 1) = w ( t ) − ρ t
∂J( w ) ∂w w = w ( t )
w(t) je vektor váhových koeficientů v t-tém kroku iterace; ρt > 0 tam kde je gradient definován je
∂J( w ) = ∑ δxx ∂w x∈Y po dosazení do definičního vztahu je
w ( t + 1) = w ( t ) − ρ t ∑ δ x x x∈Y
© Institut biostatistiky a analýz
PERCEPTRON algoritmus výpočtu w* - pseudokód:
zvolte náhodně w(0)
zvolte ρ0
t=0
repeat
Y={∅} for i=1 to N if δxiw(t)Txi ≥ 0 then Y = Y ∪ {xi}
w(t+1) = w(t) - ρtΣx∈Yδxx nastavte ρt t=t+1
until Y={∅} © Institut biostatistiky a analýz
PERCEPTRON
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
redukce dimenzionality?
;
nejdříve dichotomický problém: Î předpokládejme
na vstupu n-rozměrný vektor x, který promítneme do jednoho rozměru pomocí y=wTx
Î projekcí
do jednoho rozměru ztrácíme mnohou zajímavou informaci, ale určením prvků váhového vektoru w můžeme nastavit projekci, která maximalizuje separaci tříd;
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
předpokládejme, že známe učební množinu n1 obrazů z třídy ω1 a n2 obrazů z ω2;
;
střední vektory reprezentující každou třídu jsou 1 1 m1 = x i a m2 = xi n1 i∈ω n 2 i∈ω
;
∑
∑
1
1
nejjednodušší míra separace klasifikačních tříd, je separace klasifikačních průměrů, tj. stanovení w tak, aby byla maximalizována hodnota m2-m1=wT(m2-m1), kde mr=wTmr je průměr projektovaných dat ze třídy ωr; © Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
aby hodnota m2-m1 neomezeně nerostla s růstem modulu w, předpokládáme jeho jednotkovou délku, tj. Σiwi2=1
;
Langrangův součinitel (multiplikátor) pro hledání vázaného extrému
Fisherův w α (m2 – m1) diskriminátor
podle Fisherova pravidla stanovíme pouze optimální směr souřadnice, na kterou promítáme obrazy klasifikovaných tříd. abychom stanovili rozhodovací pravidlo, musíme určit hodnotu prahu w0 © Institut biostatistiky a analýz
LANGRANGŮV SOUČINITEL ;
Langragova metoda neurčitých koeficientů
Nechť f(x,y) a g(x,y) mají v okolí bodů křivky g(x,y)=0 totální diferenciál. Nechť v každém bodě křivky g(x,y)=0 je aspoň jedna z derivací ∂g/∂x, ∂g/∂y různá od nuly. Má-li funkce z=f(x,y,) v bodě [x0,y0] křivky g(x,y)=0 lokální extrém na této křivce, pak existuje taková konstanta λ, že pro funkci F(x,y)=f(x,y) + λ.g(x,y)
(<)
jsou v bodě [x0,y0] splněny rovnice ∂F(x0,y0)/∂x=0; ∂F(x0,y0)/∂y=0
(á)
a samozřejmě g(x0,y0)=0 (podmínky nutné). Vázané extrémy lze tedy hledat tak, že sestrojíme funkci (<) a řešíme rovnice (á) pro neznámé x0,y0, λ (λ nazýváme Lagrangeův součinitel (multiplikátor)).
© Institut biostatistiky a analýz
LANGRANGŮV SOUČINITEL ;
Langragova metoda neurčitých koeficientů
totální diferenciál: Je-li f(x,y) v [x0,y0] diferencovatelná, nazývá se výraz dz =(∂f/∂x).dx + (∂f/∂y).dy totální diferenciál funkce z=f(x,y).
© Institut biostatistiky a analýz
LANGRANGŮV SOUČINITEL ;
Langragova metoda neurčitých koeficientů
podmínky postačující: Sestrojme v bodě [x0,y0] druhý diferenciál funkce (<) d2F(x0,y0)= ∂2F(x0,y0)/∂x2+2∂2F(x0,y0)/∂x ∂x +∂2F(x0,y0)/∂y2 (Å) Jestliže pro všechny body [x0+dx,y0+dy] z určitého okolí bodu [x0,y0] takové, že g(x0+dx,y0+dy)=0 a že dx a dy nejsou zároveň rovny nule, je (Å) kladné, resp. záporné, pak je v bodě [x0,y0] vázaný lokální extrém, a to minimum (resp. maximum).
© Institut biostatistiky a analýz
LANGRANGŮV SOUČINITEL ;
Langragova metoda neurčitých koeficientů
Obdobně se řeší úloha najít vázané extrémy funkce několika proměnných, např. nutná podmínka k existenci lokálního extrému funkce w=f(x,y,z,u,v) při podmínkách F1(x,y,z,u,v), F2(x,y,z,u,v) je splnění rovnic ∂G/∂x=0, ∂G/∂y=0, ∂G/∂z=0, ∂G/∂u=0, ∂G/∂v=0, F1=0 a F2=0, kde G= f+ λ1F1+λ2F2, tj. soustava 7 rovnic pro 7 neznámých.
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE problém:
řešení: nejen maximální vzdálenost tříd, ale současně i minimální rozptyl uvnitř tříd © Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
variance transformovaných dat ze třídy ω1 je dána s 2 = ( y − m )2 r
∑
i
i
i∈ω1
kde yi= wTxi; ;
celková variance uvnitř klasifikačních tříd z celé báze dat jednoduše součtem s12 + s22
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
Fisherovo kritérium: J( w ) =
;
(m 2 − m1 )2 s12 + s 22
po dosazení maticově:
J( w ) =
w T SB w
()
T
w SW w
kde SB matice kovariance mezi třídami SB =(m2-m1)(m2-m1)T a SW je matice celkové kovariance uvnitř tříd
SW =
∑
i∈ω1
( x i − m1 )( x i − m1 )T +
∑
( x i − m2 )( x i − m2 )T
i∈ω2
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE ;
maximální J(w) určíme po derivaci () podle w tehdy, když platí (wTSBw)Sww = (wTSWw)SBw z toho pak wα
Sw-1(m2-m1)
α je Langrangův multiplikátor
Fisherův diskriminátor
směr vektoru m2-m1 je na rozdíl od původního případu modifikován maticí Sw; pokud je kovariance uvnitř tříd izotropní (rozptyl je týž ve všech směrech), Sw je úměrná jednotkové matici a w má opět směr vektoru m2-m1 © Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE VÍCE KLASIFIKAČNÍCH TŘÍD
předpoklady: Î
počet tříd: R>2
Î
rozměr dat: n>R
zavedeme n’ > 1 lineárních funkcí yk=WkTX, kde k=1,2,…,n’. Hodnoty yk tvoří vektor y. Podobně váhové vektory Wk reprezentují sloupce matice W y = WTx zobecnění matice kovariance uvnitř tříd R
SW =
∑S
r
r =1
kde
Sr =
∑
i∈ωr
1 ( x i − mr )( x i − mr ) a mr = . x i nr i∈ω
nr je počet vzorků v r-té třídě
T
∑ r
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE VÍCE KLASIFIKAČNÍCH TŘÍD
;
abychom byli schopni určit zobecněnou matici kovariance mezi třídami, určíme nejdříve celkovou kovarianční matici n
ST =
∑
( x i − m)( x i − m)T
i=1
;
kde m je průměr celé množiny obrazů n
m= ;
R
1 1 . x i = . nr x i a n = n i=1 n r =1
∑
∑
∑n r
r
pro celkovou kovarianční matici platí ST = SW + SB, kde R
SB =
∑
nr (mr − m)(mr − m)T
r =1
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE VÍCE KLASIFIKAČNÍCH TŘÍD
;
podobně mohou být definovány matice v transformovaném n’–rozměrném prostoru y R
sW =
∑∑
( yi − μr )( yi − μr )T a
r =1 i∈ωr
R
sB =
∑
nr (μr − μ)(μr − μ)T ,
r =1
kde 1 μr = nr
∑
i∈ωr
1 yi a μ = n
R
∑n μ
r r
r =1
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE VÍCE KLASIFIKAČNÍCH TŘÍD
;
opět chceme určit co největší skalár když je velká kovariance mezi třídami a malá kovariance uvnitř tříd z mnoha kritérií, např.
J( W ) = Tr {s −W1.sB } toto kritérium může být přepsáno do tvaru
J( W ) = Tr {( WS W W T ) −1( WS W W T )} ;
váhové vektory jsou v tom případě dány vlastními vektory matice SW-1SB, které odpovídají jejím n’ největším vlastním číslům
© Institut biostatistiky a analýz
Příprava nových učebních materiálů pro obor Matematická biologie je podporována projektem ESF
č. CZ.1.07/2.2.00/07.0318
„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ © Institut biostatistiky a analýz