clustering ( season 1 ) k-means

Clustering (Season 1)K-Means

Pengenalan Pola

Materi 4

Eko Prasetyo

Teknik Informatika

UPN “Veteran” Jawa Timur

2012

2

Konsep ClusteringKlasifikasi melakukan pengelompokan data dimana

setiap data sudah ada label kelasnya◦ Shingga pekerjaan berikutnya adalah membuat model

untuk dapat melakukan prediksi pada data baru yang kemudian muncul untuk diketahui kelasnya.

Clustering (pengelompokan) melakukan pemisahan/pemecahan/segmentasi data kedalam sejumlah cluster (kelompok) menurut karakteristik tertentu yang diinginkan. ◦ Dalam pekerjaan clustering label dari setiap data belum

diketahui,

◦ Diharapkan nantinya dapat diketahui kelompok data untuk kemudian diberikan label sesuai keinginan.

3

Konsep Clustering Cluster analysis adalah pekerjaan yang

mengelompokkan data (obyek) yang didasarkan hanya pada informasi yang ditemukan dalam data yang menggambarkan obyek tersebut dan hubungan diantaranya (Tan, 2006).

Tujuan: agar obyek-obyek yang bergabung dalam sebuah kelompok (cluster) merupakan obyek-obyek yang mirip (atau berhubungan) satu sama lain dan berbeda (atau tidak berhubungan) dengan obyek dalam kelompok yang lain.

Lebih besar kemiripannya (atau homogenitasnya) dalam kelompok dan lebih besar perbedaannya diantara kelompok yang lain, konsep ini yang dibahas dalam clustering.

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

Data asli

Dua cluster

Tiga cluster

Empat cluster

4

Konsep Clustering Bidang penerapan teknik clustering: kedokteran,

kesehatan, psikologi, hukum, statistik, astronomi, klimatologi dan sebagainya. ◦ Kedokteran, teknik clustering dapat digunakan untuk

mengelompokkan jenis-jenis penyakit berbahaya berdasarkan karakteristik / sifat-sifat penyakit pasien.

◦ Kesehatan, dapat digunakan untuk mengelompokkan jenis-jenis makanan berdasarkan kandungan kalori, vitamin, protein.

Penggunaan hasil clustering◦ Summarization, protoype yang dapat mewakili seluruh data◦ Compression, data-data dalam cluster yang sama dapat

dikompres dengan diwakili oleh index prototype dari setiap cluster

◦ Efisiensi pencarian tetangga terdekat

5

K-Means Metode analisis cluster yang mengarah pada pemartisian

N obyek pengamatan kedalam K kelompok (cluster) dimana setiap obyek pengamatan dimiliki oleh sebuah kelompok/cluster dengan mean (rata-rata) terdekat.

Salah satu metode pengelompokan data non hierarki (partitioning) yang berusaha mempartisi data ke dalam bentuk dua atau lebih cluster. ◦ Mempartisi data ke dalam cluster sehingga data yang memiliki

karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam cluster yang lain.

◦ Tujuannya adalah meminimalisasikan fungsi obyektif yang diset dalam proses pengelompokan, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalkan variasi antar cluster.

6

Algoritma K-Means1. Tentukan jumlah kelompok2. Alokasikan data ke dalam kelompok secara acak3. Hitung pusat cluster (centroid/rata-rata) dari data

yang ada di masing-masing cluster4. Alokasikan masing-masing data ke centroid/rata-

rata terdekat5. Kembali ke Langkah 3, ◦ apabila masih ada data yang berpindah cluster, ◦ atau apabila perubahan nilai centroid ada yang di atas

nilai threshold yang ditentukan, ◦ atau apabila perubahan nilai pada fungsi obyektif yang

digunakan masih di atas nilai threshold yang ditentukan

7

Algoritma K-Means Jika M menyatakan jumlah data dalam sebuah cluster, i

menyatakan fitur ke-i dalam sebuah cluster dan p menyatakan dimensi data, maka untuk menghitung centroid fitur ke-i digunakan formula:

◦ dilakukan sebanyak p dimensi, sehingga i mulai 1 sampai p. Cara mengukur jarak data ke pusat cluster, diantaranya :

Euclidean (Bezdek, 1981), Manhattan/City Block (Miyamoto dan Agusta, 1995), dan Minkowsky (Miyamoto dan Agusta, 1995)

M

jji x

MC

1

1

p

jjj xxxxxxD

1

2

1221212 ),(

p

jjj xxxxxxD

11211212 ),(

Euclidean Manhattan/City Block

8

Algoritma K-Means Pengalokasian data ke cluster dapat dirumuskan sebagai berikut

(MacQueen, 1967):

◦ Dimana ail adalah nilai keanggotaan titik xi ke pusat cluster Cl, d adalah jarak terpendek dari data xi ke K cluster setelah dibandingkan, dan

Cl centroid (pusat cluster) ke-l.

Fungsi objektif berdasarkan jarak dan nilai keanggotaan data dalam cluster

◦ Dimana N adalah jumlah data, K adalah jumlah cluster, ail adalah nilai keanggotaan titik data xi ke pusat cluster Cl, Cl adalah pusat cluster ke-l, D(xi,Cl) adalah jarak titik xi ke cluster Cl yang diikuti.

◦ Untuk a mempunyai nilai 0 atau 1. Apabila suatu data merupakan anggota suatu kelompok maka nilai ail =1 , jika tidak, akan maka nilai ail =0

lainnya

CxDda liil 0

)},(min{1

N

i

K

lliic CxDaJ

1 1

2,

9

Fungsi K-Means di matlab [IDX,C,sumd,D] = kmeans(X,k) [IDX,C,sumd,D] = kmeans(...,’distance’,val)

Parameter KeteranganX Matrik data set MN, dimana M adalah jumlah data, N adalah jumlah fitur.k Nilai yang menyatakan jumlah clusterIDX Matrik M1 yang menyatakan indeks cluster yang diikuti setiap data, nilai

didalamnya mulai 1 sampai k. M adalah jumlah data.C Matrik kN yang menyatakan lokasi centroid setiap cluster, dimana k adalah

jumlah cluster, N adalah jumlah fitursumd Matrik 1k yang menyatakan jumlah jarak semua data yang tergabung dalam

setiap cluster.D Matrik Mk yang menyatakan jarak dari setiap data ke centroid cluster. M

adalah jumlah data, k adalah jumlah cluster.val Nilai untuk parameter ‘distance’. Pilihan nilainya:

'sqEuclidean', untuk jarak Squared Euclidean, nilai default yang digunakan.

'cityblock', untuk Manhattan (block city). 'Hamming', untuk jarak Hamming (prosentase perbedaan bit), hanya

cocok untuk data biner.

10

Contoh Ada 10 data pada data set. Dimensi data ada 2 fitur

(agar mudah dalam visualisasi koordinat kartesius).

Fitur yang digunakan dalam pengelompokan adalah x dan y

Jarak yang digunakan adalah Euclidean distance.

Jumlah cluster (K) adalah 3. Threshold (T) yang

digunakan untuk perubahan fungsi objektif adalah 0.1.

Data ke-i Fitur x Fitur y1 1 12 4 13 6 14 1 25 2 36 5 37 2 58 3 59 2 6

10 3 8

11

Inisialisasi

Data ke-i Fitur x Fitur y C1 C2 C31 1 1 *2 4 1 *3 6 1 *4 1 2 *5 2 3 *6 5 3 *7 2 5 *8 3 5 *9 2 6 *

10 3 8 *

Centroid awal yang didapat

Cluster Fitur x Fitur y

1 1.0000 1.0000

2 3.4000 3.8000

3 2.7500 3.7500

Data anggota Fitur x Fitur y3 6 14 1 26 5 37 2 5

10 3 8M Jumlah x Jumlah y5 17 19

Rata-rata 3.4000 3.8000

Data anggota Fitur x Fitur y2 4 15 2 38 3 59 2 6M Jumlah x Jumlah y4 11 15

Rata-rata 2.7500 3.7500

C1 C2 C3

0.0000 0 0

0 0 9.1250

0 14.6000 0

0 9.0000 0

0 0 1.1250

0 3.2000 0

0 3.4000 0

0 0 1.6250

0 0 5.6250

0 17.8000 0

0.0000 48.0000 17.5000

Keanggotaan data dalam cluster Fungsi objektif

Nilai FO awal = 0Nilai FO baru = 65.5Perubahan FO = |65.5-0| = 65.5

Masih diatas TData anggota Fitur x Fitur y


Rata-rata 1.0000 1.0000

12

Iterasi 1

Data ke-i C1 C2 C3 Min C Baru

1 0.0000 3.6878 3.2596 0.0000 12 3.0000 2.8636 3.0208 2.8636 23 5.0000 3.8210 4.2573 3.8210 24 1.0000 3.0000 2.4749 1.0000 15 2.2361 1.6125 1.0607 1.0607 36 4.4721 1.7889 2.3717 1.7889 27 4.1231 1.8439 1.4577 1.4577 38 4.4721 1.2649 1.2748 1.2649 29 5.0990 2.6077 2.3717 2.3717 3

10 7.2801 4.2190 4.2573 4.2190 2

Jarak dan keanggotaan data dalam cluster

Centroid baru yang didapat

Data anggota Fitur x Fitur y1 1 14 1 2M Jumlah x Jumlah y2 2 3

Rata-rata 1.0000 1.5000

Cluster Fitur x Fitur y1 1.0000 1.50002 4.2000 3.60003 2.000 4.6667

Data anggota Fitur x Fitur y2 4 13 6 16 5 38 3 5


Rata-rata 4.2000 3.6000

Data anggota Fitur x Fitur y

5 2 3

7 2 5

9 2 6

M Jumlah x Jumlah y

3 6 14

Rata-rata 2.0000 4.6667

C1 C2 C3

0.2500 0 0

0 6.8000 0

0 10.0000 0

0.2500 0 0

0 0 2.7778

0 1.0000 0

0 0 0.1111

0 3.4000 0

0 0 1.7778

0 20.8000 0

0.5000 42.0000 4.6667

Nilai FO awal = 65.5Nilai FO baru = 47.1667Perubahan FO = |47.1667 - 65.5| = 18.3333 Masih diatas T

Fungsi objektif

Ada 4 data berpindah cluster2 dari 3 ke 24 dari 2 ke 17 dari 2 ke 38 dari 3 ke 1

13

Iterasi 2


1 0.5000 4.1231 3.8006 0.5000 12 3.0414 2.6077 4.1767 2.6077 23 5.0249 3.1623 5.4263 3.1623 24 0.5000 3.5777 2.8480 0.5000 15 1.8028 2.2804 1.6667 1.6667 36 4.2720 1.0000 3.4319 1.0000 27 3.6401 2.6077 0.3333 0.3333 38 4.0311 1.8439 1.0541 1.0541 39 4.6098 3.2558 1.3333 1.3333 3

10 6.8007 4.5607 3.4801 3.4801 3


Centroid baru yang didapat

Data anggota Fitur x Fitur y1 1 14 1 2M Jumlah x Jumlah y2 2 3

Rata-rata 1.0000 1.5000

Cluster Fitur x Fitur y1 1.0000 1.50002 5.0000 1.66673 2.4000 5.4000


Fungsi objektif


2 4 1

3 6 1

6 5 3

M Jumlah x Jumlah y

3 15 5

Rata-rata 5.0000 1.6667


5 2 3

7 2 5

8 3 5

9 2 6

10 3 8

M Jumlah x Jumlah y

5 12 27

Rata-rata 2.4000 5.4000

C1 C2 C3

0.2500 0 0

0 1.4444 0

0 1.4444 0

0.2500 0 0

0 0 5.9200

0 1.7778 0

0 0 0.3200

0 0 0.5200

0 0 0.5200

0 0 7.1200

0.5000 4.6667 14.4000

Ada 2 data berpindah cluster: 8 dan 108 dari 2 ke 310 dari 2 ke 3

14

Iterasi 3


1 0.5000 4.0552 4.6174 0.5000 12 3.0414 1.2019 4.6819 1.2019 23 5.0249 1.2019 5.6851 1.2019 24 0.5000 4.0139 3.6770 0.5000 15 1.8028 3.2830 2.4331 1.8028 16 4.2720 1.3333 3.5384 1.3333 27 3.6401 4.4845 0.5657 0.5657 38 4.0311 3.8873 0.7211 0.7211 39 4.6098 5.2705 0.7211 0.7211 3

10 6.8007 6.6416 2.6683 2.6683 3


Centroid baru yang didapatCluster Fitur x Fitur y

1 1.3333 2.00002 5.0000 1.66673 2.5000 6.0000


Fungsi objektif


2 4 1

3 6 1

6 5 3

M Jumlah x Jumlah y

3 15 5

Rata-rata 5.0000 1.6667

C1 C2 C3

1.1111 0 0

0 1.4444 0

0 1.4444 0

0.1111 0 0

1.4444 0 0

0 1.7778 0

0 0 1.2500

0 0 1.2500

0 0 0.2500

0 0 4.2500

2.6667 4.6667 7.0000Data anggota Fitur x Fitur y

1 1 1

4 1 2

5 2 3

M Jumlah x Jumlah y

3 4 6

Rata-rata 1.3333 2.0000


7 2 5

8 3 5

9 2 6

10 3 8

M Jumlah x Jumlah y

4 10 24

Rata-rata 2.5000 6.0000

Data 5 berpindah cluster dari 3 ke 1

15

Iterasi 4


1 1.0541 4.0552 5.2202 1.0541 12 2.8480 1.2019 5.2202 1.2019 23 4.7726 1.2019 6.1033 1.2019 24 0.3333 4.0139 4.2720 0.3333 15 1.2019 3.2830 3.0414 1.2019 16 3.8006 1.3333 3.9051 1.3333 27 3.0732 4.4845 1.1180 1.1180 38 3.4319 3.8873 1.1180 1.1180 39 4.0552 5.2705 0.5000 0.5000 3

10 6.2272 6.6416 2.0616 2.0616 3


Centroid baru yang didapatCluster Fitur x Fitur y

1 1.3333 2.00002 5.0000 1.66673 2.5000 6.0000

Nilai FO awal = 14.3333Nilai FO baru = 14.3333Perubahan FO = |14.3333 – 14.3333| = 0.0000 Sudah dibawah T

Fungsi objektif


2 4 1

3 6 1

6 5 3

M Jumlah x Jumlah y

3 15 5

Rata-rata 5.0000 1.6667

C1 C2 C3

1.1111 0 0

0 1.4444 0

0 1.4444 0

0.1111 0 0

1.4444 0 0

0 1.7778 0

0 0 1.2500

0 0 1.2500

0 0 0.2500

0 0 4.2500

2.6667 4.6667 7.0000Data anggota Fitur x Fitur y

1 1 1

4 1 2

5 2 3

M Jumlah x Jumlah y

3 4 6

Rata-rata 1.3333 2.0000


7 2 5

8 3 5

9 2 6

10 3 8

M Jumlah x Jumlah y

4 10 24

Rata-rata 2.5000 6.0000

Tidak ada data yang berpindah cluster

16

Perubahan hasil clustering

0 2 4 6 80

2

4

6

8

1 2 34

5 6

7 89

10

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

Data asli Inisialisasi Hasil setelah iterasi 1

Hasil setelah iterasi 2 Hasil setelah iterasi 3 Hasil setelah iterasi 4

17

Proses di matlab

data = [1 14 16 11 22 35 32 53 52 63 8];

dataset_clustering_2_dimensik = 3;[idx,C,sumd,D] = kmeans(data,k);figure('Position',[300 300 210 160]);plot(data(idx==1,1),data(idx==1,2),'ko',data(idx==2,1),data(idx==2,2),'k+',data(idx==3,1),data(idx==3,2),'kd','MarkerSize',6);

axis([0 9,0 9]);hold onplot(C(:,1),C(:,2),'kx','MarkerSize',8);hold offCdisplay('IDX | JARAK KE C1 | JARAK KE C2 | JARAK KE C3');[idx D.^0.5]

Nama file: dataset_clustering_2_dimensi.m

Nama file: contoh_kmeans.m

18

ANY QUESTION ?To Be Continued … Clustering (Season 2)

clustering ( season 1 ) k-means

Documents