algoritma clustering - universitas hasanuddinunhas.ac.id/amil/s1tif/dm2020/07 algoritma...

Algoritma ClusteringAmil 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 memilikiberbedaan 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 dimanasetiap anggota cluster tidak terjadi overlap. Artinya sebuah object data hanyaakan 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 lebihdari satu cluster.

Sehingga penggambaran cluster dalam bentuk hierarchical tree atau dendogram

6

Partitional Clustering

A Partitional Clustering

7

Hierarchical Clustering

p4

p1p3

p2

p4

p1 p3

p2

p4p1 p2 p3

p4p1 p2 p3

diclustermenjadi

8

Euclidean Distance

Contoh

A(3,2)

B(10,6)

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

𝑑𝐸 𝐵, 𝐴 = 8.06

𝑑𝐸 𝐵, 𝐴 = 49 + 16

𝑑𝐸 𝐵, 𝐴 = 65

9

Algoritma K-MeansAlgoritma 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-MeansContoh 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 centroid5.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 pengelompokanpelanggan berdasarkan “Age” dan “Income”

Cara kerja k-means (langkah ke-1)

Misalnya data akandikelompokkan menjadi 3 klaster, maka ditetapkannilai k = 3

15

Cara kerja k-means (langkah ke-2)

Karena k = 3, maka ada 3 titikkoordinat 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 berpindahke 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 kembalilangkat ke-3 sampai ke-5.

• Iterasi berhenti jika tidak ada lagianggota centroid yang pindah kecentroid lain (artinya koordinatcentroid 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 harusditentukan 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 jarakterdekat 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 -> c1B, 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 jarakterdekat 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

13 ,

2

14(

2

43 ,

2

54

)1 ,2

11(

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

Hasil k-means (k = 2)

Tuliskan nilai distance yang menunjukkan tidak terjadinyaperpindahan anggota centroid sehingga proses pengelompokan selesai.

Medicine Weight pH-Index

A 1 1

B 2 1

C 4 3

D 5 4

31

c1=(1,1) c2 = (3.67,2.67)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) =

c1=(1.5,1) c2 = (4.5,3.5)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) =

c1=(1,1); c2 = (3.67,2.67) c1=(1.5,1); c2 = (4.5,3.5)

Hasil k-means (k = 2)

Tugas No. 4

Tugas No. 4

Evaluasi Performa K-Means

• Evaluasi performa K-Means Clustering dapat menggunakan Sum of Square Error (SSE). Ide utama dari penggunaan SSE ini adalahmengukur keseragaman antar data dalam satu cluster

• Keseragaman diukur berdasarkan error/jarak/distance antara setiap data dengan centroidnya. Semakin seragam data-data dalam sebuahcluster, semakin kecil jarak antara setiap data dengan centroidnya

• Selanjutnya error disetiap cluster dijumlahkan untuk semua cluster (Sum of Square Error/SSE). Semakin kecil nilai SSE maka semakin bagus hasil clusteringnya

32

Evaluasi Performa K-Means

33

SSE dan Jumlah K

• Berdasarkan performa SSE, clustering akan makin baik bila memiliki nilai SSE yang kecil

• Nilai SSE akan mendekati 0 seiring dengan bertambahnya jumlah K. SSE akan bernilai 0 bila K samadengan jumlah data dalam data set, karena setiap data adalah cluster tunggal dengan anggotahanya dirinya sendiri sekaligus sebagai centroid.

Jumlah K

SSE

34

Elbow Method

• Gambar kiri terlihat jelas menunjukkan bahwa elbow terletak pada K=3 sehingga jumlah cluster terbaik untuk data set adalah 3 cluster

• Tetapi tidak selamanya Elbow Method dapat digunakan untuk menentukan nilai K yang optimum. Pada gambar kanan terlihat bahwa kurva sangat landai sehingga sulit untukmenentukan dimana letak elbow nya

35