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 W pokračování X

© 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


ALGORITMUS PODPŮRNÝCH VEKTORŮ SEPARABILNÍ TŘÍDY

;

připomenutí:

vzdálenost jakéhokoliv bodu od klasifikační hranice je

d=

y( x) w



;

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



;

máme „ochranné“ klasifikační pásmo o šířce 1 1 2 + = w w w

a chceme

w Tx + w0 ≥ 1

pro ∀x ∈ ω1

w T x + w 0 ≥ −1 pro ∀x ∈ ω2

nebo také - chceme najít minimální J( w, w 0 ) =

za předpokladu, že

1 w 2

2

t i ( w T x + w 0 ) ≥ 1, i = 1, 2, ..., n

kde ti =+1 pro ω1 a ti =-1 pro ω2 (minimalizace normy maximalizuje klasifikační pásmo) © 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 ∂ L( w, w 0 , λ ) = 0 ∂w ∂ L( w, w 0 , λ ) = 0 ∂w 0

λ i ≥ 0, i = 1, 2,..., n λ i [ t i ( w T x + w 0 ) − 1] = 0, i = 1, 2,..., n, kde λ je vektor Langrangových součinitelů a L(w,w0, λ) je Lagrangova funkce definována vztahem n 1 T L( w, w 0 , λ ) = w w − ∑ λ i [ t i ( w T x i + w 0 ) − 1] 2 i=1



;

když se všechny vztahy z předcházející strany dají dohromady dostaneme n

w = ∑ λitixi i=1

n

∑λ t i=1

i i

podpůrné vektory

=0


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 wT x + w 0 = ± 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]; Î 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]

Î



;

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í n 1 2 J( w, w 0 , ξ ) = w + C∑ I(ξi ) 2 i=1

kde ξ je vektor parametrů ξi a

⎧1 ξi > 0 I(ξi ) = ⎨ ⎩0 ξi = 0

C je kladná korekční konstanta, která váhuje vliv obou členů v uvedeném vztahu.



;

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 n 1 2 J( w, w 0 , ξ ) = w + C∑ ξi 2 i=1

;

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 n n n 1 T L( w, w 0 , ξ, λ,μ) = w w + C∑ ξi − ∑ μiξi − ∑ λ i [ t i ( w T x i + w 0 ) − 1 + ξi ] 2 i=1 i=1 i=1



;

příslušné Karushovy-Kuhnovy-Tuckerovy podmínky jsou n ∂L = 0 nebo w = ∑ λ i t i x i ; ∂w i=1 n ∂L = 0 nebo ∑ λ i t i x i ; ∂w 0 i=1

∂L = 0 nebo C − μi − λ i = 0, i = 1, 2,..., n; ∂ξi

[

]

λ i t i ( w T x + w 0 ) − 1 + ξi = 0, i = 1, 2,..., n; μiξi = 0, i = 1, 2,..., n; μi ≥ 0, λ i ≥ 0, i = 1, 2,..., n;



;

z čehož platí požadavek na maximalizaci L(w,w0,λ,ξ,μ) za podmínek n

w = ∑ λitix i; i=1

n

∑λ t i=1

i i

= 0;

C − μi − λ i = 0, μi ≥ 0, λ i ≥ 0, i = 1, 2,..., n;


ALGORITMUS PODPŮRNÝCH VEKTORŮ VÍCE KLASIFIKAČNÍCH TŘÍD

;

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 Î

⎡− 1 ⎢+ 1 ⎢ ⎢+ 1 ⎢ ⎣− 1

−1 −1 +1 −1

−1 +1 −1 +1

+1 +1 −1 −1

−1 −1 −1 +1

+ 1⎤ − 1⎥⎥ + 1⎥ ⎥ + 1⎦ © 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

ANALÝZA A KLASIFIKACE DAT

Recommend Documents