01/11/2014
Analisis Klaster S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha
1
Agenda •
Klastering
•
Persyaratan untuk Klastering
•
Tipe data dalam analisis klaster • • • • •
Variabel skala Interval Variabel biner Variabel nominal Variabel ordinal Variabel skala rasio
•
Klastering mempartisi
•
Klastering hirarki
2
1
01/11/2014
Klastering •
Klaster: • •
•
Analisis klaster •
•
Kumpulan objek yang sejenis / berkarakter sama dalam 1 klaster Kumpulan objek tidak sejenis/berbeda dalam klaster lainnya.
Menemukan kemiripan antar data berdasarkan karakteristik yang ditemukan pada data, kemudian mengelompokkan data objek yang mirip ke dalam klaster
Unsupervised learning: tidak ada class yang ditentukan sebelumnya
3
Klastering •
Contoh penerapan umum : • • • •
Bisnis : Menemukan kelompok konsumen 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 karakterisasi atau klasifikasi
4
2
01/11/2014
Kualitas: Klastering yang Baik? •
Metoda klastering yang baik menghasilkan klaster berkualitas tinggi: •
Kesamaan intra-class yang tinggi
•
Kesamaan inter-class yang rendah
•
Kualitas hasil klastering bergantung pada ukuran kemiripan yang dipakai dan implementasinya
•
Kualitas klastering diukur juga dengan kemampuan untuk menemukan pola tersembunyi
5
Struktur Data dalam Analisis Klaster •
Matriks data (obyek oleh struktur variabel)
•
Matrisk ketidaksamaan (obyek oleh struktur obyek)
6
3
01/11/2014
Matriks Data •
•
Menyatakan n object, misal orang, dengan p variable (= pengukuran atau atribut) mis. umur, tinggi, berat, gender, ras, dll.
x11 ... x i1 ... x n1
... x1p ... ... ... xip ... ... ... xnp
... x1f ... ... ...
xif
...
...
... xnf
Strukturnya dapat dlm bentuk tabel relasional ataupun matriks n x p 7
Matriks Ketidaksamaan •
•
Menyimpan sekumpulan kedekatan yang tersedia untuk seluruh pasangan n object. Direpresentasikan dalam bentuk tabel nxn, dimana d(i,j) adalah perbedaan atau ketidaksamaan antara obyek i dan j. Semakin dekat d(i,j) dengan 0, berarti obyek 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
4
01/11/2014
Tipe data dalam Analisis Klaster •
Variabel skala interval
•
Variabel biner
•
Variabel nominal
•
Variabel ordinal
•
Variabel skala rasio
•
Kombinasi tipe-tipe di atas.
9
Variabel Skala Interval •
Adalah pengukuran kontinyu untuk skala yang hampir linier.
•
Mis. Berat & tinggi, koordinat lintang dan bujur (untuk mengklaster rumah), dan temperatur udara.
•
Perubahan satuan dapat mempengaruhi analisis kaster, mis. Dari meter inch
•
Semakin kecil satuan ukurannya, kisaran variable akan semakin besar, mengubah struktur klastering data perlu distandarkan 10
5
01/11/2014
Variabel Skala Inteval Menstandarkan data : data ukuran diubah ke variabel yang tidak ada satuannya (tanpa unit) dengan cara : Menghitung mean absolute deviation, sf :
1.
sf= 1/n(|x1f-mf| + |x2f-mf| + …+|xnf-mf|) x1f , …, xnf : n pengukuran untuk variabel f. mf : nilai rata-rata variabel f. Menghitung standardized-measurement/ z-score :
2.
xif – mf Zif = sf 11
Variabel Skala Interval •
Ketidaksamaan dalam variabel skala interval dihitung berdasar jarak (distance) antara tiap pasang obyek.
•
Beberapa pengukuran distance : • • •
Jarak Euclidean Jarak Manhattan Jarak Minkowski
12
6
01/11/2014
Jarak Euclidean 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 obyek
13
Jarak Manhattan/ jarak blok kota 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 obyek
14
7
01/11/2014
Jarak Minkowski •
Merupakan generalisasi jarak Euclidean dan Manhattan. d(i,j) = (|xi1 – xj1|q + |xi2 – xj2|q + …+ |xip – xjp|q)1/q
• q : integer positif. • Menyatakan jarak Manhattan jika q = 1 • Menyatakan jarak Euclidean jika q = 2 15
Jarak Euclidean Berbobot •
Tiap variabel dapat diberi bobot sesuai tingkat kepentingannya. Jarak Euclidean-nya dapat dihitung sbb : d(i,j) = w1|xi1 – xj1|2 + w2|xi2 – xj2|2 + …+ wp|xip – xjp|2
• Pembobotan juga dapat diaplikasikan pada jarak Manhattan dan Minkowski 16
8
01/11/2014
Variabel Biner •
Merupakan variabel yang memiliki 2 kondisi, yaitu 0 dan 1.
•
0 = tidak ada, 1 = ada
•
Misal, pada obyek pasien, terdapat variable perokok. 1 = pasien perokok, 0 = pasien bukan perokok.
•
Variabel biner jika diperlakukan seperti intervalscale variable hasil klaster salah.
17
Variabel Biner •
Menghitung ketidaksamaan: •
object j
Matrik ketidaksamaan untuk variabel biner yang berbobot sama.
object i
1
0
jml
1
q
r
q+r
0
s
t
s+t
jml
q+s
r+t
p 18
9
01/11/2014
Variabel Biner •
Variabel Biner Simetris: • •
Kedua kondisinya bernilai dan berbobot sama. Misal, variabel jenis kelamin. Kesamaan yang invarian: hasil tdk berubah variabel dikodekan secara berbeda. r+s d(i,j) = -----------q+r+s+t
19
Variabel Biner •
Variabel Biner Asimetris : • •
• •
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 variabel, 2 buah kondisi 1 lebih penting dari 2 buah kondisi 0, sehingga seringkali disebut monary (seperti hanya memiliki 1 kondisi). Kesamaan non-varian. Menggunakan koefisien Jaccard, yaitu nilai t diabaikan.
r+s d(i,j) = -----------q+r+s
20
10
01/11/2014
Variabel Biner 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 • Atribut simetris: gender • Atribut asimetris: atribut lainnya – Y dan P 1, N 0 – Jarak antar obyek dihitung berdasar variabel asimetris.
21
Variabel Biner 0+1 d(jack,mary) = ------------ = 0.33 2+0+1
•
Jarak jim dan mary paling besar, dalam kasus ini berarti penyakitnya paling tidak sama.
•
Jack dan mary sebaliknya.
1+1 d(jack,jim) = ------------ = 0.67 1+1+1 1+2 d(jim,mary) = ------------ = 0.75 1+1+2
22
11
01/11/2014
Variabel Nominal •
Adalah generalisasi variabel biner dalam hal variable ini dapat menampung lebih dari 2 kondisi.
•
Misal, variabel warna_peta mempunyai 5 kondisi merah, hijau, biru, kuning, hitam.
•
Kondisi dinyatakan dalam huruf, simbol, atau integer 1,2,…,M. Integer hanya untuk penunjuk data, tidak menunjukkan urutan tertentu.
23
Variabel Nominal •
Menghitung ketidaksamaan untuk variabel nominal : p-m d(i,j) = -----------p
• • • •
m adalah banyaknya i dan j yang kondisinya sama. p adalah jumlah seluruh variabel. Dapat dikodekan ke variabel biner asimetris. Misal, obyek yang mempunyai warna kuning diset 1, sedangkan warna lainnya 0, dst untuk masing-masing warna. • Koefisien ketidaksamaan dihitung dengan cara yang sama dengan variabel biner.
24
12
01/11/2014
Variabel Ordinal •
Variabel ordinal diskrit: seperti variabel nominal, hanya saja kondisi M yang bernilai ordinal diurutkan dalam urutan yang mempunyai arti.
•
Variabel ordinal kontinyu: 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
Variabel Ordinal •
Nilai ordinal variable dapat dipetakan ke ranking.
•
Jika terdapat ordinal variable f yang mempunyai kondisi Mf , kondisi yang terurut menentukan ranking 1, …, Mf.
•
Menghitung ketidaksamaan antar obyeknya seperti pada variabel skala interval.
26
13
01/11/2014
Variabel Ordinal Misalkan f adalah variabel dari sehimpunan variabel ordinal yang menjelaskan obyek n. 1.
Nilai f untuk obyek ke-i adalah xif, dan f mempunyai kondisi Mf yang terurut yang menyatakan ranking 1, …, Mf. Gantikan tiap xif dengan ranking yang bersangkutan, rif Є {1, …, Mf}.
2.
Tiap variabel ordinal apat mempunyai bbrp kondisi yg berbeda kisaran variabel dipetakan ke [0.0 , 1.0] supaya bobotnya sama. rif dari obyek e-i dalam variabel ke-f diganti dengan zif 27
Variabel Ordinal rif – 1 Zif = Mf -1 3.
Ketidaksamaan dihitung menggunakan berbagai rumus jarak yang ada pada variabel skala interval, menggunakan zif untuk menyatakan nilai f untuk obyek ke-i.
28
14
01/11/2014
Variabel Skala Rasio •
Membuat pengukuran yang positif pada skala nonlinier, misal pada skala eksponensial yang menggunakan rumus : AeBt atau Ae-Bt. A dan B adalah konstanta positif.
•
Contoh: pertumbuhan populasi bakteri.
29
Variabel Skala Rasio •
Menghitung ketidaksamaan: • •
•
Variable diperlakukan seperti variabel skala interval. Dapat mengakibatkan distorsi skala. Melakukan transformasi logaritmis pada variabel skala rasio f yang mempunyai nilai xif untuk object i dengan rumus yif = log(xif), kemudian yif diperlakukan sebagai nilai variabel skala interval Memperlakukan xif sebagai data ordinal kontinyu dan memperlakukan rankingnya sebagai nilai variabel skala interval.
30
15
01/11/2014
Variable bertipe campuran •
Menghitung ketidaksamaan antar obyek bertipe variable campuran : •
•
Mengelompokkan menurut jenis variabel, lalu melakukan analisis klaster secara terpisah untuk tiap jenis variabel. Memungkinkan jika analisis dapat menurunkan hasil yang kompatibel. Memproses seluruh tipe variabel bersama-sama, melakukan 1 analisis klaster, misalnya dengan membentuk 1 matriks ketidaksamaan dengan skala interval [0.0,1.0]
31
Menghitung matriks ketidaksamaan pada variabel campuran ∑ δ d d (i, j ) = ∑ δ p
f =1
(f) ij
p
f =1
(f) ij
(f) ij
(f) • δ ij = 0 jika
• •
•
xif atau xjf tidak ada, atau Xif = xjf = 0 dan variable f adalah asymmetric binary.
Jika tidak, maka
δ ij( f=) 1.
32
16
01/11/2014
Menghitung matriks ketidaksamaan pada variabel campuran •
Kontribusi variable f terhadap dissimilarity antara i dan j, δ ij( f ),dihitung tergantung dari tipenya :
•
Jika f adalah biner atau nominal : (f)
• δ ij
•
= 0 jika xif = xjf. Jika tidak,
Jika f adalah| xberbasis interval : −x | •
d
(f)
ij
if
=
max x h
hf
jf
− min h x hf
untuk variable f. •
f) δ=ij( 1.
dengan h adalah seluruh yang tidak hilang
Jika f adalah ordinal atau berbasis rasio : −1 •
r Hitung ranking rif dan z = M −,1 dan zif diperlakukan sebagai interval-scaled if
if
f
33
Tipe – tipe Klastering •
Klastering Partisional •
•
Pembagian dari obyek – obyek data ke dalam subset / klaster yang tidak tumpang tindih dimana setiap obyek persis menempati sebuah subset / klaster
Klastering Hirarkikal •
Kumpulan dari klaster – klaster yang bertumpuk sebagai pohon hirarki
17
01/11/2014
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
18
01/11/2014
Metode Mempartisi •
Metode mempartisi: • •
•
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 obyek di dalam klaster.
2.
K-medoids Tiap klaster dinyatakan berdasar satu obyek yang lokasinya berdekatan dengan inti klaster.
37
Metode Klastering K-Means •
Algoritma K-means diimplementasikan sbb: 1.
Partisi objek ke dalam k himpunan yg tidak kosong
2.
Hitung jarak setiap objek ke centroid dari klaster setiap partisi (centroid : titik pusat, mis. mean point)
3.
Tempatkan setiap objek ke dalam klaster berdasarkan jarak terdekat (jarak minimum)
4.
Kembali ke langkah 2, berhenti jika tidak ada perubahan klaster.
38
19
01/11/2014
Metode Klastering K-Means 10
10
9
9
8
8
7
7
6
6
10 9 8 7 6
5
5
5 4
4
Tempat kan setiap obyek ke pusat yang paling mirip
3 2 1 0 0
1
2
3
4
5
6
7
8
9
10
K=2 Secara acak memilih obyek K sebagai pusat klaster awal
3 2 1 0 0
1
2
3
4
5
6
7
8
9
10
4
Perbarui mean dari klaster
Penempatan Ulang
3 2 1 0 0
1
2
3
4
5
6
7
8
9
10
Penempatan Ulang
10
10
9
9
8
8
7
7 6
6 5
5
Perbarui mean klaster
4 3 2 1
4 3 2 1
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
39
Klastering Hirarkikal •
Menghasilkan sebuah set dari klaster – klaster bertumpuk (nested) yang diorganisasi sebagai pohon hirarki
•
Dapat di visualisasikan dalam sebuah dendogram Sebuah diagram seperti pohon yang merekam urutan penggabungan dan pemisahan
•
5
6 0.2
4 3
4 2 5
0.15
2 0.1
1 0.05
0
3
1
3
2
5
4
1
6
20
01/11/2014
Metode Hirarkikal •
Metode Hirarkikal • •
Membuat dekomposisi secara hirarkis dari suatu himpunan data object. Dapat terbagi menjadi : Aglomerative (bottom-up) • Divisive (top-down) •
41
Klastering Hirarkikal •
Memakai matriks jarak sbg kriteria klastering. Metoda ini tdk perlu jumlah klaster 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
21
01/11/2014
AGNES (AGglomerative NESting) •
Sering disebut pendekatan bottom-up.
•
Mulai dari tiap obyek yang terdapat dalam grup tertentu, kemudian obyek / grup obyek yang berdekatan bergabung, sampai seluruh grup bergabung menjadi satu (level teratas hirarki), atau sampai terjadi kondisi terminasi.
43
Algoritma Agglomerative Clustering Teknik klastering hirarkikal yang lebih populer
•
Algoritma dasar
•
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
Operasi kunci adalah komputasi dari kedekatan dari dua klaster
• •
Pendekatan – pendekatan yang berbeda dalam mendefinisikan jarak antara klaster yang membedakan algoritma – algoritma yang berbeda
22
01/11/2014
Situasi Awal •
Dimulai dengan klaster dari setiap poin dan sebuah matriks kedekatan p1 p2
p3
p4 p5
...
p1 p2 p3 p4 p5 .
Proximity Matrix
. .
Situassi Intermediate •
Setelah beberapa langkah penggabungan, kita memilik beberapa C1 C2 C3 C4 C5 klaster C1 C2
C3 C4
C3 C4 C5
C1
C2
Proximity Matrix
C5
23
01/11/2014
Situasi Intermediate •
Kita ingin menggabungkan dua klaster terdekat (C2 and C5) dan memperbarui matriks kedekatan. C1 C2 C3
C4 C5
C1 C2
C3
C3 C4
C4 C5
Proximity Matrix
C1
C2
C5
DIANA (DIvisive ANAlysis) •
Sering disebut pendekatan top-down.
•
Mulai dari seluruh obyek di klaster yang sama, kemudian klaster dipisahkan menjadi klaster – klaster yang lebih kecil, sampai akhirnya tiap obyek ada di satu klaster, atau sampai terjadi kondisi terminasi.
48
24
