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
V. 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
KLASIFIKACE PODLE DISKRIMINAČNÍCH FUNKCÍ
þ
þ
þnejjednodušším tvarem diskriminační funkce je funkce lineární, která má tvar
þgr(x) = ar0 + ar1x1 + ar2x2 +…+ arnxn
þ kde ar0 je práh diskriminační funkce posouvající počátek souřadného systému a ari jsou váhové
koeficienty i-tého příznaku xi
þlineárně separabilní třídy
2_1 2_7

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
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
þ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
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
þalgoritmus podpůrných vektorů

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
þ    , x0 = 1
þ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Ů
þkdyž cílové vektory trénovací množiny tk, k=1,…K splňují lineární funkcí
þaT.tk +b = 0
þpro libovolné k a dané konstanty a a b, pak lineární klasifikační model pro libovolný obraz
splňuje ekvivalentní vztah
þaT.g(x) +b = 0
þTo znamená, že pro kódovací schéma 1 z R pro R klasifikačních tříd, je součet prvků vektoru g(x)
roven jedné stejně jako součet prvků vektoru tk pro libovolný obrazový vektor x. Tento požadavek
ale není postačující, protože hodnoty vektoru g(x) nejsou nutně vázány na interval á0; 1ñ, což by
bylo třeba, kdyby měly vyjadřovat odhady pravděpodobností zatřídění do jednotlivých klasifikačních
kategorií.

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
þUČENÍ
þObecné požadavky na postup nastavení hodnot váhových koeficientů perceptronu (a nejen perceptronu)
jsou:
þalgoritmická formulace – tj. metoda musí najít řešení pomocí konečného počtu dílčích kroků;
þkonvergence – výpočet by měl být monotónní a pokud možno co nejrychlejší.
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERCEPTRON
þUČENÍ
þna vstup perceptronu jsou vkládány prvky trénovací množiny a výsledek klasifikace je srovnán
s očekávanou správnou klasifikací;
þpokud je rozdíl mezi klasifikátorem určenou a správnou klasifikací větší než určitá předem daná
mez definující přípustnou chybu, pak se parametry klasifikátoru (váhové koeficienty) změní tak, aby
se chyba mezi určenou a požadovanou klasifikací minimalizovala;
þpokud je chyba klasifikace větší než předem stanovená mez, pak učení dále pokračuje, v opačném
případě se učení ukončí a klasifikátor je možné použít ke klasifikaci. Kromě zmíněného absolutního
kritéria ukončení učicí se fáze se v současné době často používá pro zastavení učení i relativní
kritérium založené poklesu chyby během daného časového okna.
þ

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
FISHEROVA DISKRIMINACE
skenování0001.jpg

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 þs použitím Langrangova součinitele (multiplikátoru) 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
þrozptyl transformovaných dat ze třídy ω1 je dána
þ
þ kde yi= wTxi;
þcelkový rozptyl 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 je kovarianční matice 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)
þ
þ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
ALGORITMUS PODPŮRNÝCH VEKTORŮ
þAlgoritmus podpůrných vektorů (Support Vector Machine - SVM) je metoda strojového učení. SVM hledá
nadrovinu, která v prostoru příznaků optimálně rozděluje trénovací data. þOptimální nadrovina je
taková, že body leží v opačných poloprostorech a hodnota minima vzdáleností bodů od roviny je co
největší. Jinými slovy, okolo nadroviny je na obě strany co nejširší pruh bez bodů. þNa popis
nadroviny stačí pouze nejbližší body, kterých je obvykle málo - tyto body se nazývají podpůrné
vektory (angl. support vectors) a odtud název metody. Tato metoda je ze své přirozenosti binární,
tedy rozděluje data do dvou množin. Rozdělující nadrovina je lineární funkcí v prostoru příznaků.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
(SUPPORT VECTOR MACHINE – SVM)
þSEPARABILNÍ TŘÍDY
þmějme v učební množině obrazy xi, i=1,2,…,n, ze dvou lineárně separabilních klasifikačních tříd
ω1 a ω2
þcílem je určení parametrů definující hranici
þy(x) = wTx + w0 = 0,
þjejíž pomocí klasifikátor správně zařadí všechny obrazy z učební množiny
skenování0001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
þDůležitou součástí techniky SUPPORT VECTOR MACHINES je jádrová transformace (angl. kernel
transformation) prostoru příznaků dat do prostoru transformovaných příznaků typicky vyšší dimenze.
Tato jádrová transformace umožňuje převést původně lineárně neseparovatelnou úlohu na úlohu
lineárně separovatelnou, na kterou lze dále aplikovat optimalizační algoritmus pro nalezení
rozdělující nadroviny. þPoužívají se různé jádrové transformace. Intuitivně, vyjadřují podobnost
dat, tj. svých dvou vstupních argumentů. þVýhodou této metody (a jiných metod založených na jádrové
transformaci) je, že transformace se dá definovat pro různé typy objektů, nejen body v Rn. Např.
pro grafy, stromy, posloupnosti DNA ...
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
skenování0002.jpg skenování0003.jpg
dvourozměrný prostor s oddělovací hranicí ve tvaru
x12 + x22 ≤ 1
tatáž situace zobrazená do trojrozměrného prostoru
(x12, x22, Ö2x1x2) – kruhová hranice se stane lineární

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
SEPARABILNÍ TŘÍDY
þpřipomenutí:
þvzdálenost jakéhokoliv bodu od klasifikační hranice je
skenování0001.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þurčeme hodnoty váhového vektoru w a w0 tak, aby hodnota y(x) v nejbližším bodě třídy ω1 byla rovna
1 a pro ω2 rovna -1
ALGORITMUS PODPŮRNÝCH VEKTORŮ
SEPARABILNÍ TŘÍDY
skenování0002.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
SEPARABILNÍ TŘÍDY
þmáme „ochranné“ klasifikační pásmo o šířce
þ
þ
þ a chceme
þ
þ nebo také - chceme najít minimální
þ
þ
þza předpokladu, že
þ
þkde ti =+1 pro ω1 a ti =-1 pro ω2
þ(minimalizace normy maximalizuje klasifikační pásmo)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þnelineární kvadratická optimalizační úloha se soustavou podmínek formulovaných pomocí lineárních
nerovností þKarushovy-Kuhnovy-Tuckerovy podmínky praví, že pro to musí být splněno
þ
þ
þ
þ
þ
þ kde λ je vektor Langrangových součinitelů a L(w,w0, λ) je Lagrangova funkce definována vztahem
ALGORITMUS PODPŮRNÝCH VEKTORŮ
SEPARABILNÍ TŘÍDY

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þkdyž se všechny vztahy z předcházející strany dají dohromady dostaneme
ALGORITMUS PODPŮRNÝCH VEKTORŮ
SEPARABILNÍ TŘÍDY
podpůrné vektory

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ALGORITMUS PODPŮRNÝCH VEKTORŮ
NESEPARABILNÍ TŘÍDY
þstále ale platí, že klasifikační „ochranné“ pásmo je definováno dvěma paralelními „nadrovinami“
definovanými
þwTx + w0 = ± 1
þobrazy z trénovací množiny patří do následujících tří kategorií:
èobraz leží vně pásma a je správně klasifikován [platí podmínka ti(wTx+w0)³1 i=1,2,…,n];
skenování0003.jpg
èobraz leží uvnitř pásma a je správně klasifikován (čtverečky) [platí pro ně 0£ ti(wTx+w0)<1];
èobraz je chybně klasifikován (kolečka) [platí pro něj ti(wTx+w0)<0]

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þvšechny tři kategorie obrazů mohou být řešeny na základě pro daný typ specifických podmínek
þ ti(wTx+w0)³1-ξi
þ pomocí nově zavedených proměnných ξi (tzv. volné proměnné - slack variables).
þ První kategorie je pro ξi=0, druhá 0<ξi£1 a třetí pro ξi>1.
þCílem návrhu v tomto případě je vytvořit co nejširší „ochranné“ pásmo, ale současně minimalizovat
počet obrazů s ξi>0, což vyjadřuje kritérium se ztrátovou funkcí
þ
þ
þ kde ξ je vektor parametrů ξi a
ALGORITMUS PODPŮRNÝCH VEKTORŮ
NESEPARABILNÍ TŘÍDY
C je kladná korekční konstanta, která váhuje vliv obou členů v uvedeném vztahu.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þoptimalizace je obtížná, protože ztrátová funkce je nespojitá (díky funkci I(•)). V takových
případech se proto používá náhradní ztrátová funkce
þ
þa cílem návrhu je minimalizovat J(w,w0,ξ) za podmínek, že
þ ti(wTx+w0)³1-ξi a ξi ³0, i=1,2,…,n.
þProblém lze opět řešit pomocí Langrangeovy funkce
þ
ALGORITMUS PODPŮRNÝCH VEKTORŮ
NESEPARABILNÍ TŘÍDY

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þpříslušné Karushovy-Kuhnovy-Tuckerovy podmínky jsou
þ
ALGORITMUS PODPŮRNÝCH VEKTORŮ
NESEPARABILNÍ TŘÍDY

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þz čehož platí požadavek na maximalizaci L(w,w0,λ,ξ,μ) za podmínek
þ
ALGORITMUS PODPŮRNÝCH VEKTORŮ
NESEPARABILNÍ TŘÍDY

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
SOUVISLOSTI MEZI PRINCIPY KLASIFIKACE
þ
þ
þKLASIFIKACE PODLE MINIMÁLNÍ VZDÁLENOSTI
þreprezentativní obrazy klasifikačních tříd - etalony
þje-li v obrazovém prostoru zadáno R poloh etalonů vektory x1E, x2E,…, xRE, zařadí klasifikátor
podle minimální vzdálenosti klasifikovaný obraz x do té třídy, jejíž etalon má od bodu x minimální
vzdálenost. Rozhodovací pravidlo je určeno vztahem
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ
þ
þuvažme případ dvou tříd reprezentovaných etalony x1E = (x11E, x12E) a x2E = (x21E, x22E) ve
dvoupříznakovém euklidovském prostoru; þvzdálenost mezi obrazem x = (x1,x2) a libovolným z obou
etalonů je pak definována
þ
þ
þhledáme menší z obou vzdáleností, tj. mins=1,2v(xsE,x), ale také mins=1,2v2(xsE,x);
SOUVISLOSTI MEZI PRINCIPY KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ
þ
SOUVISLOSTI MEZI PRINCIPY KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ
þ
þ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 + x211E - 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í
þß
þ klasifikátor pracující na základě kritéria minimální vzdálenosti je „ekvivalentní“ lineárnímu
klasifikátoru s diskriminačními funkcemi.
þ
SOUVISLOSTI MEZI PRINCIPY KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ
þ
þKlasifikace podle minimální vzdálenosti s třídami reprezentovanými více etalony je „ekvivalentní“
klasifikaci podle diskriminační funkce s po částech lineární hraniční plochou
2_13
SOUVISLOSTI MEZI PRINCIPY KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
SOUVISLOSTI MEZI PRINCIPY 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.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þPříprava nových učebních materiálů
þoboru Matematická biologie
þje podporována projektem ESF
þč. CZ.1.07/2.2.00/28.0043
þ„INTERDISCIPLINÁRNÍ ROZVOJ STUDIJNÍHO OBORU MATEMATICKÁ BIOLOGIE“
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU