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
– pokračování —

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Ů
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
þpřímé rozšíření řešení případu dichotomického problému podle schématu
è„jedna versus zbytek“ – M dichotomických úloh;
è každý klasifikátor je trénován podle schématu s hraniční funkcí yi(x)>0 pro obrazy z ωi a yi(x)<0
pro všechny ostatní;
è„jedna versus jedna“ – M(M-1)/2 binárních klasifikátorů
èklasifikační schéma používající K binárních klasifikátorů, přičemž jednotlivé shluky obrazů z
jednotlivých tříd jsou stanoveny navrhovatelem a jsou kódovány vektory o délce K, jehož hodnoty
jsou +1 nebo -1.
è např. pro M=4 a K=6 může být taková matice
è
ALGORITMUS PODPŮRNÝCH VEKTORŮ
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