Kümeleme
(Clustering)
Benzelik Ölçüsü (Measure of
Similarity),
Hiyerarşik Kümeleme
(Hierarchical Clustering),
K-means Kümeleme
Alper VAHAPLAR
Veri Madenciliğine Giriş
2
1
•
Nesneleri benzer özelliktekiler bir arada olacak şekilde gruplandırma
işlemi
•
Küme : Aynı küme içindeki veri nesnelerinin birbirine benzediği, diğer
kümedeki veri nesnelerinden farklılık gösterdiği veri grupları.
•
•
Günlük hayatta:
o
Hayvanları ve bitkileri birbirinden ayırmak,
o
Erkek ve Bayanları birbirinden ayırmak,
o
Farklı araç gruplarını belirlemek (araba – otobüs)
Amaçlar:
o
Veri içindeki doğal grupları belirlemek,
o
Homojen sınıflar oluşturmak,
o
Veri indirgeme (Data Reduction),
o
Sapan değer tespiti (Outlier Detection)
Alper VAHAPLAR
•
•
•
•
Veri Madenciliğine Giriş
3
Veri Madenciliğine Giriş
4
Başlıca Konular:
Benzerlik nasıl ölçülür?
Kaç küme olsun?
Doğru küme???
Alper VAHAPLAR
2
•
‘Benzerliğin’ Ölçülmesi
yoksa «benzemezliğin» ölçülmesi mi?
•
•
•
Uzaklık ölçüsü (distance measure) [d(x,y)]
İki nesne arasındaki farklılığın belirlenmesi
d(x,y) özellikleri:
1.
d(x, y)  0 tüm x ve y değerleri için
2.
d(x, y) = 0 sadece x = y ise (Positive definiteness)
3.
d(x, y) = d(y, x) tüm x ve y değerleri için. (Symmetry)
4.
d(x, z)  d(x, y) + d(y, z) tüm x, y ve z değerleri için.
(Triangle Inequality)
Alper VAHAPLAR
•
•
5
Uzaklık Fonksiyonu (Distance Function)
Öklid Uzaklığı (Euclidean Distance)
d Euc ( x, y ) 
•
Veri Madenciliğine Giriş
 (x
i
i
 yi ) 2
Manhattan (City Block) Uzaklığı
d Man ( x, y) i xi  yi
•
Minkowski Uzaklığı
d Min ( x, y ) 
Alper VAHAPLAR

i
xi  yi 
Veri Madenciliğine Giriş
6
3
Alper VAHAPLAR
•
•
Veri Madenciliğine Giriş
7
Veri Madenciliğine Giriş
8
Uzaklık Ölçüsü
Örnek:
Alper VAHAPLAR
4
3
point
p1
p2
p3
p4
p1
2
p3
p4
1
p2
0
0
1
2
3
p1
p1
p2
p3
p4
4
p2
2.828
0
1.414
3.162
0
2.828
3.162
5.099
5
y
2
0
1
1
6
p3
3.162
1.414
0
2
p4
5.099
3.162
2
0
p1
0
4
4
6
p1
p2
p3
p4
Euclidean Distance Matrix
Alper VAHAPLAR
x
0
2
3
5
p2
4
0
2
4
p3
4
2
0
2
p4
6
4
2
0
Manhattan Distance Matrix
Veri Madenciliğine Giriş
9
3
point
p1
p2
p3
p4
p1
2
p3
p4
1
p2
0
0
1
2
p1
p1
p2
p3
p4
0
2.828
3.162
5.099
3
4
p2
2.828
0
1.414
3.162
5
y
2
0
1
1
6
p3
3.162
1.414
0
2
p4
5.099
3.162
2
0
Euclidean Distance Matrix
Alper VAHAPLAR
x
0
2
3
5
p1
0
4
4
6
p1
p2
p3
p4
p2
4
0
2
4
p3
4
2
0
2
p4
6
4
2
0
Manhattan Distance Matrix
Veri Madenciliğine Giriş
10
5
•
Uzaklık Ölçüsündeki Problem
o
Farklı aralıktaki veriler (Different ranges in data)
• Normalization (min-max, Z-score, etc)
o
Kategorik değişkenler (Categorical variables)
Alper VAHAPLAR
•
Veri Madenciliğine Giriş
11
Ali – Ayşe, Ali – Veli ve Ayşe – Veli arasındaki uzaklıkları bulunuz.
Adı
Yaşı
Kilosu
Gözrengi
Ali
22
65
Siyah
Ayşe
19
52
Ela
Veli
23
60
Siyah
Değişken
Yaşı
Kilosu
Min
18
50
Max
30
85
Alper VAHAPLAR
Veri Madenciliğine Giriş
12
6
•
Ali – Ayşe, Ali – Veli ve Ayşe – Veli arasındaki uzaklıkları bulunuz.
Adı
Yaşı
Kilosu
Gözrengi
Ali
22 (0,33)
65 (0,43)
Siyah
Ayşe
19 (0,08)
52 (0,06)
Ela
Veli
23 (0,42)
60 (0,29)
Siyah
Değişken
Yaşı
Kilosu
Min
18
50
Max
30
85
Alper VAHAPLAR
•
•
•
d
Ali
Ayşe
Veli
Ali
0
1.096
0.165
Ayşe
1.096
0
1.079
0.165
1.079
0
Veli
Veri Madenciliğine Giriş
13
Kategorik Değişkenler için Uzaklık Ölçüsü
Binary Data (0/1 - Var/Yok – Yes/No)
Jackard’s Distance
Object j
Object i
1
0
sum
1
a
b a b
0
c
d cd
sum a  c b  d
p
d (i, j) 
Alper VAHAPLAR
Veri Madenciliğine Giriş
bc
a bc
14
7
•
Elma ile Muz arasındaki Jackard’s uzaklığnı bulunuz.
Meyve
Yuvarlaklık
Tatlı
Ekşi
Yumuşak
Elma
Evet
Evet
Evet
Hayır
Muz
Hayır
Evet
Hayır
Evet
bc
a bc
d (i, j) 
(a = 1, b = 2, c = 1, d= 0)
(2+1) / (1 + 2 + 1) = 3/4 = 0.75
Muz
Elma
Alper VAHAPLAR
•
1
0
sum
1
0
a
b
c
d
ac bd
sum
a b
cd
p
Veri Madenciliğine Giriş
15
Benzer hastalığı olanlar kimler?
Name
Jack
Mary
Jim
Fever
Y
Y
Y
Cough
N
N
P
Test-1
P
P
N
Test-2
N
N
N
0 1
 0.33
2  0 1
d(Jack,Jim) = 1  1  0.67
111
1 2
 0.75
d(Jim,Mary) =
11 2
Test-3
N
P
N
Test-4
N
N
N
d (i, j) 
d(Jack,Mary)=
bc
a bc
Object j
Object i
1
0
sum
1
a
c
ac
0
b
d
bd
sum
a b
cd
p
Sonuç: Jack ve Mary daha benzer.
Alper VAHAPLAR
Veri Madenciliğine Giriş
16
8
•
Hiyerarşik (Hierarchical Methods)
AGNES, DIANA, BIRCH, CURE, CHAMELEON, ...
o
•
Bölümleyici (Partitioning Methods)
o
•
Yoğunluk Temelli (Density-Based Methods)
DBSCAN, OPTICS, DENCLUE, ...
o
•
Izgara Temelli (Grid-Based )
STING, WaveCluster, CLIQUE ...
o
•
K-Means, K-Medoids, PAM, CLARA, CLARANS, ...
Model Temelli (Model-Based)
COBWEB, CLASSIT, SOM (Self-Organizing Feature Maps) ...
o
Alper VAHAPLAR
•
•
•
Veri Madenciliğine Giriş
17
Ağaç yapısına benzer kümeleme (dendrogram)
Birleştirici (Agglomerative) Yöntem
o
Başlangıçta her nesne tek başına bir kümedir.
o
En yakın iki küme birleştirilir,
o
Tüm veriler aynı kümeye girinceye kadar devam eder.
o
Sonunda tek bir küme oluşur.
Bölücü (Divisive) Yöntem
o
Başlangıçta tüm veriler aynı kümede kabul edilir.
o
En benzemeyen gruplar birbirlerinden ayrılır,
o
Sonunda her kayıt ayrı bir küme oluşturur.
Alper VAHAPLAR
Veri Madenciliğine Giriş
18
9
•
•
Kümeler arası uzaklığın ölçülmesi
Tekli Bağlantı (Single linkage),
o
En yakın komşu yaklaşımı
o
İki küme arasındaki elemanlar arasında en yakın olanlarının uzaklığını temel
alır.
•
Tam Bağlantı (Complete linkage),
o
En uzak komşu yaklaşımı,
o
İki küme arasındaki elemanlar arasında en uzak olanlarının uzaklığını temel
alır.
o
•
based on the maximum distance between any record in two clusters.
Ortalama Bağlantı (Average linkage),
o
Bir kümedeki tüm elemanların diğer kümedeki tüm elemanlara olan ortalama
uzaklığını temel alır.
Alper VAHAPLAR
Veri Madenciliğine Giriş
•
Single link: iki kümedeki en yakın elemanlar,
•
Complete link: iki kümedeki en uzak elemanlar,
•
Average: uzaklık ortalamaları.
Alper VAHAPLAR
Veri Madenciliğine Giriş
19
20
10
Veri Seti: 2,5,9,15,16,18,25,33,33,45
Alper VAHAPLAR
•
Veri Madenciliğine Giriş
21
Dataset: 2,5,9,15,16,18,25,33,33,45
Alper VAHAPLAR
Veri Madenciliğine Giriş
22
11
•
Dataset: 2,5,9,15,16,18,25,33,33,45
The average dis tan ce 
Alper VAHAPLAR
5
2
0.4
4
1
5
0.15
6
5
0.2
3
0.1
3
6
1
4
4
0
3
6
2
5
4
0.3
0.25
2
0.05
4
0.35
2
3
Acount * Bcount
23
0.2
1
2
xA yB
Veri Madenciliğine Giriş
5
1
3
 d ( x, y)
0.15
0.1
0.05
0
1
Single Link
3
6
4
1
2
5
Complete Link
4
5
0.25
1
2
5
0.2
2
0.15
3
6
1
4
0.1
0.05
3
0
3
6
4
1
2
5
Average Link
Alper VAHAPLAR
Veri Madenciliğine Giriş
24
12
•
•
•
Single Linkage
o
Eliptik olmayan şekilleri bulabilir
o
Gürültü ve sapan değerlere karşı hassastır
Complete Linkage
o
Gürültü ve sapan değerlere daha az duyarlıdır
o
Büyük kümeleri bölme eğilimindedir, dairesel kümeler oluşturur
Average Linkage
o
Gürültü ve sapan değerlere daha az duyarlıdır
o
Dairesel kümeler oluşturur (complete linkage’a benzer)
Alper VAHAPLAR
•
•
Veri Madenciliğine Giriş
25
Avantajları
o
Küme sayısının önceden bilinmesi gerekmez.
o
Uygulaması kolaydır.
o
Hızlı ve anlaşılır (az karmaşık) algoritmaya sahiptir.
Dezavantajları
o
Ağacın nereden kesilmesi gerekliliği
o
Gürültü ve sapan değerlere hassasiyet
o
Farklı büyüklük ve şekillerdeki kümeleri bulmada zorluk
o
Büyük kümeleri bölme eğilimi
Alper VAHAPLAR
Veri Madenciliğine Giriş
26
13
•
n nesneli D veritabanını uzaklık kareleri toplamı en küçük olan k
adet kümeye ayırmayı hedefler.
•
Verilen k küme sayısına göre seçilen bölümleme yöntemini (ör: SSE
– hata kareler toplamı) optimize etmeye çalışır.
Alper VAHAPLAR
•
•
Veri Madenciliğine Giriş
27
Küme içi değişim
Within Cluster Variation (WCV)
SSE   ik1 pCi d ( p  ci ) 2
•
•
Kümeler arası değişim
Between Cluster Variation (BCV)
BCV = d(c1, c2)
•
Amaç: BCV/WCV oranını maksimize etmek
BCV d (c1 , c2 )

WCV
SSE
Alper VAHAPLAR
Veri Madenciliğine Giriş
28
14
•
k-means Clustering
•
•
•
•
n adet nesneyi k tane kümeye ayırmak, k < n
Adım 1: k değerini belirle,
Adım 2: Rasgele k tane veriyi başlangıç küme merkezi olarak ata,
Adım 3: Her veri için en yakın küme merkezini bul ve veriyi o
kümeye ata,
•
Adım 4: Oluşan her kümenin yeni küme merkezini hesapla
(ortalama),
•
Adım 5: Adım 3-5 i şu koşullar sağlanıncaya kadar tekrar et:
o
Küme merkezleri yer değiştirmeyince
o
Hiçbir veri küme değiştirmeyince
o
Hedeflenen SSE elde edilince
Alper VAHAPLAR
Veri Madenciliğine Giriş
Adım 1: k = 2 olsun (iki kümeye ayıralım)
 Adım 2: Rasgele iki nokta, küme merkezleri olsun
Alper VAHAPLAR
Veri Madenciliğine Giriş
c1=(1,1) ve c2=(2,1)
29

30
15

Adım 3: (ilk tur) Her kayıt için en yakın küme merkezini belirle.
(c1=(1,1) ve c2=(2,1))
c1
c2
SSE   ik1 pCi d ( p  ci ) 2
SSE   ik1 pCi d ( p  ci ) 2  2 2  2.24 2  2.83 2  3.612  12  2.24 2  0 2  0 2  36 .0762
Alper VAHAPLAR
Veri Madenciliğine Giriş
31
BCV d (c1  c2 ) 1


 0,0278
WCV
SSE
36

Her turda bu oranın artmasını bekliyoruz.

Adım 4: Her küme için yeni küme merkezi hesapla (k-means)
 1  1  1   3  2  1 
new c1  
, 
  (1,2)
 3   3 
 3  4  5  4  2   3  3  3  2  1 
new c2  
, 
  (3.6,2.4)
5
5



Alper VAHAPLAR
Veri Madenciliğine Giriş
32
16

Adım 5: Adım 3 ve 4’ü koşullara sağlanana kadar tekrar et.

Adım 3 (ikinci tur) : küme merkezlerini güncelle [c1=(1,2) ve
c2=(3.6,2.4)]. Her verinin bu yeni küme merkezlerine
uzaklıklarını bul.
Alper VAHAPLAR

Veri Madenciliğine Giriş
33
Adım 3 (ikinci tur) : küme merkezlerini güncelle [c1=(1,2) ve
c2=(3.6,2.4)]. Her verinin bu yeni küme merkezlerine
uzaklıklarını bul.
c1
c2
C1
SSE   ik1 pCi d ( p  ci ) 2  12  0.85 2  0.72 2  1.52 2  0 2  0.57 2  12  1.412  7,88
Alper VAHAPLAR
Veri Madenciliğine Giriş
34
17
BCV d (c1  c2 ) 2.63


 0,3338
WCV
SSE
7.88

Adım 4 (ikinci tur) : Her küme için yeni küme merkezi hesapla.
 1  1  1  2   3  2  1  1 
new c1  
, 
  (1.25,1.75)
4
4



 3  4  5  4   3  3  3  2 
new c2  
, 
  (4,2.75)
4
4




Adım 5: Adım 3 ve 4’ü koşullara sağlanana kadar tekrar et.
Alper VAHAPLAR

Veri Madenciliğine Giriş
35
Adım 3 (üçüncü tur) : küme merkezlerini güncelle
[c1=(1.25,1.75) ve c2=(4,2.75)]. Her verinin bu yeni küme
merkezlerine uzaklıklarını bul.
c1
c2
C1
SSE   ik1 pCi d ( p  ci ) 2  6,25
Alper VAHAPLAR
BCV d (c1  c2 ) 2.93


 0,4688
WCV
SSE
6,25
Veri Madenciliğine Giriş
36
18

Adım 4 (üçüncü tur): Her küme için yeni küme merkezi hesapla.


Hiçbir veri küme değiştirmediği için küme merkezleri sabit
kalır.
Adım 5: Adım 3 ve 4’ü koşullara sağlanana kadar tekrar et.

Küme merkezleri yer değiştirmediği için algoritma sonlanır.
Alper VAHAPLAR
Veri Madenciliğine Giriş
37
k1
Y
k=3,
Rasgele 3 nokta
seç
k2
k3
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
38
19
k1
Y
Her noktayı
en yakın kümeye
ata
k2
k3
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
39
k1
k1
Y
Yeni küme
merkezlerini
belirle
k2
k3
k2
k3
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
40
20
Verileri yeni
kümelerine ata
k1
Y
Hangi noktalar
küme
değiştirdi?
k3
k2
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
41
k1
Y
Küme
değiştiren
noktalar
k3
k2
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
42
21
k1
Y
Yeni küme
merkezlerini
hesapla
k3
k2
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
43
k1
Y
Yeni küme
merkezlerini
belirle
k2
k3
X
Alper VAHAPLAR
Veri Madenciliğine Giriş
44
22
•
Güçlü Yanları (Strength)
o
o
o
•
Etkin ve Hızlı bir algoritma: O(tkn)
Anlaşılması kolay
Genellikle yerel optimumda sonlanır.
Zayıf Yanları (Weakness)
o
o
o
o
o
o
Sadece ortalama anlamlı iken uygulanabilir. Kategorik verilere
uygulanamaz.
Küme sayısı k’nın önceden bilinmesi gerekir.
Gürültü ve sapan değerlerden çok etkilenir.
Konveks olmayan şekilleri bulamaz.
Başlangıçta seçilen küme merkezlerine göre kümeler farklılık gösterebilir
Başlangıçta seçilen küme merkezlerine göre adım sayısı değişebilir.
Alper VAHAPLAR
Veri Madenciliğine Giriş
45
Alper VAHAPLAR
Veri Madenciliğine Giriş
46
23
Alper VAHAPLAR
•
•
•
Veri Madenciliğine Giriş
47
Alternatifleri
K-medians – ortalama yerine her kümenin ortancasının kullanılması
o
Mean of 1, 3, 5, 7, 1009 is 205
o
Median of 1, 3, 5, 7, 1009 is 5
K-modes – Kategorik verileri kümelemek için ortalama yerine
kümenin mod değerinin kullanılması
•
K-medoids
o
Kümedeki diğer elemanlara en benzer nesnenin küme merkezi olarak kabul
edildiği kümeleme
o
•
PAM (Partitioning Around Medoids) Algorithm
Fuzzy c-means
o
Verilerin birden çok kümeye üyeliklerinin söz konusu olduğu bulanık küme
mantığı ile k-means kümeleme
Alper VAHAPLAR
Veri Madenciliğine Giriş
48
24
•
•
Yoğunluğu baz alarak yapılan kümeleme (veriler arasındaki uzaklık).
Temel özellikleri:
•
o
Farklı şekillerdeki kümeleri tespit edebilme
o
Gürültünün belirlenebilmesi
o
Tek iterasyon
o
Yoğunluk parametrelerinin bilinmesi gerekli
Several interesting studies:
o
DBSCAN: Ester, et al. (KDD’96)
o
OPTICS: Ankerst, et al (SIGMOD’99).
o
DENCLUE: Hinneburg & D. Keim (KDD’98)
Alper VAHAPLAR
•
Veri Madenciliğine Giriş
49
Density-Based Spatial Clustering of Applications with Noise.
Density = number of points within a specified radius (Eps)
• Belirli bir uzaklıktaki komşu veri sayısı
o
A point is a core point if it has more than a specified
number of points (MinPts) within Eps
• Eps uzaklıkta belirli sayıda (MinPts) komşusu olan veri
noktası
o
A border point has fewer than MinPts within Eps, but is in
the neighborhood of a core point
o
Eps uzaklıkta MinPts’den az sayıda komşusu olan ancak bir core
point’in komşuluğunda olan veri noktası
•
o
A noise point is any point that is not a core point or a
border point.
•
Alper VAHAPLAR
Core point ya da Border point olmayan veriler (Gürültü)
Veri Madenciliğine Giriş
50
25
Alper VAHAPLAR
Veri Madenciliğine Giriş
Original Points
Alper VAHAPLAR
51
Point types: core,
border and noise
Veri Madenciliğine Giriş
Eps = 10, MinPts = 4
52
26
Original Points
Clusters
• Gürültüyü ve farklı şekillerdeki kümeleri tespit edebilir.
Alper VAHAPLAR
Veri Madenciliğine Giriş
53
(MinPts=4, Eps=9.75).
Original Points
• Farklı yoğunluklar
•Yükse boyutlu veriler
Alper VAHAPLAR
Veri Madenciliğine Giriş
54
(MinPts=4, Eps=9.92)
27
1
0.9
0.8
0.7
y
0.6
0.5
0.4
0.3
0.2
0.1
0
Alper VAHAPLAR
0
0.2
0.4
0.6
Veri Madenciliğine Giriş
x
0.8
1
55
Complete
Link
Alper VAHAPLAR
Veri Madenciliğine Giriş
56
28
K-means
Alper VAHAPLAR
Veri Madenciliğine Giriş
57
DBSCAN
Alper VAHAPLAR
Veri Madenciliğine Giriş
58
29
Alper VAHAPLAR
Veri Madenciliğine Giriş
59
◘ En basit yaklaşım, uzayı eşit hacimli dörtgenlere bölmek ve he
bölmeye düşen veri sayısına göre yoğunluk belirlemek
Alper VAHAPLAR
Veri Madenciliğine Giriş
60
30
İstatistiksel fonksiyonlar kullanarak verileri ifade eden modeller kurmaya
dayanır.
Alper VAHAPLAR
Veri Madenciliğine Giriş
61
Sınavdan
Sonra…
Sınıflandırma (Classification)
K-En yakın komşuluk
(K-nearest neighborhood)
Karar Ağaçları (Decision Trees)
Alper VAHAPLAR
Veri Madenciliğine Giriş
62
31
•
The Iris Plant data set.
o
http://194.27.66.123/datamining/iris.xls
• Attribute Information:
• 1. sepal length in cm
2. sepal width in cm
3. petal length in cm
4. petal width in cm
5. class:
-- Iris Setosa
-- Iris Versicolour
-- Iris Virginica
Alper VAHAPLAR
•
•
•
Veri Madenciliğine Giriş
63
Summarize the data set by the operations
o
Show in table,
o
Data Audit,
o
Summary Statistics,
o
Histograms,
o
Plot Diagram,
Add a new field
o
Sepal-width/sepal-length,
o
Binn this new field
Apply k-means to the data set,
Alper VAHAPLAR
Veri Madenciliğine Giriş
64
32
Download

Sunum