clustering
DESCRIPTION
ClusteringTRANSCRIPT
Contoh
Cluster Analysis?
• Cluster: kumpulan objek data– Anggota cluster yang sama memiliki kemiripan satu sama lain, tetapi
berbeda dengan anggota cluster lain.
• Cluster analysis– Menemukan kemiripan data berdasarkan karakteristik dan
mengelompokan data yang mirip ke dalam cluster.
• Unsupervised learning: class tidak ditentukan sebelumnya
• Penggunaan– Tool untuk melihat distribusi data
– Preprocessing untuk langkah berikutnya
Aplikasi Cluster Analysis
• Pengenalan Pola
• Spatial Data Analysis – Cluster spatial
• Pemrosesan gambar
• Economic Science (terutama market research)
• WWW– Berita, hasil pencarian
– Cluster Weblog data to discover groups of similar access patterns
Aplikasi clustering (lanj)
• Marketing: Membantu pihak pemasaran untuk menentukan
grup khusus dan membuat program khusus untuk grup ini.
• Land use: Identifikasi area yang digunakan untuk hal yang
sama.
• Asuransi: Identifikasi grup yang memiliki tingkat claim yang
tinggi.
• Tata kota: Identifikasi rumah-rumah berdasrkan tipe, harga
dan lokasi.
Cluster yang berkualitas:• Metode yang bagus akan menghasilkan:
– intra-class similarity yang tinggi (anggota di dalam kelas yang
sama mirip)
– low inter-class similarity (anggota di kelas yang lain, jauh
berbeda)
• Kualitas cluter bergantung kepada ukuran kemiripan
yang digunakan oleh metode clustering.
• Kualitas juga ditentukan sejauh mana clustering dapat
menemukan pola tersembunyi.
Ukuran Kesamaan
• Kesamaan/kemiripan diukur berdasarkan fungsi jarak, d(i, j)
• Definisi distance functions bisanya sangat berbeda untuk interval-scaled, boolean, categorical, ordinal ratio, and vector variables.
• Bobot diasosiasikan dengan aplikasi dan arti data.
• Sulit untuk mendefinsikan “cukup sama ” or “cukup bagus” karena subyektif.
Requirement Clustering
• Scalability untuk data dalam jumlah besar
• Menangani berbagai macam tipe atribut.
• clusters dengan berbagai bentuk.
• Sesedikit mungkin parameter
• Meanangani noise dan outliers
• Tidak peduli urutan input record
• High dimensionality banyak atribut
• Incorporation of user-specified constraints
• Interpretability and usability
Struktur Data
• Data matrix– (two modes)
• Dissimilarity matrix– (one mode)
npx...nfx...n1x
...............ipx...ifx...i1x
...............1px...1fx...11x
0...)2,()1,(
:::
)2,3()
...ndnd
0dd(3,1
0d(2,1)
0
Tipe data dalam clustering
• Interval-scaled variables
• Binary variables ada atau tidak
• Nominal, ordinal, and ratio variables
• Campuran
Interval-Scaled Variable
• Skala linear (bukan eksponensial, bukan logaritimik)
• Positif atau negatif, pecahan atau bulat.
• Tinggi badan, berat badan, jarak dst.
• Contoh:– jarak 50m ke 100m sama dengan jarak 150-
200.
Contoh yang bukan interval-Scaled Variable
• skala richter gempa
• naik satu level = 10 kali lipat level sebelumnya.
http://www.sdgs.usd.edu/publications/maps/earthquakes/images/RichterScale.gif
Interval Variable• Jika ada beberapa atribut dan punya distribusi
berbeda: perlu distandardkan.
• Buat data menjadi standard, z-score:
– Hitung mean absolute deviation:
dimana
– Hitung standardized measurement (z-score)
.)...21
1nffff
xx(xn m
|)|...|||(|121 fnffffff
mxmxmxns
f
fifif s
mx z
Mengapa z-score?
• Tidak bisa membandingkan atribut dengan distribusi berbeda.
• Contoh:– Seseorang mendapatkan nilai 70 untuk bhs
Inggris (rata2 kelas: 60, std deviasi: 15). Dia mendapat nilai 72 untuk matematika (rata2: 68, std deviasi: 6). Nilai mana yang lebih baik?
Lanj• z-score nilai bhs Inggris:
(70-60) /15 = 0.67
• z-score nilai Matematika:
(72-68)/6 = 0.67
Dari tabel standard distribusi, probabilitas z=0.67 adalah 0.24 (25%), artinya baik untuk bhs Inggris maupun Matematika, nilai siswa ini lebih baik dari 75% siswa yg lain.
Jarak antara Interval-Scaled Variable
• similarity atau dissimilarity antar dua objek:
jarak kedua objek
• Yang populer: Minkowski distance:
q : integer positif
• If q = 1, d is Manhattan distance
pp
jx
ix
jx
ix
jx
ixjid )||...|||(|),(
2211
||...||||),(2211 pp jxixjxixjxixjid
Interval Variable (lanj)
• Jika q = 2, d adalah Euclidean distance:
– Properties
• d(i,j) 0
• d(i,i) = 0
• d(i,j) = d(j,i)
• d(i,j) d(i,k) + d(k,j)
• Cara lain: weighted distance, parametric Pearson product moment correlation
)||...|||(|),( 22
22
2
11 pp jx
ix
jx
ix
jx
ixjid
Variabel Binary
• A contingency table
• Jarak untuk symmetric binary
variables:
• Jarak untuk asymmetric binary
variables:
• Jaccard coefficient (similarity
measure untuk asymmetric
binary variables):
dcbacb jid
),(
cbacb jid
),(
pdbcasum
dcdc
baba
sum
0
1
01
Object i
Object j
cbaa jisim
Jaccard ),(
Contoh
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4Jack M Y N P N N NMary F Y N P N P NJim M Y P N N N N
•gender is a symmetric attribute•the remaining attributes are asymmetric binary•let the values Y and P be set to 1, and the value N be set to 0
75.0211
21),(
67.0111
11),(
33.0102
10),(
maryjimd
jimjackd
maryjackd
Nominal Variabel• Dapat memiliki > 2 states: red, yellow, blue,
green
• Method 1: Simple matching
– m: jumlah cocok, p: jumlah variabel
• Method 2: banyak binary variables
– Buat binary variable sebanyak states
pmpjid ),(
Ordinal
• Dapat discrete atau continuous
• Urutan penting: misalnya rank
• Dapat diperlakukan sebagai interval-scaled
– ganti xif dengan peringkat
– Petakan ke [0, 1] dengan mengganti objek ke i dan variabel ke f dengan
– Hitung seperti interval variabel
},...,1{fif
Mr
11
f
ifif M
rz
Ratio-Scaled Variables
• Ratio-scaled variable: nilai positif dengan
skala nonlinear (exponential scale) seperti
AeBt or Ae-Bt
• Cara:
– Gunakan logarithmic transformation
yif = log(xif)
– Pelakukan sebagai continuous ordinal data
Campuran
• Database dapat mengandung semua tipe:– symmetric binary, asymmetric binary, nominal, ordinal,
interval and ratio
• Gunakan weighted formula untuk mengkombinasikan semua variabel:
)(1
)()(1),(
fij
pf
fij
fij
pf
djid
Pendekatan Clustering
• Partisi :
– Buat partisi dan evaluasi berdasarkan kriteria tertentu, misalnya
meminimalkan sum of square errors
– Metode: k-means, k-medoids, CLARANS
• Hirarkis:
– Buat struktur hierarchical menggunakan kriteria tertentu
– Metode: Diana, Agnes, BIRCH, ROCK, CAMELEON
• Density-based :
– Berdasarkan connectivity dan density functions
– Metode: DBSACN, OPTICS, DenClue
• Yang lain: Grid-based approach, model-based, frequent pattern-based, user-
guided or constraint-based:
Jarak antar cluster• Single link: jarak terpendek antar elemen di dua cluster dis(Ki,
Kj) = min(tip, tjq)
• Complete link: jarak terjauh antar elemen di dua cluster, i.e.,
dis(Ki, Kj) = max(tip, tjq)
• Average: rata2 jarak i.e., dis(Ki, Kj) = avg(tip, tjq)
• Centroid: jarak antara centroids, i.e., dis(Ki, Kj) = dis(Ci, Cj)
• Medoid: jarak antarta medoids, i.e., dis(Ki, Kj) = dis(Mi, Mj)
– Medoid: elemen yang dipilih dan dianggap merupakan titik tengah
cluster
Metode Partisi: K-means
1. Partisi objek ke k nonempty subset
2. Hitung centroid (centroid adalah titik
tengah cluster)
3. Masukkan setiap objek ke cluster
dengan centroid terdekat
4. Kembali ke langkah 2, sampai tidak ada
posisi yang berubah
Contoh K-Means
• Anda diminta mencluster 8 point berikut: A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9). gunakan K-Means dengan euclidean distance. Asumsikan A2, B2 dan C2 sebagai inisial cluster untuk cluster A, B dan C. Tampilkan perhitungan dan isi cluster (termasuk centroid cluster yang dihitung dengan rata-rata).
Contoh K-Means• A1(2, 10), A2(2, 5), A3(8, 4), B1(5, 8),
B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9).• Jarak antara setiap titik dengan setiap
cluster. Cluster A, centroid: (2,5)Cluster B, centroid: (7,5)Cluster C, centroid: (4,9)
A1 cluster A
A3 cluster A, d(A3,A) = B1 cluster A, d(B1,A) =B3 cluster A, d(B3,A) =C1 cluster A, d(C1,A) =
22 |510||22(|),1( AAd
5),1( AAd
Contoh K-Means:
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
K=2
Arbitrarily choose K object as initial cluster center
Assign each objects to most similar center
Update the cluster means
Update the cluster means
reassignreassign
K-Medoids
• Kelemahan utama centroid jika ada outlier posisi centroid akan terpengaruhi.
• Centroid diganti Modoids salah satu data dipilih sebagai titik tengah
Contoh K-Metoid (PAM)
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
K=2
Arbitrary choose k object as initial medoids
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
Assign each remaining object to nearest medoids Randomly select a
nonmedoid object,Oramdom
Compute total cost of swapping
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
Total Cost = 26
Swapping O and Oramdom
If quality is improved.
Do loop
Until no change
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10