algoritma clustering - universitas algoritma klastering.pdf · pdf file p4 p1 p3 p2 p4 p1...

Algoritma Clustering Amil Ahmad Ilham

1

Pengertian Cluster

Cluster: Kumpulan dari object data, dimana data dalam cluster yang sama memiliki kemiripan dan memiliki perbedaan dengan data yang berada dalam cluster lain (Jia Wei-Han)

Centroid: Titik pusat cluster

Proses pembelajaran di dalam cluster : • Jarak antar data dalam cluster sama di minimalkan

(memaksimalkan kemiripan) • Jarak antar data dari cluster berbeda di maksimalkan

(memaksimalkan perbedaan)

2

Tujuan: Cluster Analysis • Menentukan kelompok objects data sedemikian hingga object data yang berada

dalam satu kelompok memiliki kemiripan satu dengan lainnya, dan memiliki berbedaan dengan object data yang berada dalam kelompok lain

Memaksimasi Inter- cluster distances

Meminimasi Intra- cluster distances

Tujuan

3

Gambaran Cluster

Data set pada gambar secara alami memiliki tiga kelompok data. Dengan demikian data set ini terdiri dari 3 cluster.

4

Bagaimana melakukan clustering

5

Macam clustering

• Partitional Clustering

Proses untuk membagi sekumpulan objek ke dalam beberapa cluster dimana setiap anggota cluster tidak terjadi overlap. Artinya sebuah object data hanya akan menjadi bagian dari sebuah cluster

• Hierarchical Clustering

Proses untuk membagi sekumpulan objek ke dalam beberapa cluster yang memungkinkan terjadi overlap. Sebuah object data bisa menjadi anggota lebih dari satu cluster.

Sehingga penggambaran cluster dalam bentuk hierarchical tree atau dendogram

6

Partitional Clustering

A Partitional Clustering

7

Hierarchical Clustering

p4

p1 p3

p2

p4

p1 p3

p2

p4p1 p2 p3

p4p1 p2 p3

dicluster menjadi

8

Euclidean Distance

Contoh

A(3,2)

B(10,6)

𝑑𝐸 𝐵, 𝐴 = (10 − 3) 2+(6 − 2)2

𝑑𝐸 𝐵, 𝐴 = 8.06

𝑑𝐸 𝐵, 𝐴 = 49 + 16

𝑑𝐸 𝐵, 𝐴 = 65

9

Algoritma K-Means Algoritma K-Means

10

Algoritma K-Means

• K-Means adalah salah satu partitional clustering yang terkenal

• Parameter K menunjukkan banyaknya cluster yang akan dibentuk

• Perbandingan dengan metode lain

• Kelebihan: komputasi yang sederhana

• Kekurangan: kualitas kluster tergantung pada pemilihan centroid awal dan nilai k.

• Nilai k ditentukan di awal.

• Koordinat awal setiap centroid ditentukan secara acak.

11

Algoritma K-Means Contoh k-Means clustering dengan k=3 (berarti ada 3 centroid yaitu m1, m2, m3)

Setiap cluster diasosiasikan dengan sebuah centroid

Setiap point data dimasukkan ke cluster dengan centroid terdekat berdasarkan jarak terkecil.

12

Algoritma K-Means

1.Tentukan jumlah klaster (k) 2.Tentukan koodinat awal setiap centroid secara acak. 3. Hitung jarak setiap data ke setiap centroid (misalnya

menggunakan Euclidean Distance) 4.Tentukan keanggotaan setiap centroid berdasarkan jarak terdekat

dari data ke centroid 5.Update koordinat dari masing-masing centroid 6. Kembali ke no 3, iterasi berhenti jika sudah tidak ada perubahan

keanggotaan centroid

13

Cara kerja k-means

14

Misalnya akan dilakukan pengelompokan pelanggan berdasarkan “Age” dan “Income”

Cara kerja k-means (langkah ke-1)

Misalnya data akan dikelompokkan menjadi 3 klaster, maka ditetapkan nilai k = 3

15

Cara kerja k-means (langkah ke-2)

Karena k = 3, maka ada 3 titik koordinat awal centroid yang harus ditentukan secara acak, misalnya:

16

Cara kerja k-means (langkah ke-3)

Hitung jarak (distance) dari setiap data ke setiap centroid. Misalnya: • jarak dari data ke c1 adalah d(p1,c1), d(p2,c1), d(p3,c1) …

• Jarak dari data ke c2 adalah d(p1,c2), d(p2,c2), d(p3,c2) …

• Jarak dari data ke c3 adalah d(p1,c3), d(p2,c3), d(p3,c3) …

17

Cara kerja k-means (langkah ke-4) Tetapkan keanggotaan setiap centroid • Data yang memiliki jarak terdekat ke suatu centroid, ditetapkan menjadi anggota

centroid tersebut.

18

Cara kerja k-means (langkah ke-5)

Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah-tengah anggotanya)

19

Koordinat baru centroid = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

Cara kerja k-means (perulangan)

• Karena koordinat centroid berpindah, maka ulangi kembali langkat ke-3 sampai ke-5.

• Iterasi berhenti jika tidak ada lagi anggota centroid yang pindah ke centroid lain (artinya koordinat centroid tidak berubah lagi)

• Pengelompokan selesai.

20

Contoh penggunaan k-means

Misalkan ada 4 macam obat yang memiliki dua atribute (weight dan pH). Tujuan: mengelompokkan obat ini menjadi 2 klaster obat

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4 A B

C

D

21

Contoh penggunaan k-means (langkah ke-1)

Karena 4 macam obat ini akan dikelompokkan menjadi 2 klaster, maka ditetapkan nilai k = 2

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4 A B

C

D

22

Contoh penggunaan k-means (langkah ke-2)

Karena k = 2, maka ada 2 titik koordinat awal centroid yang harus ditentukan secara acak, misalnya: c1=(1,1) dan c2 = (2,1) (Kebetulan sama dengan koordinat A dan B)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

23

A B

C

D

C

D

A B

Contoh penggunaan k-means (langkah ke-3)

Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1,1) dan c2 = (2,1)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

24

Hitung distance (d): d(A,c1) = d(A,c2) =

d(B,c1) = d(B,c2) =

d(C,c1) = d(C,c2) =

d(D,c1) = d(D,c2) =

Tugas No. 1

Tugas No. 1

Contoh penggunaan k-means (langkah ke-4)

Tetapkan keanggotaan setiap centroid berdasarkan jarak terdekat dari data ke centroid

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

25

Hitung distance (d): d(A,c1) = d(A,c2) =

d(B,c1) = d(B,c2) =

d(C,c1) = d(C,c2) =

d(D,c1) = d(D,c2) =

Berdasarkan jarak terdekat: A -> c1 B, C, D -> c2

Contoh penggunaan k-means (langkah ke-5)

Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah- tengah anggotanya)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

26

c1: (1,1) => (1,1)

c2: (2,1) => (3.67,2.67)

c2 = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

Contoh penggunaan k-means (ulangi langkah ke-3)

Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1,1) dan c2 = (3.67,2.67)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

27

Hitung distance (d): d(A,c1) = d(A,c2) =

d(B,c1) = d(B,c2) =

d(C,c1) = d(C,c2) =

d(D,c1) = d(D,c2) =

Tugas No. 2

Tugas No. 2

Contoh penggunaan k-means (ulangi langkah ke-4)

Tetapkan keanggotaan setiap centroid berdasarkan jarak terdekat dari data ke centroid

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

28

Hitung distance (d): d(A,c1) = d(A,c2) =

d(B,c1) = d(B,c2) =

d(C,c1) = d(C,c2) =

d(D,c1) = d(D,c2) =

Berdasarkan jarak terdekat: A, B -> c1 (B pindah ke c1) C, D -> c2

Contoh penggunaan k-means (ulangi langkah ke-5)

Hitung ulang koordinat setiap centroid sehingga centroid akan berpindah ke titik pusat klaster (berada ditengah- tengah anggotanya)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

29

c = (rata-rata nilai sumbu x, rata-rata nilai sumbu y)

) 2

1 3 ,

2

1 4(

2

43 ,

2

54

)1 , 2

1 1(

2

11 ,

2

21

2

1

 

  

  

 

  

  

c

c

Contoh penggunaan k-means (ulangi langkah ke-3)

Hitung jarak (distance) dari setiap data ke setiap centroid menggunakan Euclidean Distance. Koordinat centroid: c1=(1.5,1) dan c2 = (4.5,3.5)

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

30

Hitung distance (d): d(A,c1) = d(A,c2) =

d(B,c1) = d(B,c2) =

d(C,c1) = d(C,c2) =

d(D,c1) = d(D,c2) =

Tugas No. 3

Tugas No. 3