logo-IBA logo-MU
© Institut biostatistiky a analýz
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU
ANALÝZA A KLASIFIKACE DAT
prof. Ing. Jiří Holčík, CSc.

logo-IBA logo-MU
© Institut biostatistiky a analýz
IV. LINEÁRNÍ KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
LINEÁRNÍ SEPARABILITA
lin separabilitaq.bmp
lineárně separabilní úloha
nelineárně separabilní úloha
lineárně neseparabilní úloha
lineárně separované klasifikační třídy

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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 n-rozměrném prostoru
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DICHOTOMICKÁ ÚLOHA
ZÁKLADNÍ VLASTNOSTI
þzápis v jiném (kompaktnějším) tvaru:
þ
þx0=1 a pak
þz toho

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
skenování0001.jpg
DICHOTOMICKÁ ÚLOHA
ZÁKLADNÍ VLASTNOSTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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
þ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

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ÚLOHA S VÍCE TŘÍDAMI
þkombinace více tříd (problém?):
èklasifikace „jedna versus zbytek“
qR-1 hranice oddělí jednu klasifikační třídu od všech dalších
èklasifikace „jedna versus jedna“
qR(R-1)/2 binárních hranic mezi každými dvěma třídami
è
skenování0002.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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í
è
skenování0003.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METODY STANOVENÍ KLASIFIKAČNÍCH HRANIC
þmetoda nejmenších čtverců
þperceptron (neuron)
þFisherova lineární diskriminace

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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;
þ
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ
þ sumární popis těchto reprezentací je
þ
þ kde       je matice, jejíž r-tý sloupec zahrnuje n+1 dimenzionální vektor
þ
þhodnota x na vstupu je zařazena do třídy, pro níž je největší;
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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
v matici    je i-tý řádek    , pak funkce součtu čtverců chyb je
þ
þ
þDerivací podle     , kterou položíme rovno nule
þdostáváme
þ
þ
þkde      je tzv. pseudoinverzní matice k matici    .
þDiskriminační funkce pak jsou ve tvaru
þ
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ
skenování0004.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
METODA NEJMENŠÍCH ČTVERCŮ
skenování0005.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERCEPTRON
þ
skripta_obr_2_1_popisky
MODEL NEURONU

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
vstup výstup
    0
    1
MODEL NEURONU
Lineární model neuronu s prahem
>

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERCEPTRON
þpředpokládejme, že
þw*Tx > 0 pro "xÎw1
þw*Tx < 0 pro "xÎw2
þsnažíme se o nalezení extrému ztrátové funkce perceptronu
þ
þ (p)
þ
þ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é dx jsou stanoveny tak, že dx =-1 pro xÎw1 a dx =1 pro xÎw2. þsoučet (p)
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)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þalgoritmus výpočtu w* (gradientní metoda):
þ
þ
þw(t) je vektor váhových koeficientů v t-tém kroku iterace;
þrt > 0
þtam kde je gradient definován je
þ
þ
þpo dosazení do definičního vztahu je
þ
PERCEPTRON

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
algoritmus výpočtu w* - pseudokód:
§zvolte náhodně w(0)
§zvolte r0
§t=0
§repeat
Y={Æ}
for i=1 to N
if dxiw(t)Txi ³ 0 then Y = Y È {xi}
w(t+1) = w(t) - rtΣxÎYdxx
nastavte rt
t=t+1
§until Y={Æ}
skenování0012.jpg
PERCEPTRON

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERCEPTRON
skenování0013.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
skenování0016.jpg
FISHEROVA DISKRIMINACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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
þ
þ
þ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;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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.
Siwi2=1 þLangrangův součinitel (multiplikátor) pro hledání vázaného extrému
þw a (m2 – m1)
þ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
Fisherův diskriminátor

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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 l, že pro
funkci
þF(x,y)=f(x,y) + l.g(x,y) (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  (Y) a řešíme rovnice (ÿ) pro neznámé
x0,y0, l (l nazýváme Lagrangeův součinitel (multiplikátor)).
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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).

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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 (Y)
þ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).
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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+ l1F1+l2F2, tj. soustava 7 rovnic pro 7 neznámých.
þ
þ
þ
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE
skenování0006.jpg
problém:
řešení:
nejen maximální vzdálenost tříd, ale současně i minimální rozptyl uvnitř tříd

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE
þvariance transformovaných dat ze třídy ω1 je dána
þ
þ kde yi= wTxi;
þcelková variance uvnitř klasifikačních tříd z celé báze dat jednoduše součtem s12 + s22

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FISHEROVA DISKRIMINACE
þFisherovo kritérium:
þ
þ
þpo dosazení maticově:
þ
þ  (%)
þ
þ kde SB matice kovariance mezi třídami
þSB =(m2-m1)(m2-m1)T
þa SW je matice celkové kovariance uvnitř  tříd
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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 a Sw-1(m2-m1)
þ a je Langrangův multipliká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
Fisherův diskriminátor

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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
þ
þ
þkde
þ
þ
þnr je počet vzorků v r-té třídě

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þabychom byli schopni určit zobecněnou matici kovariance mezi třídami, určíme nejdříve celkovou
kovarianční matici
þ
þ
þkde m je průměr celé množiny obrazů
þ
þ
þ
þpro celkovou kovarianční matici platí ST = SW + SB, kde
FISHEROVA DISKRIMINACE
VÍCE KLASIFIKAČNÍCH TŘÍD

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þpodobně mohou být definovány matice v transformovaném n’–rozměrném prostoru y
FISHEROVA DISKRIMINACE
VÍCE KLASIFIKAČNÍCH TŘÍD

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ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ř.
þ
þ
þ toto kritérium může být přepsáno do tvaru
þ
þ
þ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
FISHEROVA DISKRIMINACE
VÍCE KLASIFIKAČNÍCH TŘÍD

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© 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Í
logo-MU