Algoritma Cluster

Posted: March 30, 2009 in Materi Kuliah, Pengantar Teknik Informatika

ALGORITMA CLUSTERING
Algoritma clustering merupakan algoritma pengelompokkan sejumlah data ( N ) menjadi kelompok – kelompok data tertentu ( cluster ). Objek data yang terletak didalam satu cluster harus mempunyai kemiripan. Sedangkan yang tidak berada didalam satu cluster tidak mempunyai kemiripan.
Jumlah kemungkinan peng-clusteran – an. Misalnya, data X dimana :

X = {x1,x2,……….,xn}

Rumus yang digunakan untuk menentukan jumlah cluster adalah :

S(N,m) = (-1)m-1 iN

Beberapa contoh penerapan rumus diatas diantaranya :

S(15,3) = 2375101
S(20,4) = 45232115901
S(100,5) = 1068

Berdasarkan penjelasan diatas, coba bayangkan suatu pecahan kecil clustering X dan kemudian menentukan suatu clustering yang pantas diantara semuanya. Yang sering menjadi pertanyaan adalah pecahan clustering yang mana yang akan dipertimbangkan untuk dipilih. Kemudian pecahan clustering yang seperti apa yang dikatakan pantas.
Semua persoalan diatas dapat dijawab tergantung terhadap algoritma clustering tertentu dan criteria tertentu yang diterapkan.

PENGELOMPOKAN ALGORITMA CLUSTERING
Kategori pengelompokan algoritma clustering yang utama adalah sebagai berikut :
1.Sekuensial Clustering
Sekuensial clustering merupakan suatu teknik clustering yang menghasilkan satu clustering tunggal. Hasil akhir clustering ini biasanya ditentukan oleh permintaan vector yang terdapat didalam algoritma.
2.Hierarki Clustering
Metode ini digunakan apabila belum ada informasi tentang jumlah kelompok. Metode ini juga disebut sebagai metode iterative clustering dengan menggunakan hasil clustering yang sebelumnya (nested clustering). Seperti yang disebutkan diatas algoritma clustering mengelompokkan sejumlah objek atau data berdasarkan kemiripan. Dalam hierarki clustering ini, hasil clustering pada level 1 akan di-cluster lagi dengan cluster yang lain berdasarkan kemiripan yang terdapat pada cluster yang dihasilkan pada clustering level 1.
Hierarki Clustering dapat dikelompokkan kembali menjadi :
-Agglomerative
Agglomerative clustering merupakan suatu teknik hierarki clustering yang menghasilkan suatu rangkaian penurunan jumlah cluster pada setiap tahapan. Clustering yang terdapat pada setiap tahapan diperoleh dari tahapan sebelumnya dengan cara menggabungkan 2 cluster yang mempunyai kemiripan.
Agglomerative clustering dapat dilakukan dengan menggunakan 2 cara yaitu : teori matriks (matrix theory) dan teori grafik (graph theory).
-Devisive
Algoritma devisive berkebalikan arah dengan metode agglomerative dimana algoritma ini menghasilkan suatu rangkain peningkatan jumlah cluster pada setiap tahapan. Clustering yang terdapat pada setiap tahapan diperoleh dari tahapan sebelumnya dengan cara memecah suatu cluster tunggal menjadi 2 bagian.
– Jenis teknik clustering yang lainnya merupakan kombinasi dari teknik – teknik
clustering yang telah dijelaskan diatas. Misalnya : Algoritma Chameleon.

CLUSTERING ALGORITHM BASED ON COST FUNCTION OPTIMIZATION
Algoritma clustering yang didasarkan pada cost function optimization merupakan kategori algoritma clustering dimana tingkat kepantasan diukur berdasarkan cost function. Algoritma kategori ini juga biasa disebut iterative function optimization schemes. Yang tergolong kedalam kategori ini adalah :
-Hard Clustering
Setiap titik merupakan kepunyaan dari suatu cluster tunggal. Pembagian vector – vector ke masing – masing cluster dilakukan secara optimal tergantung kepada optimalisasi kriteria yang digunakan. Yang termasuk kedalamnya adalah :
1.Basic hard clustering algorithms, misalnya k-means
2.k-medoids algorithms
3.Mixture decomposition
4.Branch and bound
5.Simulated annealing
6.Deterministic annealing
7.Boundary detection
8.Mode seeking
9.Genetic Clustering algorithms
-Fuzzy clustering
Merupakan suatu algoritma clustering dimana setiap titik merupakan kepunyaan lebih dari satu cluster secara bersama.
-Possibilistic clustering
Merupakan suatu algoritma clustering dimana setiap titik yang merupakan kepunyaan suatu cluster didasarkan kepada kemungkinan ( possibility ). Dalam algoritma ini mengharuskan menghitung kemungkinan untuk suatu sifat vector untuk dijadikan kepunyaan suatu cluster.

Metode lain yang digunakan dalam algoritma clustering diantaranya :
-Algoritma yang didasarkan pada teori grafik ( graph theory ), misalnya Minimum Spanning Tree, Regions of Influence, Directed Trees.
-Competitive Learning Algorithm
Merupakan skema kompetitif dasar Kohonen self organizing maps. Algoritma ini merupakan algoritma iterative yang tidak mempunyai biaya fungsi. Algoritma ini menghasilkan beberapa clustering dan mengumpul menjadi satu cluster yang pantas, berdasarkan jarak suatu metrik.
-Subspace Clustering Algorithm
-Binary Morphology Clustering Algorithms.

SEQUENTIAL CLUSTERING ALGORITHMS
Sifat umum yang diberikan oleh algoritma ini adalah :
-Terdapat satu atau lebih sedikit alur atau jalan data yang dibutuhkan
-Jumlah dari cluster – cluster tidak diketahui sebelumnya, kecuali kemungkinan dari suatu upper bound, q.
-Cluster – cluster didefinisikan dengan bantuan dari : suatu pendefinisian jarak satu titik dari suatu cluster, d(x,C). Dan dengan bantuan suatu threshold yang berasosiasi dengan jarak.

BASIC SEQUENTIAL CLUSTERING ALGORITHM (BSAS)
Pertama kita menganggap semua vector – vector disajikan ke algoritma hanya sekali saja. Jumlah dari cluster – cluster tidak diketahui sebelumnya. Kenyataannya suatu cluster dihasilkan karena pengembangan algoritma.
d(x,C) merupakan jarak antara suatu sifat vector x dengan suatu cluster C yang didasarkan kepada ketidaksamaan. Parameter yang ditentukan oleh user yang dibutuhkan dalam skema algoritma adalah threshold ketidaksamaan dan nilai maksimum yang untuk jumlah cluster – cluster, q.
Ide utama dari algoritma ini adalah setiap vekto – vector yang baru dipertimbangkan apakah vector – vector tersebut dibagikan kedalam cluster yang telah ada atau dimasukkan kedalam cluster yang baru dibuat, tergantung dari jaraknya terhadap yang telah dibuat sebelumnya.

Algoritma BSAS dapat dinyatakan sebagai berikut :

m=1 {jumlah cluster}
Cm={x1}
For i=2 to N
Find Ck: d(xi,Ck)=min1£j£md(xi,Cj)
If (d(xi,Ck)>Θ) AND (m<q) then
m=m+1
Cm={xi}
Else
Ck=CkÈ{xi}
End {if}
End {for}
Pemilihan d(x,C) yang berbeda mengarah ke algoritma yang berbeda dan beberapa ukuran yang diperkenalkan pada bab 11 dapat dipakai dalam hal ini.
Ketika mean vector mc digunakan sebagai representasi cluster C dengan jumlah elemen nc, peng-update-an kecil dari suatu vector x menjadi sebagai berikut :

mCnew=(nC mC + x) / (nC+1)

Permintaan penyajian data didalam algoritma mempunyai peranan yang penting terhadap hasil – hasil clustering. Perbedaan permintaan penyajian data memungkinkan menghasilkan clustering yang berbeda juga, dalam hal jumlah dari cluster – cluster. Faktor lain yang menentukan hasil clustering adalah pemilihan threshold . Nilai threshold ini secara langsung mempengaruhi jumlah cluster yang dibentuk dengan menggunakan BSAS. Jika nilai terlalu kecil cluster – cluster yang tidak dibutuhkan akan dibuat. Sebaliknya jika nilai terlalu besar maka cluster – cluster yang tepat akan diciptakan.
Skema BSAS dapat digunakan dengan menggunakan kemiripan sebagai pengganti ukuran ketidakmiripan dengan menggunakan modifikasi yang sesuai.yaitu operator min diganti dengan menggunakan operator max. Didalam BSAS pemilihan untuk suatu vector x dilakukan sebelum formasi cluster akhir. Selain itu BSAS juga menunjukkan suatu jalur data tunggal, dengan kompleksitas O(N). Jika cluster – cluster direpresentasikan dengan perwakilan titik, maka cluster – cluster terlihat begitu rapat.

Estimating the number of clusters in the data set
Pada bagian ini dibahas mengenai suatu metode sederhana untuk menentukan jumlah dari cluster – cluster. Metode tersebut cocok untuk BSAS, sama seperti algoritma-algoritma yang lainnya yang digunakan untuk menentukan jumlah dari cluster – cluster dimana jumlah dari cluster – cluster tidak diperlukan sebagai suatu parameter input. BSAS ( ) menunjukkan algoritma BSAS dengan menggunakan suatu threshold ketidakmiripan tertentu .

Untuk = a sampai b tahapan c
-Jalankan BSAS( ) sebanyak s kali, setiap langkah sajikan data dengan permintaan yang berbeda.
-Kurangi jumlah dari cluster – cluster m , karena merupakan angka yang paling sering dihasilkan dari BSAS( ) sebanyak s kali.

Berikutnya .
Nilai – nilai a dan b merupakan tingkat ketidakmiripan pada level minimum dan maksimum diantara semua pasangan vektor X. Pemilihan c secara langsung dipengaruhi oleh pemilihan d(x,C). Semakin jauh nilai s diperhatikan, semakin besar nilai s semakin besar sample statistic maka semakin akurat tingkat akurasi yang dihasilkan. Selanjutnya membuat plot jumlah cluster- cluster terhadap . Plot ini mempunyai sejumlah bidang datar. Kita mengurangi jumlah cluster – cluster karena jumlah yang sesuai dengan bidang datar terluas.

MBSAS, suatu modifikasi dari BSAS
Seperti yang telah dinyatakan sebelumnya ide pokok dibalik algoritma BSAS adalah setiap vektor input x dibagikan ke satu cluster yang telah dibuat atau ke cluster yang baru terbentuk. Oleh karena itu, suatu pemilihan untuk vektor x diperoleh terlebih daripada formasi akhir cluster, yang ditentukan setelah semua vektor dimunculkan. Penyempurnaan dari BSAS berikut ini, kemudian disebut modified BSAS ( MBSAS) untuk mengatasi kekurangan pada algoritma BSAS. Untuk melakukan itu semua kita vektor X harus disajikan sebanyak 2 kali. Proses algoritma ini dilakukan dalam 2 fase. Fase pertama disebut dengan fase penentuan cluster ( cluster determination phase) dimana pembagian beberapa vektor – vektor X harus disajikan kedalam cluster – cluster. Sama seperti BSAS dengan pengecualian dimana tidak ada vektor yang dibagikan kedalam suatu cluster yang telah dibentuk. Pada akhir dari tahapan ini, setiap cluster hanya terdiri dari satu elemen tunggal. Fase kedua disebut fase penggolongan pola ( pattern classification phase) dimana selam fase ini, vektor – vektor yang tidak dibagikan kedalam cluster disajikan selama satu waktu ke algoritma dan dibagikan kedalam cluster yang paling dekat.
Didalam MBSAS, pemilihan untuk suatu vektor x dilakukan selama fase pattern classification yang diperoleh dengan cara mengambil kedalam seluruh anggota semua cluster. MBSAS termasuk sensitive terhadap permintaan penyajian dari vektor – vektor. Selain itu juga MBSAS membutuhkan 2 jalur data dengan kompleksitas O(N). MBSAS dapat digunakan ketika parameter kemiripan digunakan.

Algoritma Maxmin
Misalkan w merupakan kumpulan semua titik – titik yang telah dipilih untu membentuk cluster – cluster keatas di tahapan iterasi saat ini. Formasi dari cluster – clusteri dijabarkan sebagai berikut :

Untuk setiap x X-W menentukan dx = minzÎ W d(x,z)
Kemudian menentukan y dimana dy = maxxÎ X-Wdx

If
dy lebih besar dari threshold yang ditentukan sebelumnya dan kemudian vektor ini membentuk suatu cluster baru.
Else
Fase penentuan cluster dengan algoritma penghilangan.
End If

Setelah formasi cluster – cluster, setiap vektor yang tidak di bagikan di bagikan ke cluster terdekat.

Algoritma maxmin merupakan algoritma yang lebih diinginkan secara komputasi daripada MBSAS. Walaupun algoritma tersebut diharapkan menghasilkan hasil clustering yang lebih baik.

Refinement Stages
Pada semua algoritma – algoritma sebelumnya, memungkinkan 2 cluster yang dihasilkan terletak saling berdekatan sekali, kemudian memungkinkan juga untuk menggabung keduanya menjadi 1 cluster. Salah satu cara untuk mengatasi masalah ini adalah dengan menjalankan menjalankan prosedur merging berikut ini, setelah penghapusan skema sebelumnya.
Suatu prosedur merging sederhana :
Temukan Ci, Cj (i<j) dimana d(Ci,Cj)=mink,r=1,…,m,k≠rd(Ck,Cr) (A)
If d(Ci,Cj)£M1 then
– Merge Ci, Cj menjadi Ci dan hapus Cj
– Jika penting, update representative cluster Ci
– Gantilah nama cluster Cj+1,…,Cm menjadi Cj,…,Cm-1
– m = m -1
– Balik ke langkah awal (A)
Else
– Stop
End {if}

M1 merupakan parameter yang didefinisikan oleh user yang menghitung kedekatan antara kedua cluster Ci dan Cj.

Kekurangan lainnya dari sequential diagram adalah sensitifitas terhadap permintaan penyajian vektor – vektor. Misalnya dengan menggunakan algoritam BSAS, x2 dibagikan kepada cluster pertama, C1 dan setelah penghapusan algoritma cluster – cluster dibentuk. Kemudian memungkinkan untuk x2 untuk lebih dekat ke suatu cluster yang berbeda dari C1. Bagaimanapun juga, tidak terdapat cara bagi x2 untuk pindah ke cluster yang terdekat yang dibagikan sekali terhadap yang lainnya. Suatu cara untuk mengatasi masalah ini dengan menggunakan algoritam reassignment procedure berikut :

For i = 1 to N
– Temukan Cj dimana, d(xi,Cj)=min k=1,…,md(xi,Ck)
– b(i) = j
End { for }
For j =1 to m
-Cj={xiÎX: b(i)=j}
-Jika perlu, update representative
End {for}

Didalam procedure diatas, b(i) menunjukkan yang terdekat terhadap cluster xi.
Prosedur ini dapat digunakan setelah penghapusan algoritma.atau jika prosedur merging juga digunakan setelah penghapusan merging prosedur.

Seperti yang telah dijelaskan sebelumnya hasil dari BSAS dan MBSAS sangat tergantung sekali terhadap permintaan vektor – vector yang disajikan dalam algoritma dan juga terhadap nilai Θ . Pemilihan Θ yang tidak sesuai dapat menghasilkan hasil clustering yang tidak berguna. Salah satu cara untuk mengatasi masalah tersebut dengan mendefinisikan suatu bidang gray. Hal ini dapat dilakukan dengan menggunakan 2 threshold.
Skema Sequensial dua threshold ( TTSAS)
-Formasi dari cluster – cluster, sama baiknya terhadap pembagian vektor – vektor ke cluster – cluster yang diungkapkan secara langsung ( seperti BSAS dan tidak seperti MBSAS)
-Dua threshold Θ1 dan Θ2 (Θ1<Θ2) yang digunakan
-Ide utama dari TTSAS sebagai berikut :
-Jika jarak d(x,C) terhadap x dari clusternya yang terdekat, C, lebih besar dari Θ2 maka suatu cluster baru direpresentasikan oleh x yang dibentuk.
-Jika d(x,C)= 2)
TTSAS bukan merupakan algoritma yang sensitive terhadap permintaan penyajian data, bila dibandingkan dengan BSAS.

Sumber : http://pola.its-sby.edu

Comments
  1. adi prasetyo says:

    ada penjelasannya tentang Algoritma Chameleon

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s