KLASTERING DENGAN METODE K-MEANS

Partitional clustering

PENDAHULUAN

K-mean merupakan teknik klastering yang paling umumdan sederhana.

Tujuan klastering ini adalah mengelompokkan obyek kedalam k klaster/kelompok.

Nilai k harus ditentukan terlebih dahulu (berbedadengan hierarchical clustering).

Ukuran ketidakmiripan masih tetap digunakan untukmengelompokkan obyek yang ada.

ALGORITMA K-MEANS

Secara ringkas algoritma K-means adalah

sebagai berikut:

1. Pilih jumlah klaster k

2. Inisialisasi k pusat klaster

3. Tempatkan setiap data/obyek ke klaster terdekat

4. Perhitungan kembali pusat klaster

5. Ulangi langkah 3 dengan memakai pusat klaster

yang baru. Jika pusat klaster tidak berubah lagi

maka proses pengklasteran dihentikan.

PENENTUAN JUMLAH DAN PUSAT KLASTER

Inisialisasi atau penentuan nilai awal pusat klasterdapat dilakukan dengan berbagai macam cara, antaralain: Pemberian nilai secara random

Pengambilan sampel awal dari data

Penentuan nilai awal hasil dari klaster hirarki denganjumlah klaster yang sesuai dengan penentuan awal.

Dalam hal ini biasanya user memiliki pertimbanganintuitif karena dia memiliki informasi awal tentang obyekyang sedang dipelajari, termasuk jumlah klaster yang paling tepat.

PENEMPATAN OBYEK KE DALAM KLASTER

Penempatan obyek ke dalam klaster didasarkanpada kedekatannya dengan pusat klaster

Dalam tahap ini perlu dihitung jarak tiap data ketiap pusat klaster yang telah ditentukan.

Jarak paling dekat antara suatu data denganpusat klaster tertentu merupakan hal penentudata tersebut akan masuk klaster yang mana.

PERHITUNGAN KEMBALI PUSAT KLASTER

Pusat klaster ditentukan kembali dengan cara dihitung nilai rata-rata

data/obyek dalam klaster tertentu.

Jika dikehendaki dapat pula digunakan perhitungan median dari anggota

klaster yang dimaksud

Mean bukan satu-satunya ukuran yang bisa dipakai

Pada kasus tertentu pemakaian median memberikan hasil yang lebih baik.

Karena median tidak sensitif terhadap data outlier (data yang terletak jauh

dari yang lain, meskipun dalam satu klaster - pencilan)

Contoh:

Mean dari 1, 3, 5, 7, 9 adalah 5

Mean dari 1, 3, 5, 7, 1009 adalah 205

Median dari 1, 3, 5, 7, 1009 adalah 5

KONVERGENSI ATAU TERMINASI

Untuk mengentikan proses iterasi dalam mencaripengklasteran yang optimum, maka digunakan ratio perbandingan antara nilai kovarian antar klaster dan di dalamklaster:

Dimana, m nilai pusat dari setiap cluster, p merepresentasikan setiap titik data

Semakin besar nilai ratio, semakin tepat klaster yg terbentuk

CONTOH

Data points untuk k-means

Maka, dengan algoritma k-means:1. Menanyakan user berapa jumlah klaster k (misal k=2)

2. Menentukan secara random untuk inisialisasi lokasi pusatklaster; m1=(1,1) dan m2=(2,1)

3. Untuk setiap record dicari nilai pusat klaster terdekat, dengan menghitung jarak tiap2 titik terhadap pusatklaster.

1ST ITERATION

Sehingga dengan kedekatannya

mengindikasikan ke klaster mana

Expectation: increasing for the ratio

2ND ITERATION

4. Mengupdate nilai titik pusat cluster -1& 2 dengan

mean dari setiap klaster yg terbentuk:

m1’=[(1+1+1)/3, (3+2+1)/3]= (1, 2)

m2’=[(3+4+5+4+2)/5, (3+3+3+2+1)/5]=(3.6, 2.4)

5. Kemudian dihitung jarak tiap2 titik dengan pusat yg

baru

HASIL PERHITUNGAN ITERASI KE 2

Catatan : untuk point h pada gambar masuk C2, semestinya

masuk C1

Jadi anggota dari cluster 1 dan cluster 2 sekarang menjadi

sama-sama 4

C1

Sehingga diperoleh jumlah error kuadrat dari pusatklaster

Dan ratio:

Karena nilainya lbh besar dari sebelumnya, shgterjadi peningkatan

3RD ITERATION

Menemukan kembali lokasi pusat klaster dengan

mengupdatenya dari mean:

m1’’=[(1+1+1+2)/4,(3+2+1+1)/4]=(1.25, 1.75)

m2’’=[(3+4+5+4)/4,(3+3+3+2)/4]=(4,2.75)

Kemudian dicari jaraknya tiap2 titik terhadap titik

pusat klaster yang baru

Karena nilainya lebih besar dari

sebelumnya,maka dilakukan

iterasi lagi

PENGHENTIAN ITERASI

Jika tidak juga ditemukan pusat kluster yang sama dengan

iterasi sebelumnya, maka penghentian iterasi bisa dilakukan

dengan :

1. menggunakan nilai threshold. Iterasi dihentikan jika nilai deltanya <

threshold. 2. menggunakan ratio perbandingan antara nilai kovarian antar klaster

dan di dalam klaster:

Jika rasionya > dari rasio maka iterasi dihentikan

Kelebihan

Relatively efficient: O(tkn), dimana n adalah # objects, k adalah # clusters, dan t merupakan # iterations. Umumnya, k, t << n.

Biasanya berhenti pada nilai optimum lokal (local optimum). Nilaiglobal optimum dapat ditentukan dengan menggunakan teknikseperti deterministic annealing dan genetic algorithms

Kekurangan

Dapat diterapkan hanya saat nilai mean telah ditentukan, bagaimana untuk data-data bersifat kategori?

Perlu ditentukan k, jumlah klaster

Tidak dapat menangani noisy data dan outliers

Tidak tepat untuk membentuk klaster dengan data non-convex shapes

LATIHAN SOAL

Given the samples X1 = {1, 0}, X2 = {0, 1}, X3 =

{2, 1}, and X4 = {3, 3}, suppose that the

samples are randomly clustered into two

clusters C1 = {X1, X3} and C2 = {X2, X4}.

Apply one iteration of the K-means partitional-

clustering algorithm, and find a new distribution of

samples in clusters. What are the new centroids?

How can you prove that the new distribution of

samples is better than the initial one?