PREPOZNAVANJE UZORAKA
Metode klasifikacije
Metode grupisanja
Vanr.prof. Dr. Lejla Banjanović- Mehmedović
www.lejla-bm.com
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
1
Metode klasifikacije
 Algoritmi klasifikacije vrše raspodjelu uzoraka
u odgovarajuće klase ili grupe uzoraka prema
klasifikacijskoj šemi.
 Uzorak može sadržavati jedan ili više atributa
(obilježja).
 Klase uzoraka su skupovi (familije) uzoraka
koji djele neke zajedničke osobine.
 Tačnost klasifikacije uzoraka značajno ovisi o
izboru odgovarajućih atributa, koja će
omogućiti podjelu uzoraka u klase.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
2
1
Metode klasifikacije
 Razlikujemo dvije šeme klasifikacije:
 Nadgledane metode klasifikacije zasnivaju se na
skupu uzoraka, koji je već ranije klasifikovan ili
prepoznat, tj. zna se kojoj klasi pripada. Ovaj skup
uzoraka naziva se skup za treniranje, a sam proces
se naziva učenje.
 Nenadgledana šema klasifikacije koristi
objektivnu mjeru sličnosti između podataka za
klasifikaciju bez unaprijed poznatih klasa.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
3
Metode klasifikacije
 Različiti inteligentni sistemi koriste
brojne klasifikacione metode:




Stabla odlučivanja
Metode grupisanja
Bayesov klasifikator
Neuronske mreže
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
4
2
Nadzirano učenje
 Klasifikacija
 Regresija
 Neuronske mreže
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
5
Nenadzirano učenje
 Metode grupisanja (klasterizacije)
 Neki tipovi neuronskih mreža:
 Kohonenova samoorganizirajuća mreža
 Hopfieldova mreža
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
6
3
Metode grupisanja
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
7
Metode grupisanja
Metod udaljenosti
Algoritmi grupisanja (grupisanja):
 Inkrementalno (sekvencijalno) grupisanje
 Hijerarhijsko grupisanje
• Aglomerativno grupisanje
• Divizijsko grupisanje
 Parcijalno grupisanje (K-means, Fuzzy Kmeans grupisanje)
 K-najbliži susjed
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
8
4
Metode grupisanja
 Grupisanje
podataka
(segmentiranje
(segmentiranje,
grupiranje, klasterizacija, grupisanje, eng.
clustering) spada u metodu klasifikacije čiji je
cilj ''otkrivanje'' organizacije objekata u obliku
grupa (eng. clusters), na osnovu kriterija
sličnosti ili razlike između objekata, čime se
dolazi do korisnih zaključaka o promatranim
objektima.
 Grupisanje (grupiranje) spada u
nesuperviziranu metodu klasifikacije. (eng.
cluster = grupa)
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
9
Metode grupisanja
 Metode g
grupisanja
p
j
predstavljaju
p
j j
skup
p
metodologija za automatsko klasificiranje
uzoraka u grupe koristeći mjere asocijacije
tako da uzorci u istoj grupi su što više slični a
uzorci u različitim grupama što više različiti.
 Ulaz u sistem klaster analize je skup uzoraka.
 Izlaz iz klaster analize je broj grupa koji formiraju
particiju ili strukturnu particiju u skupu podataka.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
10
5
Metode grupisanja
 Predstavljaju glavni alat koji se koristi u
mnogim
i naučnim
č i oblastima.
bl ti
 Postoji više pravca, gdje se koristi grupisanje,
ali su dva posebno interesantna:
 Redukcija podataka
j ((etimacija)
j ) zasnovana na g
grupama
p
 Predikcija
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
11
Primjena metoda grupisanja
 Inžinjerstvo: analiza podataka u cilju
usporedbe i primjene u robotici,...
robotici
 Inteligentna analiza
 Ispitivanje tržišta: grupisanje kupaca sa
sličnim ponašanjem na osnovu neke baze
podataka koja govori o njihovim osobinama
i posljednjim kupovinama
 Biologija: klasifikacija biljaka i životinja na
osnovu njihovih
h h osobina
b
 Medicina
 Socijalna istraživanja
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
12
6
Definicija grupisanja
 Vektori se posmatraju kao tačke u ldi
dimenzionalnom
i
l
prostoru
t
i grupa je
j opisana
i
kao:
 ''neprekidna oblast prostora sa velikom gustinom
tačaka, odvojena od drugih, istih takvih oblasti sa
oblastima prostora sa relativnom malom gustinom
tačaka''. Grupa opisana na ovakav način se često
zove prirodna grupa.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
13
Klaster analiza
Inteligentni sistemi_3
Copyright: Lejla BanjanovićMehmedović
14
7
Definicija grupisanja
 Posmatrajmo matematski formu formu grupisanja. Neka
je X skup podataka definisan kao:
X  x1, x2 ,..., xN 
 Grupisanje skupa X predstavlja njegovu podjelu u k
podskupova (grupa) G1,G2,…,Gk tako da su zadovoljena
sljedeća tri uslova:
Gi   ,
i  1,2,..., k
k
G
i
X
i 1
Gi  G j   , i  j , j  1,2,..., k
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
15
Klaster analiza tačaka u 2D prostoru
u ovisnosti od broja grupa
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
16
8
Vrste grupa
a) kompaktni klasteri, c) izduženi klasteri,
b) sferični i elipsoidalni klasteri
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
17
Osnovni koraci pri grupisanju
podataka
 Ako pretpostavimo da su svi objekti
predstavljeni preko svojih osobina,
osobina koje
formiraju l-dimenzionalni vektor osobina,
osnovni koraci koje ekspert preuzima prilikom
grupisanja podataka su:






Biranje osobina (značajki) objekata
Određivanje mjere sličnosti.
Kriterij grupisanja podataka.
Algoritam grupisanja podataka.
Validacija rezultata
Interpretacija rezultata
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
18
9
Različita rješenja grupisanja
podataka
Prikaz dva načina grupisanja za dati skup tačaka
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
19
Metod udaljenosti
 Mjere udaljenosti (engl.
(engl distance measure)
pronalaze različitosti, odnosno sličnosti između
elemenata ili objekata, unutar skupa podataka.
 Posmatrano u širem kontekstu, mjera udaljenosti
je gradivni element većine metoda grupisanja
podataka.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
20
10
Mjere različitosti
 Minkowski metrika
1
 d
d p ( xi , x j )    xi , k  x j ,k
 K 1

p
p


 d
d 2 ( xi , x j )    xi , k  x j ,k
 K 1

2
2


 Euklidska udaljenost
 L1 metrika
1
dL1  xi , x j    xik  x jk
m
k 1
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
21
Mjere sličnosti
 Unutrašnji proizvod
l
su  x, y   xT y   xi y i
i 1
 Tanimoto distanca
sT  x, y  
Prepoznavanje uzoraka
xT y
x  y  xT y
2
2
Copyright: Lejla BanjanovićMehmedović
22
11
Algoritmi grupisanja podataka
 Inkrementalno (sekvencijalno)
grupisanje
i
j podataka
d
k
 Hijerarhijsko grupisanje podataka
 Iterativno grupisanje podataka bazirano
na kvadratu greške (k-means algoritam,
k-mediod algoritam, Fuzzy k-means
algoritam)
 Grupisanje po principu k-najbližih
susjeda (eng. k-neighboard)
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
23
K-means parcijalno
grupisanje
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
24
12
K-means parcijalno grupisanje
Grupisanje objekata sličnih karakteristika,
k i t ći zadati
koristeći
d ti skup
k
atributa
t ib t
 Dva kriterija:
 primjeri koji pripadaju
istoj grupi su međusobno slični
 primjeri koji pripadaju
određenoj grupi značajno se
razlikuju od primjera koji
pripadaju ostalim grupama
Centroid
Centroid
Centroid
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
25
K-means parcijalno grupisanje
 Glavna pretpostavka je da funkcija pripadnosti
grupii μij može
ž iimati
ti samo vrijednosti
ij d
ti 0 ili 1
(eng. hard clustering).
ij  0,1, j  1,...k
k

i 1
Prepoznavanje uzoraka
ij
1
Copyright: Lejla BanjanovićMehmedović
26
13
K-means parcijalno grupisanje
 K-means grupisanje predstavlja dijeljenje osnovne
populacije u K klastera
C1, C2 ,..., Ck 
 Svaki klaster ima nk uzoraka i vrijedi
n
k
 N , k  1,...K
 Srednja vrijednost u algoritmu odnosi se na "prosječnu
lokaciju“, tj. srednja vrijednost Mk klastera Ck
d f š se kao
definiše
k
centroid
d klastera
kl
M
Prepoznavanje uzoraka
k
 1 / n k
nk

i 1
x ik
Copyright: Lejla BanjanovićMehmedović
27
K-means parcijalno grupisanje
 Kvadratna greška klastera Ck je suma
kvadratnih distanci izmedju svakog uzorka u
klasteru i njegovog centroida (varijacija
2
unutar klastera): 2 n
ek    xik  M k 
k
i 1
p
kvadratna g
greška cijelog
j gp
prostora
 Ukupna
koji sadrži svih K klastera je
nk
E   ek2
2
k
Prepoznavanje uzoraka
i 1
Copyright: Lejla BanjanovićMehmedović
28
14
Algoritam K-means parcijalnog
grupisanja
1. Izabrati proizvoljno k <N grupa
2. Odrediti središte za svaku od k grupa
3. Ponavljati:
 pridružiti pomoću funkcije udaljenosti sve elemente
populacije njihovim najbližim grupama (proračun se
vrši na osnovu centralnih vrijednosti)
 izračunati novu vrijednost središta grupe za svaku
grupu pojedinačno kao prosječnu vrijednost objekata
sadržanih unutar svake grupe
 ponavljati sve dok se mijenjaju vrijednosti središta
grupe (stabilnost klasterske pripadnosti, tj. kada nema
prebacivanja bilo kojeg uzorka iz jednog klastera u drugi,
a što uzrokuje umanjenje ukupne kvadratne greške).
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
29
K-means parcijalno grupisanje
 grupisanje svakom slogu dodjeljuje vrijednost pripadnosti
kl t
klasteru,
tte opcionalno
i
l
pridružuje
id ž j vrijednost
ij d
t udaljenosti
d lj
ti od
d
centra klastera.
 Vrijednosti atributa moraju biti numeričke!
Centri rezultujućih grupa sa pripadajućim objektima
korištenjem k – means algoritma
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
30
15
K-means parcijalno grupisanje
 Ekvivalentan algoritmu u domenu neuralnih
mrežaž Kohenenova
K h
mreže
ž
 Popularnost uslijed:
 Vremenska kompleksnost: O(nkl), algoritam u
linearnoj ovisnosti o veličini seta podataka
 Prostorna kompleksnost: O(k+n), svi podaci u
glavnoj memoriji => pristup brz i algoritam
efikasan
 Neovisnost o redu prezentacije uzoraka
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
31
K-means parcijalno grupisanje
Jednostavan za implementaciju
Kompleksnost i vrijeme nije
problematično
Neizvjesnost sa:
 podešavanjem broja klastera
 stop-kriterijumom
stop kriterijumom => može konvergirati
lok. minimumu, uslijed lošeg izbora
inicijalne particije
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
32
16
K-means parcijalno grupisanje
Senzitivan na šum i izuzetke!!!
Preporuka: K-mediods:
 umjesto mean-a, koristi najčešće locirani
centralni objekt u klasteru.
 nije osjetljiv na šum i izuzetke.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
33
Fuzzy grupisanje
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
34
17
Fuzzy k - means algoritam
 Fuzzy k - means algoritam je dizajniran tako
da proizvede grupe,
grupe gdje je za svaki objekat
proračunata mjera pripadnosti pojedinoj grupi.
 Na početku ovog algoritma pretpostavljamo
oblik i broj grupa.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
35
Fuzzy k - means algoritam
 Neka je X  x1 ,..., x N skup od N vektora, koji
predstavljaju podatke.
 Fuzzy clustering od X u c clustera se sastoji od
1 ,..., c , pri čemu vrijedi
funkcija
i : X   0,1
  (x)  1
i
i
za svako x  X . Ove funkcije se nazivaju funkcijama
pripadnosti i imaju vrijednost između 0 i 1.
 Fc-M algoritam je dizajniran tako da proizvede fuzzy
clustere na isti način kao što se p
podrazumijeva
j
da kmeans proizvede tzv. ''hard'' clustere, preko minimizacije
funkcije cilja:

m
 2  ik  xk   i  0
 i
k
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
36
18
Fuzzy k - means algoritam
 i predstavlja vrijednost i-te funkcije
pripadnosti u k-toj
k toj tački podataka .
 v1 ,..., v c vektori predstavljaju centre
clustera.
 Da bi se minimizirala funkcija cilja, centri
clustera i funkcije pripadnosti su dizajnirane
tako da se najveća pripadnost javlja u
tačkama blizu odgovarajućih centara
clustera.
 m se naziva eksponencijalna težina i koristi
se da priguši šum u podacima.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
37
Fuzzy k - means algoritam
• Algoritam radi minimizaciju funkcije cilja
koja je postignuta na sljedeći način:
v i    ik  xk
m
• Centri klastera
k
• Funkcije pripadnosti
ik 
Copyright: Lejla BanjanovićMehmedović
m
ik
k
1/ x
k
 1/ x
j
Prepoznavanje uzoraka
 
 i
k
2
 j

1/  m 1 
2

1/  m 1 
38
19
Fuzzy k - means algoritam
1.
Slučajno se bira k centara
clustera
Izračuna
č
se Euklidova distancu
izmedju
centara
clustera
i
svakog vektora
Uzima se da m u formuli ima
vrijednost 2
Izračuna se vrijednost funkcije
pripadnosti
Dodijele
se
vektori
onom
clusteru
za
koji
funkcija
pripadnosti
ima
najveću
vrijednost
Ponovo
se
računaju
centri
klastera i algoritam ponavlja
iterativno sa korakom 2 sve dok
stop-kriterij ne bude ispunjen
2.
3.
4.
5.
6.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
39
Primjer
1.5
Tip
Standardizirani
podatak o cijeni
Audi
BMW
Corvette
Ford
Honda
Mazda
Mercedes
Nissan
Porcshe
Toyota
VW
Volvo
0,866
0,496
1,235
-0,706
-0,429
0,126
1,051
-0,429
3,454
-0,059
-0,706
0,219
Standandizirani
podatak o dužini
kočionog puta
0,208
-0,602
-1,811
-1,542
0,410
0,679
0,006
0,073
-2,215
1,218
-0,128
0,612
1
0.5
0
-0.5
-1
-1.5
-2
-2.5
-1
Vrijednosti testnih parametara
grupisanih po tipu vozila
Primjena K-means algoritma za k=3
grupa i matricu podataka X
Prepoznavanje uzoraka
-0.5
0
Copyright: Lejla BanjanovićMehmedović
0.5
1
1.5
2
2.5
3
3.5
40
20
Primjer
1.5
Tip
Standardizirani
podatak o cijeni
Audi
BMW
Corvette
Ford
Honda
Mazda
Mercedes
Nissan
Porcshe
Toyota
VW
Volvo
0,866
0,496
1,235
-0,706
-0,429
0,126
1,051
-0,429
3,454
-0,059
-0,706
0,219
Standandizirani
podatak o dužini
kočionog puta
0,208
-0,602
-1,811
-1,542
0,410
0,679
0,006
0,073
-2,215
1,218
-0,128
0,612
1
0.5
0
-0.5
-1
-1.5
-2
-2.5
-1
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
Vrijednosti testnih parametara
grupisanih po tipu vozila
Primjena FKM algoritma za k=3 grupa
i matricu podataka X
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
41
Primjer primjene k-means, kmediods i fuzzy-k-means algoritma
 Mapa okruženja mobilnog robota korištena kao ulaz
za grupisanje
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
42
21
Primjer primjene k-means, kmediods i fuzzy-k-means algoritma
 Rezultati primjene k - means algoritma na robotsku
mapu, 6 iteracija
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
43
Primjer primjene k-means, kmediods i fuzzy-k-means algoritma
 Rezultati primjene fuzzy k - means algoritma na
robotsku mapu, 65 iteracija
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
44
22
Primjena fuzzy K meansgrupisanja
 Automatizacija kuća i zgrada
 Korištenjem uzoraka omogućava se
unapređenje sistema upravljanja sa
osobenostima predikcije.
 Uzorci predstavljaju zauzetost prostora
ukućanima u predhodnih par godina u cilju
automatske kontrole temperature
 Metode bazirane na Fuzzy C-means i eXclusive
Self-Organizing Maps daju najbolje perfomase
u upravljanju.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
45
Zaključak klaster analize
 Algoritmi grupisanja se razlikuju u
mnogim aspektima:




brzina učenja,
količina podataka za treniranje,
brzina klasifikacije,
robusnost,, itd.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
46
23
Zaključak klaster analize
K-means metoda je jednostavna, nije vremenski
zahtjevna i nezavnisna je od rasporeda uzoraka.
uzoraka
Negativne strane se odnose na činjenicu da sama
selekcija broja klastera utiče na rezultat.
Kao alternativna metoda preporučuje K-mediods, koja
umjesto mean-a, koristi najčešće locirani centar objekt
u klasteru i nije osjetljiv na šum.
Fuzzy K-means grupisanje pri istom ulaznom setu
podataka vrši bolje grupisanje od K-means algoritma.
Potrebno je više vremena za FCM grupisanje nego za
K-means grupisanje istog seta podataka.
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
47
Zaključak klaster analize
Nema najboljeg
j
j g algoritma
g
g
grupisanja
p
j p
podataka.
 Preporuka: isprobati više algoritama na datom
skupu podataka!!!
Prepoznavanje uzoraka
Copyright: Lejla BanjanovićMehmedović
48
24
Download

PU 2 Metode grupisanja - Vanr.prof.dr. Lejla Banjanović