Clustering Menggunakan K-means: Oleh: Sorikhi

Clustering Menggunakan K-means Oleh: Sorikhi

Outline • Pendahuluan • Algoritma K-means • Contoh • Partisi K-means • Demo • Masalah • Penutup

Pendahuluan Pendekatan Clustering • Merupakan pendekatan clustering yang mempartisi / membagi dataset training secara iterative • Partisi akan menghasilkan beberapa cluster (jumlah cluster ditentukan terlebih dahulu) • Optimal partisi akan didapatkan dengan meminimalkan jarak masing-masing cluster

E    xCk d (x, mk ) K k 1

2

N

Contoh, Euclidean distance d 2 ( x, mk )   (xn m kn ) 2 n 1

Pendahuluan • Algoritma K-means merupakan metode heuristic dimana masing-masing cluster direpresentasikan oleh pusat cluster dan algoritma akan mengerucut ke centroid masing-masing cluster • Algoritma K-means merupakan metode partisi paling sederhana yang digunakan untuk analisa clustering dan digunakan secara luas dalam aplikasi data mining

Algoritma K-means • Jika jumlah K cluster diketahui, maka algoritma Kmeans dilakukan melalui tiga tahapan setelah inisialisasi Inisialisasi: memilih seed point secara acak 1. Tugaskan masing-masing objek ke cluster dengan nilai seed point terdekat 2. Hitung seed point baru sebagai centroid cluster (centroid adalah pusat, titik rata-rata cluster) 3. Kembali ke langkah 1, berhenti jika tidak ada lagi perubahan

Contoh Problem • Terdapat 4 macam obat yang memiliki dua atribut (pH dan indeks bobot), tujuan kita adalah mengelompokkan objek dalam K=2 kelompok obat Obat

Bobot

D

pH

A

1

1

B

2

1

C

4

3

D

5

4

C

A

B

Contoh • Step 1: Gunakan inisial seed point untuk partisi c1  A, c2  B

D

Euclidean distance

C

d( D, c1 )  ( 5  1)2  ( 4  1)2  5 A

B

d( D, c2 )  ( 5  2)2  ( 4  1)2  4.24

Tugaskan masing-masing objek Ke cluster dengan nilai seed point terdekat

Contoh • Step 2: Hitung centroid baru dari partisi Setelah mengetahui anggota masing-masing cluster, sekarang hitung centroid baru masingmasing kelompok

c1  (1, 1) 2  4  5 1 3  4 c 2   ,  3 3   11 8 ( , ) 3 3

Contoh • Step 2: Perbarui keanggotaan berdasarkan centroid baru Hitung jarak masing-masing objek terhadap centroid baru

Tentukan keanggotaan masingmasing objek

Contoh • Step 3: Ulangi hingga mengerucut / convergence Setelah mengetahui anggota masing-masing cluster, sekarang hitung centroid baru masingmasing kelompok

1  1 2 11 c1   ,  ( 1 , 1)  2  2  2 1 1 45 34 c2   ,  ( 4 , 3 )  2  2 2  2

Contoh • Step 3: Ulangi hingga mengerucut / convergence Hitung jarak masing-masing objek terhadap centroid baru

Berhenti karena keanggotaan baru tiap cluster tidak mengalami perubahan

Latihan • Dari data obat, gunakan K-means dengan perhitungan jarak menggunakan Manhattan distance, K = 2 dan seed point C1 = A dan C2 = C. Jawab pertanyaan berikut: 1. Berapa langkah dibutuhkan untuk mencapai convergence? 2. Apa saja keanggotaan masing-masing cluster setelah convergence? 3. Apa saja centroid masing-masing cluster setelah convergence? Obat

Bobot

pH

A

1

1

B

2

1

C

4

3

D

5

4

D C

A

B

Partisi K-means Ketika K centroid telah ditentukan, maka akan mempartisi keseluruhan data ke dalam K subspace untuk membentuk sebuah partisi Jumlah partisi menggunakan Voronoi Diagram Mengubah posisi centroid akan menimbulkan partisi baru

Demo

K-means Demo

Masalah • Kompleksitas komputasi

• O(tKn), dimana n adalah jumlah objek, K jumlah cluster, dan t jumlah iterasi. Normalnya, K, t << n

• Local optimum

• Sensitif terhadap seed point awal • Mengerucut ke local optimum: kemungkinan bukan solusi yang diinginkan

• Masalah lain

• Harus ditentukan K dengan seksama • Tidak mampu menangani noise pada data dan outlier • Tidak cocok untuk menentukan cluster dengan bentuk nonconvex • Hanya dapat diterapkan hanya jika mean/nilai rata-rata dapat ditentukan, bagaimana jika data kategorikal? • Bagaimana cara menghitung performance K-mean?

Penutup • Algoritma K-means merupakan algoritma yang sangat sederhana dan metode terkenal untuk analisa clustering • Performancenya ditentukan oleh inisialisasi dan penggunaan pengukuran jarak yang tepat • Terdapat beberapa variasi K-means untuk mengatasi kelemahannya • • • •

K-Medoid: tahan terhadap noise dan outlier K-Modes: digunakan untuk clustering data kategorikal CLARA: digunakan pada data set dengan ukuran besar Mixture model (algoritma EM): menangani cluster tak pasti