28.05.2014
MEH535 Örüntü Tanıma
7. Kümeleme (Clustering)
Doç.Dr. M. Kemal GÜLLÜ
Elektronik ve Haberleşme Mühendisliği Bölümü
web: http://akademikpersonel.kocaeli.edu.tr/kemalg/
E-posta: [email protected]
Kümeleme
• Veride etiket bilgisi yok
• Denetimsiz öğrenme (unsupervised
learning)
• Neden gereklidir?
– Büyük veri kümelerini etiketleme maliyeti
– Sınıf etiketleri bilinmiyor olabilir (örn: uydu
görüntüsü)
– Büyük veri kümeleri az sayıdaki prototip
kümesi ile sıkıştırılabilir
2
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
1
28.05.2014
Kümeleme
• Denetimsiz öğrenme:
– Yarı parametrik
• Sınıf içi farklılıkları gruplama
• Optik karakter tanımada farklı “1” yazım şekilleri
• Ses tanımada aynı kelimenin farklı telaffuzları
– Parametrik olmayan (sonraki konu)
3
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Kümeleme
• Karışım Yoğunlukları (Mixture Densities):
k
p  x    p  x|Gi  P Gi 
i 1
Gi the bileşen/grup/küme,
P ( Gi ) karışım oranları (önseller),
p ( x | Gi) bileşen yoğunlukları
• Gauss karışımı p(x|Gi) ~ N ( μi , ∑i )
parametreler: Φ = {P ( Gi ), μi , ∑i }ki=1
etiketsiz örnek X={xt}t (denetimsiz öğrenme)
4
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
2
28.05.2014
Sınıf-Küme
•
•
Denetimli: X = { xt ,rt }t
Sınıflar Ci i=1,...,K
•
•
k
p  x    p  x|Ci  P Ci 
p  x    p  x|Gi  P Gi 
p ( x | Ci) ~ N ( μi , ∑i )
p ( x | Gi) ~ N ( μi , ∑i )
K
i 1
i 1
•
•
Φ = {P (Ci ), μi , ∑
K
i } i=1

Pˆ  Ci   t
N
rit
 r x

t
Si
Denetimsiz: X = { xt }t
Kümeler Gi i=1,...,k
t i
rx
r
t
mi 
Φ = {P ( Gi ), μi , ∑i }ki=1
t
t i
Etiketler, r ti ?
t
t i
t
 mi  xt  mi 
T
r
t
t i
5
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
K-Ortalama Kümeleme
• Veriyi en iyi betimleyen k adet referans vektör bul
(prototip/kod kitabı vektörleri/kod kelimeleri)
• Referans vektörler, mj, j =1,...,k
• En yakın (en benzer) referansı kullan:
xt  mi  min xt  m j
j
• Geriçatma hatası


E mi i 1 X   t  i bit xt  mi
k
1 if xt  mi  min xt  m j
j
b 
0 otherwise
t
i
6
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
3
28.05.2014
K-Ortalama Kümeleme
t

xt  m j
1 if x  mi  min
j
b 

0 aksi halde
t
i
7
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
K-Ortalama Kümeleme
• Algoritma:
8
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
4
28.05.2014
K-Ortalama Kümeleme
• Örnek:
9
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
ISODATA
• Iterative Self-Organizing Data Analysis:
– K-ortalama algoritmasının genişletilmiş şeklidir
– Küme sayısının otomatik seçilmesine yöneliktir
– Kullanıcı tanımlı parametreleri:
•
•
•
•
•
Küme başına düşen en az örnek sayısı
Yaklaşık istenen küme sayısı
Kümeyi parçalama için gerekli saçılma parametresi
Küme birleştirme için gerekli uzaklığı
Birleştirebilecek küme sayısının üst sınırı
– Algoritma:
1.
2.
3.
4.
K-ortalama kümeleme gerçekleştir
Birbirine benzemeyen örnekler içeren kümeleri böl
Birbirine yakın farklı kümeleri birleştir
1. adıma git
10
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
5
28.05.2014
Beklendik En Büyükleme (EM)
• Expectation Maximization (EM)
• Karışım modeli ile Log olabilirlik
L  |X   log p  xt | 
t
  t log  p  xt |Gi  P Gi 
k
i 1
• Gizli değişkenler: z,(bilinmiyor)
• Eksiksiz olabilirlik: Lc(Φ |X,Z), x ve z biliniyor
• Eksik olabilirlik: L(Φ |X), yalnızca x biliniyor
11
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Beklendik En Büyükleme (EM)
• E ve M adımları:
– Aşağıdaki adımları tekrarla:
1. E-adımı: Mevcut Φ ve verilen X kullanılarak z’yi
kestir
2. M-adımı: Bulunan z ve verilen X’i kullanarak yeni
Φ’ yı bul
E-step:Q  |l   E  LC  |X, Z  |X, l 
M-step:l 1  arg max Q  |l 

– Q’daki artış, eksik olabilirliğin artması
anlamındadır (durma ölçütü: değişim yok!)
L  l 1|X   L  l |X 
12
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
6
28.05.2014
Beklendik En Büyükleme (EM)
• Gauss Karışımlarında EM:
• zti = 1 Eğer xt Gi’ye ait ise zti = 1 kararı ver, aksi halde
0 kararı (denetimli öğrenmedeki r ti etiketi)
• p(x|Gi)~N(μi,∑i) kabulünü yap
• E-adımı:
p  xt |Gi ,  l  P Gi 
E  z X ,   
t
i
l
 p  x |G ,   P G 
t
l
j
j
j
 P Gi |xt ,  l   hit
• M-adımı:
P Gi  
Sli 1 
h
t
t
i
mil 1 
N
 h x
t
t
i
 hx
h
t
i
t
t
t
m
l 1
i
 x
h
t
t
m
t
t
i

Kestirilen etiketler
(bilinmeyen) üzerinden
parametre kestirimi yap
l 1 T
i
t
i
13
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Beklendik En Büyükleme (EM)
• Örnek:
14
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
7
28.05.2014
K-Ortalama Kümeleme
• Örnek:
15
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Sıradüzensel Kümeleme
• K-ortalama, ISODATA gibi yaklaşımlar
→ keskin küme sınırları
• Kümeler altında alt kümelerin bulunduğu ağaç
yapısına sahip sıradüzensel (hierarchical) gösterim
– Tercih sebebi (örn; biyolojik sınıflandırma)
• Sıradüzensel Kümeleme.
– Toplamacı/Birleştirici (Agglomerative)
• Her biri 1 örneğe sahip N küme ile başla, her yinelemede 2 en
yakın kümeyi birleştir, tek küme kalana kadar devam et (single link
clustering)
– Bölücü (Divisive)
• Tek kümeden başlayarak bölme ile N tek ton küme elde edene
kadar devam et
– Hesapsal yük: Birleştirici yaklaşım << Bölücü yaklaşım
16
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
8
28.05.2014
Sıradüzensel Kümeleme
• Birleştirici Yaklaşım:
– Birbirine en yakın iki küme bulunurken kullanılabilecek
uzaklık ölçütleri:
Single-link
Complete-link
17
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Sıradüzensel Kümeleme
• Gösterim → Ağaç gösterimi (dendrogram)
– Kümelerin yapısını gösteren ikili ağaç yapısı
– Kümeler arasındaki benzerlik (düşey eksende)
Dendrogram
18
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
9
28.05.2014
Sıradüzensel Kümeleme
19
Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
10
Download

Sunu71.28 MB