S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha
1
Agenda Clustering Requirement untuk clustering Tipe data dalam cluster analysis Interval-scale variable Binary variable Nominal variable Ordinal variable Ratio-scaled variable
Partitioning clustering Hierarchical clustering 2
Clustering Cluster : Kumpulan objek yang sejenis / berkarakter sama
dalam 1 cluster Kumpulan objek tidak sejenis/berbeda dalam cluster lainnya.
Cluster analysis Menemukan kemiripan antar data berdasarkan
karakteristik yang ditemukan pada data, kemudian mengelompokkan data objek yang mirip ke dalam cluster
Unsupervised learning: no predefined classes 3
Clustering Contoh penerapan umum : Bisnis : Menemukan grup customer dan target pemasaran. Biologi : menurunkan taksonomi tanaman dan hewan, mengkategorikan gen Web : mengklasifikasikan dokumen untuk information retrieval Dapat sebagai proses awal untuk algoritma lain seperti misalnya characterization atau classification
4
Quality: What Is Good Clustering? Metoda clustering yang baik menghasilkan high
quality clusters : high intra-class similarity low inter-class similarity
Kualitas hasil clustering bergantung pada ukuran
kemiripan yang dipakai dan implementasinya Kualitas clustering diukur juga dengan kemampuan
untuk menemukan hidden pattern
5
Struktur Data dalam Cluster Analysis Data matrix (object by variable structure) Dissimilarity matrix (object by object structure)
6
Data matrix Menyatakan n object,
misal orang, dengan p variable (= measurements atau attribute) mis. umur, tinggi, berat, gender, ras, dll. Strukturnya dapat dlm bentuk tabel relasional ataupun matriks n x p
x11 ... x i1 ... x n1
... x1f ... ... ...
xif
...
...
... xnf
... x1p ... ... ... xip ... ... ... xnp
7
Dissimilarity matrix Menyimpan sekumpulan
proximity yang tersedia untuk seluruh pasangan n object. Direpresentasikan dalam bentuk tabel nxn, dimana d(i,j) adalah difference atau dissimilarity antara object i dan j. Semakin dekat d(i,j) dengan 0, berarti object i dan j semakin dekat.
0
d(2,1)
0
d(3,1) d(3,2)
0
:
:
:
:
:
:
d(n,1) d(n,2)
...
...
0
8
Tipe data dalam Cluster Analysis Interval-scale variable Binary variable Nominal variable Ordinal variable Ratio-scaled variable Kombinasi tipe-tipe di atas.
9
Interval-scale variable Adalah pengukuran kontinyu untuk skala yang hampir linear. Mis. Berat & tinggi, koordinat lintang dan bujur (untuk meng-cluster rumah), dan temperatur udara. Perubahan satuan dapat mempengaruhi cluster analysis, mis. Dari meter inch Semakin kecil satuan ukurannya, range variable akan semakin besar, mengubah struktur clustering data perlu distandarkan 10
Interval-scale variable Menstandarkan data : data ukuran diubah ke variable yang tidak ada satuannya (unitless) dengan cara : 1. Menghitung mean absolute deviation, sf : sf= 1/n(|x1f-mf| + |x2f-mf| + …+|xnf-mf|) x1f , …, xnf : n pengukuran untuk variabel f. mf : nilai rata-rata variabel f. 2. Menghitung standardized-measurement/ z-score : xif – mf Zif = sf 11
Interval-scale variable Dissimilarity dalam interval-scale variable dihitung
berdasar jarak (distance) antara tiap pasang object. Beberapa pengukuran distance : Euclidean distance Manhattan distance Minkowski distance
12
Euclidean distance d(i,j) =
|xi1 – xj1|2 + |xi2 – xj2|2 + …+ |xip – xjp|2
i = (xi1,xi2,…,xip) j= (xj1,xj2,…,xjp) i dan j adalah dua p-dimensional data object
13
Manhattan/city block distance d(i,j) = |xi1 – xj1| + |xi2 – xj2| + …+ |xip – xjp|
i = (xi1,xi2,…,xip) j= (xj1,xj2,…,xjp) i dan j adalah dua p-dimensional data object
14
Minkowski distance Merupakan generalisasi Euclidean dan Manhattan
distance. d(i,j) = (|xi1 – xj1|q + |xi2 – xj2|q + …+ |xip – xjp|q)1/q
• q : integer positif. • Menyatakan Manhattan distance jika q = 1 • Menyatakan Euclidean distance jika q = 2 15
Weighted Euclidean distance Tiap variable dapat diberi bobot sesuai tingkat
kepentingannya. Euclidean distancenya dapat dihitung sbb : d(i,j) = w1|xi1 – xj1|2 + w2|xi2 – xj2|2 + …+ wp|xip – xjp|2
• Pembobotan juga dapat diaplikasikan pada Manhattan dan Minkowski distance 16
Binary variables Merupakan variabel yang memiliki 2 state, yaitu 0
dan 1. 0 = tidak ada, 1 = ada Misal, pada object pasien, terdapat variable perokok. 1 = pasien perokok, 0 = pasien bukan perokok. Binary variable jika diperlakukan seperti intervalscale variable hasil cluster salah.
17
Binary variable Menghitung dissimilarity :
object j
Dissimilarity matrix 1
0
jml
1
q
r
q+r
0
s
t
s+t
jml
q+s
r+t
p
untuk binary variables yang berbobot sama. object i
18
Binary variable Symmetric binary variable : Kedua state-nya bernilai dan berbobot sama. Misal, variable gender. invariant similarity : hasil tdk berubah variable dikodekan secara berbeda.
r+s d(i,j) = -----------q+r+s+t 19
Binary variable Asymmetric binary variable : Jika hasil state tidak sama tingkat kepentingannya. Mis. Hasil test penyakit, positif/negatif. Hanya diambil hasil
yang paling penting saja (biasanya yg terjarang) dan dikodekan sebagai 1 (ex. Positif HIV), sedang yg lain 0 (ex. Negatif HIV). Dengan 2 variable, 2 buah state 1 lebih penting dari 2 buah state 0, sehingga seringkali disebut monary (seperti hanya memiliki 1 state). noninvariant similarity. Menggunakan koefisien Jaccard, yaitu nilai t diabaikan.
r+s d(i,j) = -----------q+r+s 20
Binary variable name
gender
fever
cough
test-1
test-2
test-3
test-4
Jack
M
Y
N
P
N
N
N
Mary
F
Y
N
P
N
P
N
Jim
M
Y
Y
N
N
N
N
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
• Object-id : name • Symmetric attribute : gender • Assymetric : atribut lainnya – Y dan P 1, N 0 – Distance antarobject dihitung berdasar asymmetric variable. 21
Binary variable 0+1 d(jack,mary) = ------------ = 0.33 2+0+1 1+1 d(jack,jim) = ------------ = 0.67 1+1+1 1+2 d(jim,mary) = ------------ = 0.75 1+1+2
Distance jim dan mary paling besar, dalam kasus ini berarti penyakitnya paling tidak sama. Jack dan mary sebaliknya.
22
Nominal variables Adalah generalisasi binary variable dalam hal variable
ini dapat menampung lebih dari 2 state. Ex., variable warna_peta mempunyai 5 state merah, hijau, biru, kuning, hitam. State dinyatakan dalam huruf, simbol, atau integer 1,2,…,M. Integer hanya untuk penunjuk data, tidak menunjukkan urutan tertentu.
23
Nominal variable Menghitung dissimilarity untuk nominal variable :
p-m d(i,j) = -----------p • • • •
m adalah banyaknya i dan j yang state-nya sama. p adalah jumlah seluruh variable. Dapat dikodekan ke asymmetric binary variable. Ex. Object yang mempunyai warna kuning diset 1, sedangkan warna lainnya 0, dst untuk masing-masing warna. • Koefisien dissimilarity dihitung dengan cara yang sama dengan binary variable. 24
Ordinal variable Discrete ordinal variable : seperti nominal variable, hanya saja state M yang bernilai ordinal diurutkan dalam urutan yang mempunyai arti. Continuous ordinal variable : sekumpulan data yang kontinyu dari suatu skala yang tidak diketahui. Yang penting adalah urutannya, bukan bobot / pengaruh/tingkat kepentingan urutan tersebut. Misal, rangking emas, perak, perunggu. Urutannya lebih penting daripada nilai ukuran sesungguhnya. 25
Ordinal variable Nilai ordinal variable dapat dipetakan ke ranking. Jika terdapat ordinal variable f yang mempunyai Mf
state, state yang terurut menentukan ranking 1, …, Mf. Menghitung dissimilarity antar objectnya seperti pada interval-scaled variable.
26
Ordinal variable 1.
2.
Misalkan f adalah variable dari sehimpunan ordinal variable yang menjelaskan n object. Nilai f untuk object ke-i adalah xif, dan f mempunyai Mf state yang terurut yang menyatakan ranking 1, …, Mf. Gantikan tiap xif dengan ranking yang bersangkutan, rif Є {1, …, Mf}. Tiap ordinal variable dapat mempunyai bbrp state yg berbeda range variable dipetakan ke [0.0 , 1.0] supaya bobotnya sama. rif dari object ke-i dalam variable ke-f diganti dengan zif 27
Ordinal variable rif – 1 Zif = Mf -1
3.
Dissimilarity dihitung menggunakan berbagai rumus distance yang ada pada interval-scaled variable, menggunakan zif untuk menyatakan nilai f untuk object ke-i.
28
Ratio-scaled variable Membuat pengukuran yang positif pada skala
nonlinier, misal pada skala eksponensial yang menggunakan rumus : AeBt atau Ae-Bt. A dan B adalah konstanta positif. Ex. : pertumbuhan populasi bakteri.
29
Ratio-scaled variable Menghitung dissimilarity : Variable diperlakukan seperti interval-scale variable.
Dapat mengakibatkan distorsi skala. Melakukan transformasi logaritmis pada ratio-scaled variable f yang mempunyai nilai xif untuk object i dengan rumus yif = log(xif), kemudian yif diperlakukan sebagai nilai interval-scaled variable. Memperlakukan xif sebagai data continuous ordinal dan memperlakukan rankingnya sebagai nilai intervalscaled variable. 30
Variable bertipe campuran Menghitung dissimilarity antar object bertipe variable campuran : Mengelompokkan menurut jenis variable, lalu
melakukan cluster analysis secara terpisah untuk tiap jenis variable. Memungkinkan jika analisis dapat menurunkan hasil yang kompatibel. Memproses seluruh tipe variable bersama-sama, melakukan 1 cluster analysis, misalnya dengan membentuk 1 dissimilarity matrix dengan skala interval [0.0,1.0] 31
Menghitung dissimilarity matrix pada mixed variable (f) (f) δ ∑ f =1 ij d ij p
d (i, j ) =
δ ij( f )=
(f) δ ∑ f =1 ij p
0 jika
xif atau xjf tidak ada, atau Xif = xjf = 0 dan variable f adalah asymmetric binary.
Jika tidak,
(f) δ ij maka =
1.
32
Menghitung dissimilarity matrix pada mixed variable Kontribusi variable f terhadap dissimilarity antara i
dan j, δ ij( f ) ,dihitung tergantung dari tipenya : Jika f adalah binary atau nominal : (f) δ ij = 0 jika xif = xjf. Jika tidak, δ ij( f )= 1.
Jika f adalah interval-based : | | −
(f)
x x max x − min x if
jf
dengan h adalah seluruh nonmissing object untuk variable f. d
ij
=
h
hf
h
hf
Jika f adalah ordinal atau ratio-scaled : Hitung ranking rif dan z
sebagai interval-scaled
if
=
r −1 M − 1 , dan zif diperlakukan if
f
33
Types of Clusterings Partitional Clustering A division data objects into non-overlapping subsets (clusters)
such that each data object is in exactly one subset
Hierarchical clustering A set of nested clusters organized as a hierarchical tree
Partitional Clustering
Original Points
A Partitional Clustering
Hierarchical Clustering
p1 p3
p4
p2
p1 p2 Traditional Hierarchical Clustering
p3 p4
Traditional Dendrogram
p1 p3
p4
p2
p1 p2 Non-traditional Hierarchical Clustering
p3 p4
Non-traditional Dendrogram
Metode Partitioning
Metode Partitioning :
Jika terdapat k partisi yang akan dibuat, metode ini membuat partisi awal. Kemudian digunakan teknik relokasi secara iteratif untuk memperbaiki partisi dengan memindahkan object dari satu grup ke grup lain. Algoritma umum : 1.
K-means Tiap cluster dinyatakan berdasar nilai mean object di dalam cluster.
2.
K-medoids Tiap cluster dinyatakan berdasar satu object yang lokasinya berdekatan dengan inti cluster.
37
The K-Means Clustering Method Algoritma K-means diimplementasikan sbb:
1.
Partisi objek ke dalam k himpunan yg tidak kosong
2.
Hitung jarak setiap objek ke centroid dari cluster setiap partisi (centroid : titik pusat, mis. mean point)
3.
Assign setiap objek ke dalam cluster berdasarkan jarak terdekat (minimum distance)
4.
Kembali ke langkah 2, berhenti jika tidak ada perubahan cluster.
38
The K-Means Clustering Method 10
10
9
9
8
8
7
7
6
6
5
5
10 9 8 7 6 5 4
4 3 2 1 0 0
1
2
3
4
5
6
7
8
K=2 Arbitrarily choose K object as initial cluster center
9
10
Assign each objects to most similar center
Update the cluster means
3 2 1 0 0
1
2
3
4
5
6
7
8
9
10
4 3 2 1 0 0
1
2
3
4
5
6
reassign 10
9
9
8
8
7
7
6
6
5
5
4 3 2 1 0 1
2
3
4
5
6
7
8
8
9
10
reassign
10
0
7
9
10
Update the cluster means
4 3 2 1 0 0
1
2
3
4
5
6
7
8
9
39
10
Hierarchical Clustering Produces a set of nested clusters organized as a
hierarchical tree Can be visualized as a dendrogram A tree like diagram that records the sequences of merges
or splits
5
6 4 3
4 2
0.2
5 2
0.15
1 0.1
3
0.05
0
1
3
2
5
4
6
1
Metode Hierarchical Metode Hierarchical Membuat dekomposisi secara hierarkis dari suatu himpunan data object. Dapat terbagi menjadi :
Aglomerative (bottom-up) Divisive (top-down)
41
Hierarchical Clustering Memakai distance matrix sbg kriteria clustering. Metoda ini tdk perlu jml. clusters k sebagai input, tapi perlu kondisi terminasi. Step 0
a
Step 1
Step 2 Step 3 Step 4
ab
b
abcde
c
cde
d
de
e Step 4
agglomerative (AGNES)
Step 3
Step 2 Step 1 Step 0
divisive (DIANA) 42
AGNES (AGglomerative NESting Sering disebut pendekatan bottom-up. Mulai dari tiap object yang terdapat dalam grup
tertentu, kemudian object / grup object yang berdekatan bergabung, sampai seluruh grup bergabung menjadi satu (level teratas hirarki), atau sampai terjadi kondisi terminasi.
43
Agglomerative Clustering Algorithm
More popular hierarchical clustering technique
Basic algorithm is straightforward 1. 2. 3. 4. 5. 6.
Compute the proximity matrix Let each data point be a cluster Repeat Merge the two closest clusters Update the proximity matrix Until only a single cluster remains
Key operation is the computation of the proximity of two clusters
Different approaches to defining the distance between clusters distinguish the different algorithms
Starting Situation Start with clusters of individual points and a proximity
matrix
p1 p2
p3
p4 p5
p1 p2 p3 p4 p5 . . .
Proximity Matrix
...
Intermediate Situation After some merging steps, we have some clusters C1 C2 C3 C4 C5 C1 C2
C3 C4
C3 C4 C5
C1
C2
C5
Proximity Matrix
Intermediate Situation We want to merge the two closest clusters (C2 and C5) and
update the proximity matrix.
C1 C2 C3 C4 C5 C1 C2
C3
C3 C4
C4 C5 C1
C2
C5
Proximity Matrix
DIANA (DIvisive ANAlysis) Sering disebut pendekatan top-down. Mulai dari seluruh object di cluster yang sama,
kemudian cluster dipisahkan menjadi cluster-cluster yang lebih kecil, sampai akhirnya tiap object ada di satu cluster, atau sampai terjadi kondisi terminasi.
48
