INTELIGENTNI SISTEMI
Metode klasifikacije
Vanr.prof. Dr. Lejla Banjanović- Mehmedović
www.lejla-bm.com
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
1
Sadržaj izlaganja




Metoda K-najbliži susjed
Bayesov klasifikator
Metoda potpornih vektora (SVM)
Validacija metoda klasifikacije
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
2
1
K-najbliži susjed grupisanje
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
3
K-najbliži susjed algoritam (Knearest neighbor)
Proračunati distance izmedju novog uzorka i
svih predhodnih uzoraka, koji su već
klasificirani u klastere
Sortirati distance u rastućem redoslijedu i
selektirati K uzoraka sa najmanjim
vrijednostima distance.
Primjeniti princip izbora. Novi uzorak će
ć biti
dodat (klasificiran) klasteru K sa najvećim
selektiranim uzorcima.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
4
2
K-najbliži susjed algoritam
 Kao mjera distance
uobičajeno
bič j
se koristi
k i ti
Euklidska ili Mahalanobis
distanca.
 Jednostavnija varijanta
algoritma je za k = 1 i
poznat je kao algoritam
najbližeg susjeda (eng.
(eng
Nearest Neighbor, NN).
Ovo znači da novi uzorak
je pridružen klasi
najbližeg susjeda.
Inteligentni sistemi 4
Problematika klasifikacije
uzoraka, koristeći algoritam
najbližeg susjeda (NS)
Copyright: Lejla BanjanovićMehmedović
5
K-najbliži susjed
X 1   A, B, A, B, C , B
X 2   A, A, A, B, A, B
X 3   B, B, A, B, A, B
X 4   B, C , A, B, B, A
X 5   B, A, B, A, C , A
X 6   A, C , B, A, B, B
Inteligentni sistemi 4
C1   X 1 , X 2 , X 3 
C2   X 4 , X 5 , X 6 
Y   A, C , A, B, C , A
Copyright: Lejla BanjanovićMehmedović
???
6
3
K-najbliži susjed
Traženje sličnosti
sličnosti, umjesto distance !!!
SMC Y , X 1   4 / 6  0.66
SMC Y , X 4   4 / 6  0.66
SMC Y , X 2   3 / 6  0.50
SMC Y , X 5   2 / 6  0.33
SMC Y , X 3   2 / 6  0.33
SMC Y , X 6   2 / 6  0.33
C1   X 1 , X 2 , X 3 , Y  !!!
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
7
MATLAB primjer za K
K--najbliži
susjed klasifikator
Rezultat izvršenja KNN
koda:
-
objekti klase 1: plavi
objekti klase 2: crveni
novi objektat: zeleni
najbližih susjeda: 10
--------------------------više crvenih susjeda
pripada klasi objekata 2
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
8
4
Zaključak
 K-najbliži
j
susjed
j
treba koristiti u slučajevima
j
kada postoji malo ili nikakvo prethodno znanje
o distribuciji podataka.
 Tačnost ove metode uveliko ovisi o broju
trenirajućih uzoraka, ako je dati broj manji
tačnost je veća, neovisno o vrijednosti
parametra k.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
9
Bayesov naivni klasifikator
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
10
5
Bayesova teorema
 Skup nezavisnih hipoteza:
H (k ) = Hi k  , i = 00,1,...,N
1 N
 P(Hi) – početna vjerovatnoća hipoteze Hi prije
eksperimenta, tzv. a’priori vjerovatnoća prikazuje
početno znanje o vjerovatnoćama različitih hipoteza.
Ukoliko ne postoji takvo znanje, svim hipotezama se
dodjeljuje jednaka početna vjerovatnoća.
 Izvodi se eksperiment, čiji je rezultat dogadjaj X.
 P(X) – vjerovatnoća pojavljivanja događaja X, bez obzira
na to koja je hipoteza ispravna.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
11
Bayesova teorema
 P(X|Hi) – uslovna vjerovatnoća pojavljivanja X uz uslov
ispravnosti hipoteze Hi.
Hi
 P(Hi|X) – uslovna vjerovatnoća ispravnosti hipoteze Hi
nakon pojavljivanja događaja X, tzv. a'posteriori
vjerovatnoća koja predstavlja naše uvjerenje u
pojedinačnu hipotezu Hi nakon što se desio događaj X.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
12
6
Bayesova teorema
 Pretpostavimo da su hipoteze (događaji) H1, H2, ... Hn
međusobno isključivi i da je njihova unija prostor uzoraka.
uzoraka
 Vjerovatnoća dogadjaja X se računa kao suma proizvoda
vjerovatnoća svake hipoteze sa vjerovatnoćom dogadjaja
pri toj hipotezi (Teorema totalne vjerovatnoće):
N
P ( X )  P ( X  E1 )  ...P ( X  EN )   P ( X | Hi )P (Hi )
i 1
 Bayesova teorema proračunava a’posteriori
vjerovatnoću:
j
t ć
P( H i | X ) 
P( X / H i ) P( H i )
P( X / H i ) P( H i )
 N
P( X )
 P( H i ) P( X / H i )
i 1
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
13
Naivni Bayesov klasifikator
 Spada u grupu statističkih parametarskih klasifikatora
(vektor atributa se interpretira kao stohastička varijabla
čija raspodjela zavisi od klase uzoraka), iz tog razloga se
može koristiti Bayesova teorema u klasifikaciji.
 Pretpostavimo da imamo skup od m uzoraka ili podataka
S ={S1,S2,...,Sm}, gdje je svaki uzorak Si predstavljen
kao n-dimenzini vektor {x1,x2,...,xn}, pri čemu svako xi
predstavlja atribut uzorka.
 Neka je definisano k klasa k1, k2,…, kk i neka svaki
uzorak pripada jednoj od ovih klasa. Neka je dat dodatni
uzorak X, pri čemu ne znamo kojoj klasi pripada.
P (k j | X ) 
Inteligentni sistemi 4
P ( X | k j )P (k j )
P( X )
Copyright: Lejla BanjanovićMehmedović
14
7
Naivni Bayesov klasifikator
 Ukoliko klasifikaciju predstavimo kao
pronalaženje
l ž j najvjerojatnije
j j
j t ij kl
klasifikacije
ifik ij tada
t d
se može računati po izrazu:
kMAP  argmax P (k j x1, x2 ,..., xn )
hH
 što predstavlja najvjerovatniji element
g skupa
p K svih mogućih
g
klasifikacija
j
konačnog
uzoraka. Svaki uzorak prikazan je kao skup
vrijednosti atributa
 x1 , x2 ,..., xn 
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
15
Naivni Bayesov klasifikator
kMAP  argmax P ( k j x1, x2 ,..., xn ) 
k j K
 argmax
k j K


P x1, x2 ,..., xn k j P (k j )
P ( x1, x2 ,..., xn )
 argmax P ( x1, x2 ,..., xn k j )P ( k j )
k j K



Događaji E1, E2,...En su
međusobno nezavisni ako i
samo ako za bilo koji
podskup ovih događaja
vrijedi:
P( Ek 1 , Ek 2 ,...Ekm )  P( Ek1 )  ...  P( Ekm )
Naivni Bayesov klasifikator uvodi pojednostavljenje u vidu
pretpostavljene međusobne nezavisnosti vrijednosti atributa
u n-torkama
n torkama  x1, x2 ,..., xn  tako da vrijedi izraz:
P (k j x1, x2 ,..., xn )   P ( xi k j )

i
Prepravljeni izraz za klasifikaciju Naivnim Bayesovim
klasifikatorom sada glasi:
kMAP  argmax P (k j )
k j K
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
 P( x
i
kj )
i
16
8
Primjer za klasifikaciju Naivnim
Bayesovim klasifikatorom

Za svaki uzorak opisan
p
atributima A1,, A2 i A3 data jje klasa,,
kojoj pripada. Potrebno je predvidjeti klasu za novi uzorak
opisan sa X= {1,2,2}.
Uzorak
Atribut A1
Atribut A2
Atribut A3
Klasa K
1
1
2
1
1
2
0
0
1
1
3
2
1
2
2
4
1
2
1
2
5
0
1
2
1
6
2
2
2
2
7
1
0
0
1
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
17
Primjer za klasifikaciju Naivnim
Bayesovim klasifikatorom
 A’priori vjerovatnoće za svaku od klasa su:
P (K1 )  4 / 7  0.57
P (K 2 )  3 / 7  0.43
 Proračun uslovnih vjerovatnoća za svaki atribut
novog uzorka u odnosu na svaku klasu:
P ( A1  1| K1 )  2 / 4  0.50
P ( A1  1| K 2 )  1/ 3  0.33
P ( A2  2 | K1 )  1/ 4  0.25
P ( A2  2 | K 2 )  2 / 3  0.66
P ( A3  2 | K1 )  1/ 4  0.25
P ( A3  2 | K 2 )  2 / 3  0.66
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
18
9
Primjer za klasifikaciju Naivnim
Bayesovim klasifikatorom
 Pod pretpostavkom uslovne nezavisnosti
atributa,
t ib t uslovne
l
vjerovatnoće
j
t ć su:
n
P ( X K1 )   P ( xt K i ) P ( A1  1 K1 )P ( A2  2 K1 )P ( A3  2 K1 ) 
t 1
0.5  0.25  0.25  0.03125
n
P ( X K 2 )   P ( xt K i ) P ( A1  1 K 2 )P ( A2  2 K 2 )P ( A3  2 K 2 ) 
t 1
0.33  0.66  0.66  0.14375
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
19
Primjer za klasifikaciju Naivnim
Bayesovim klasifikatorom
 Množenjem uslovnih vjerovatnoća sa odgovarajućim
a’priori
a
priori vjerovatnoćama,
vjerovatnoćama moćemo naći odgovarajuće
a’posteriori vjerovatnoće:
P (K1 | X )  P ( X | K1 )P (K1 )  0.03125  0.5714  0.0179
P (K 2 | X )  P ( X | K 2 )P (K 2 )  0.14375  0.4286  0.0616
 te maksimum imeđu njih:
xMAP  argmax P (K i | X )  Max P (K1 | X ), P (K 2 | X ) 
x X
 Max 0.0179,0.0616  0.0616
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
20
10
Metoda potpornih vektora
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
21
Metoda potpornih vektora
 Predviđena je za klasifikaciju u samo dvije kategorije, ali
razvijeni su i različiti pristupi koji omogućuju klasifikaciju
više od dvije kategorije.
 Ova tehnika pruža jako dobre rezultate naročito na
podacima koji imaju veliki broj atributa, tj.
prilagođena je za manipulaciju velikim količinama
podataka.
 Primjena
j




u računarstvu (za raspoznavanje uzoraka),
mobilnoj robotici (manipulacija sa senzorskim informacijama)
genetici (za simulaciju ponašanje novih generacija gena),
ekonomiji (za predviđanje ponašanja tržišta)
 Prvi put predložena 1995. godine.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
22
11
Metoda potpornih vektora
 Pripada grupi kernel (jezgrenih) metoda
kl ifik ij i zasniva
klasifikacije
i
se na principu
i i
minimizacije
i i i
ij
greške na skupu za učenje.
 Osnovna ideja je naći razdvajajuću hiperravan
tako da su svi podaci iz određene klase sa iste
strane ravni.
 Ovo obično nije moguće u ulaznom prostoru (eng. input
space) nego se skup uzoraka (podataka) preslikava u ndi
dimenzijski
ij ki prostor
t poznatiji
tiji pod
d nazivom
i
p osto
prostor
značajki (eng.feature space) u kojem će se provesti
razdvajanje uzoraka.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
23
Metoda potpornih vektora
 SVM je linearni klasifikator
koji pronalazi hiperravan koja
razdvaja dvije klase.
 Postoji beskonačno mnogo
hiperravni koje razdvajaju 2
klase.
 Svaka od hiperravni savršeno
klasifikuje obučavajući skup
(date tačke).
tačke)
Hiperravni koje razdvajaju klase
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
24
12
Metoda potpornih vektora
 Hiperravan koju
pronalazi SVM je
hiperravan sa
najvećom marginom
separacije (eng.
maximum margin
hyperplane), tj. ona
najbolje vrši
klasifikaciju.
Margina separacije
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
25
Metoda potpornih vektora
 Razlikuju se dvije glavne vrste klasifikatora:
 Linearni
 Nelinearni
 Linearni se još dijeli na separabilne i
neseparabilne klasifikatore.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
26
13
Linearni SVM –separabilni slučaj




Separabilni linearni
klasifikator
Inteligentni sistemi 4
Linearni SVM klasifikator
funkcioniše tako što za
zadati obučavajući skup (2
klase) pronalazi hiperravan
separacije sa maksimalnom
marginom separacije.
Hiperravan koja razdvaja
klase (pomoću koje se vrši
klasifikacija) zove se
granica odluke ((eng.
g
g
decision boundary) i
označava jednačinom:
w*x + b = 0
gde su w i b parametri
modela.
Copyright: Lejla BanjanovićMehmedović
27
Treniranje linearnog SVM
 Problem učenja linearnog SVM:
min
w
2
2
y i  ( w  xi  b)  1, i  1, , N
w
 Potrebno je odrediti vektore w i b uz zadate uslove.
 Ovaj problem se rješava metodom Lagranžovih
množilaca. Upotrebom ove metode dobijamo novu
funkciju koja se minimizira:

Lp 
1 2 N
w   i  y i ( w  xi  b)  1
2
i 1
(*)
 gde se parametri λi zovu Lagranžovi množioci.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
28
14
Treniranje linearnog SVM
 Po definiciji metode za Lagranžove množioce moraju da
važe sljedeći
j
uslovi ((Khun-Tucker):
)
i  0
i  y i ( w  xi  b)  1  0
 Vektori xi za koje važi yi*(w*xi + b) = 1 nazivaju se
vektori potpore (eng. support vectors). To su vektori
koji se nalaze na hiperravnima bi1 i bi2 (hiperravni koje
su paralelne granici odluke i kojima pripadaju tačke
najbliže granici odluke).
 Vrijednosti
j
λi izračunavamo p
pomoću dualnog
g problema
p
tj. uvrštavanjem parcijalnih izvoda u (*)

N
N
Lp
Lp
 0   i yi  0
 0  w   i yi xi
b
i 1
w
i 1
N
1
slijedi: LD   i   i  j y i y j xi  x j
2 i, j
i 1
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
29
Treniranje linearnog SVM
 Kada se odredi granica
odluke novi primjeri
klasificiraju se pomoću
sljedeće funkcije:

 N
f ( z )  sign( w  z  b)  sign ( i y i xi  x)  b 

 i 1
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
30
15
Linearni SVM - neseparabilni
slučaj
 Linearno separabilni
podaci su idealan slučaj.
slučaj
 U realnosti postoje greške
u podacima npr. pogrešno
dodjeljena klasa, itd.
 Problem je u tome što uz
prisustvo P i Q u
obučavajućem skupu ne bi
mogli da izračunamo B1 jer
P i Q ne bi zadovolji uslove
iz prethodne analize. Zato
je potrebno relaksirati te
uslove.
Inteligentni sistemi 4
Neseparabilan slučaj za linearni SVM
Copyright: Lejla BanjanovićMehmedović
31
Linearni SVM - neseparabilni
slučaj

Dobijamo granicu odluke koja
g
ima relaksiranu marginu
(eng. soft margin). Novi
uslovi z aobučavanje
linearnog SVM imaju sljedeći
oblik:

w  xi  b  1   i
ako je yi  1
w  xi  b  1   i
ako je yi  1

gde je εi> 0 i=1,...,N (broj
uzoraka). Vrijednosti εi zovu
se promjenljive relaksacije
(eng. slack variables) ili
fiktivne promenljive.
Inteligentni sistemi 4
SVM sa relaksiranom marginom
Copyright: Lejla BanjanovićMehmedović
32
16
Linearni SVM - neseparabilni
slučaj
 Ako funkcija ostane ista
kao u prethodnoj analizi,
analizi
moguće je da će metod
pronaći SVM sa jako
velikim vrijednostima εi tj.
sa širokom marginom ali
koji pogrešno klasifikuje
veliki broj tačaka (slika).
Da bi se tajj p
problem riješio
j
uvodi se parametar C koji
će kažnjavati granice
odluke sa velikim
vrijednostima εi.
Inteligentni sistemi 4
SVM sa velikim vrijednostima εi
Copyright: Lejla BanjanovićMehmedović
33
Linearni SVM - neseparabilni
slučaj
 Nova formula treniranja:
f ( w) 
2
 N 
 C   i 
2
 i 1 
w
k
 gdje k i C parametar zadaje korisnik.
 Ako je k=1 izmenjena funkcija za problem Lagranžovih
množilaca data je sa:
Lp 
N
1 2
 N  N
w  C    i    i  y i ( w  xi  b )  1   i     i  i
2
i 1
 i 1  i 1
 Postupak za minimiziranje ove funkcije je isti. Vrijednost
parametra C uglavnom se određuje pomoću validacionog
(test skupa).
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
34
17
Nelinearni SVM
 Prethodno opisani SVM klasifikatori formiraju linearnu
granicu odluke između dvije klase.
klase
 SVM klasifikatori sa nelinearnom granicom odluke.
Dat obučavajući skup u kome su dvije klase razdvojene
nelinearnom granicom. SVM klasifikator za ovaj skup
formiramo tako što transformišemo tačke iz
obučavajućeg skupa u prostor u kome će te tačke biti
linearno separabilne. U tom novom prostoru
pronalazimo linearni SVM p
p
pomoću p
postupka
p
koji
j jje već
objašnjen.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
35
Nelinearni SVM
Granice odluke u datom prostoru i u prostoru dobijenom transformacijom.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
36
18
Nelinearni SVM
 Funkciju koja služi za transformaciju označićemo sa
Φ(x).
Φ(x)
 Problem učenja linearnog SVM u prostoru dobijenom
transformacijom zapisuje se na sljedeći način:
min
w
2
w
2
y i  ( w   ( xi )  b)  1, i  1,  , N
 dok dualan problem ima oblik:
N
L D   i 
i 1
Inteligentni sistemi 4
1
 i  j y i y j  ( x i )   ( x j )
2 i, j
Copyright: Lejla BanjanovićMehmedović
37
Nelinearni SVM
 Prilikom implementacije nelinearnih SVM dolazi
d više
do
iš problema.
bl
 Kako formirati Φ(x) tako da budemo sigurni da će
tačke u novom prostoru biti linearno separabilne?
 Takođe ako je novi prostor jako velike
dimenzionalnosti izračunavanje skalarnog proizvoda
Φ(xi)*Φ(xj) je vremenski i računski veoma zahtjevno.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
38
19
Nelinearni SVM
 Navedeni problemi rjšavaju se upotrebom funkcija
jezgara (eng.
(eng kernel function).
function)
 Iz dualnog problema slijedi da nije potrebno da
eksplicitno znamo funkciju Φ(x) već samo da znamo
koliki je skalarni proizvod Φ(xi)*Φ(xj) za sve tačke iz
originalnog prostora (obučavajućeg skupa).
 Funkcije koje nam daju vezu između skalarnog proizvoda
xi *xj i Φ(xi)*Φ(xj) su funkcija jezgara. Za funkciju
jezgaraK važi:

K(xi, xj)= Φ(xi)*Φ(xj)
 Neke od često korišćenih funkcija jezgra su polinomske
K(x,y)=(x*y)d i K(x,y)=(x*y + 1)d.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
39
Zaključak SVM metode
 Prednosti:
 Jednostavna primjena
 Tačnost
 Mogućnosti generalizacije problema
 Velika brzina treniranja podataka.
 U praksi, SVM metoda je, iako relativno novija,
pronašla široku primjenu.
primjenu
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
40
20
Validacija metoda
klasifikacije
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
41
Kriteriji za izračunavanje
vrijednosti greške
 Srednja apsolutna greška (eng. mean absolute error –
MAE))
 Korijen srednje kvadratne greške (eng. root mean
squared error – RMSE)
 Relativna apsolutna greška (eng. relative absolute error–
RAE)
 Korijen relativne kvadratne greške (eng. root relative
squared error– RRSE)
 ai -stvarna vrijednost, pi - željena vrijednost.
Inteligentni sistemi 4
Copyright: Lejla BanjanovićMehmedović
42
21
Download

INTELIGENTNI SISTEMI Sadržaj izlaganja