ANALÝZA A KLASIFIKACE DAT

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;


LINEÁRNÍ SEPARABILITA

lineárně separabilní úloha

lineárně neseparabilní úloha lineárně separované klasifikační třídy

nelineárně separabilní úloha


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



;

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





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


Ú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í


METODY STANOVENÍ KLASIFIKAČNÍCH HRANIC ;

metoda nejmenších čtverců

;

perceptron (neuron)

;

Fisherova lineární diskriminace


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;


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ší;


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


METODA NEJMENŠÍCH ČTVERCŮ


METODA NEJMENŠÍCH ČTVERCŮ


PERCEPTRON MODEL NEURONU


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)


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


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


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;


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


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)).




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).




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).




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.


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


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



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



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



;

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



;

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



;

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


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

ANALÝZA A KLASIFIKACE DAT

Recommend Documents