KLASTERISASI DATA IRIS MENGGUNAKAN METODE BERBASIS ARTIFICIAL BEE COLONY DAN K-HARMONIC MEANS

Prosiding Seminar Nasional Manajemen Teknologi XIV Program Studi MMT-ITS, Surabaya 23 Juli 2011

KLASTERISASI DATA IRIS MENGGUNAKAN METODE BERBASIS ARTIFICIAL BEE COLONY DAN K-HARMONIC MEANS I Made Widiartha, Agus Zainal Arifin, Anny Yuniarti Jurusan Teknik Informatika, Fakultas Teknologi Informasi, ITS email : [email protected]

ABSTRAK Pengelompokan data ke dalam beberapa klaster dapat dilakukan dengan berbagai metode, salah satunya menggunakan K-Means Clustering (KM). KM memiliki kelemahan yaitu dari sisi sensitifitas hasil klaster pada inisialisasi awal titik pusat klaster dan adanya kemungkinan hasil klaster merupakan lokal optimal. K-Harmonic Means (KHM) merupakan metode klasterisasi data yang menyempurnakan KM. Meskipun metode KHM dapat mengurangi masalah inisialisasi, namun dalam KHM masih terdapat kemungkinan terjadinya masalah lokal optimal. Salah satu cara untuk mengatasi permasalahan lokal optimal ini adalah dengan memanfaatkan suatu metode yang memiliki solusi global ke dalam metode KHM. Metode Artificial Bee Colony (ABC) merupakan suatu metode swarm yang berbasis pada perilaku mencari makan (foraging behavior) dari koloni lebah madu yang telah terbukti memiliki solusi global. Dalam penelitian ini diusulkan sebuah metode baru untuk klasterisasi data yang berbasis pada metode ABC dan KHM (ABC-KHM). Kinerja metode ABC-KHM ini telah dibandingkan dengan metode ABC dan KHM dengan menggunakan dataset iris. Dari hasil penelitian didapatkan hasil dimana metode ABC-KHM ini telah berhasil mengoptimalkan posisi titik pusat klaster yang mengarahkan hasil klaster menuju suatu solusi global. Kata kunci: K-Means Clustering, K-Harmonic Clustering, Artificial Bee Colony, ABCKHM.

PENDAHULUAN Klasterisasi data (clustering) adalah sebuah proses untuk mengelompokkan data kedalam beberapa klaster/kelompok sehingga data dalam satu klaster memiliki tingkat kemiripan yang maksimum dan data antar klaster memiliki kemiripan yang minimum [7]. Salah satu metode yang dapat digunakan dalam melakukan klasterisasi data adalah K-Means Clustering (KM). Metode KM ini memiliki kelemahan yaitu hasil klaster sangat sensitif dengan inisialisasi titik pusat awal dan sangat mudah terjebak pada lokal optimal [8]. Untuk mengatasi masalah yang terjadi pada inisialisasi titik pusat klaster, Zhang, Hsu, dan Dayal [10] mengusulkan sebuah metode baru yang diberi nama K-Harmonic Means (KHM) yang kemudian dimodifikasi oleh Hammerly dan Elkan [2]. Meskipun KHM dapat mengurangi masalah inisialisasi, namun dalam KHM masih terdapat kemungkinan terjadinya masalah lokal optimal [8]. Untuk mengatasi permasalahan lokal optimal ini maka diperlukan suatu metode yang memiliki kemampuan untuk menghindari kemungkinan adanya konvergensi terhadap lokal optimal. ISBN : 978-602-97491-3-7 C-26-1


Artificial Bee Colony (ABC) merupakan suatu metode yang mengadopsi perilaku mencari makan (foraging behavior) dari koloni lebah madu. Pada metode ini terdapat tiga jenis lebah yang dipakai yaitu lebah pekerja/employed bee, lebah penunggu/onlooker bee, dan lebah pengintai/scout [4]. Metode ABC telah terbukti memiliki kemampuan untuk menangani permasalahan lokal optimal dan memiliki kualitas yang lebih baik atau setara jika dibandingkan dengan metode sejenis lainnya seperti Algoritma Genetika, Particel Swarm Optimization, Differential Evolution, dan Evolution Stategies [6]. Dalam penelitian ini diusulkan sebuah metode baru untuk klasterisasi data yang berbasis pada metode ABC dan KHM (ABC-KHM). Perilaku lebah pada metode ABC digunakan untuk membantu KHM untuk dapat keluar dari lokal optimal sehingga metode ABC-KHM ini diharapkan mampu mengoptimalkan posisi titik pusat klaster yang mengarah pada solusi global optimal. Metode yang diusulkan ini diterapkan pada dataset iris. K-HARMONIC MEANS CLUSTERING KHM merupakan suatu metode klasterisasi data dimana klaster-klaster dibentuk dengan peyempurnaan secara iteratif berdasarkan letak titik pusat dari masing-masing klaster. Pada KHM, nilai fungsi tujuan dihasilkan dengan mencari total rata-rata harmonik dari seluruh titik data untuk jarak antara masing-masing titik data ke seluruh titik pusat klaster yang ada [9]. Adapun langkah-langkah Metode KHM adalah sebagai berikut [8] : 1. Inisialisasi posisi titik pusat klaster awal secara random 2. Hitung nilai fungsi tujuan dengan persamaan 1, dimana p adalah input parameter. Nilai p biasanya ≥ 2. K 1 i 1  p l 1 || x i  c l || N

KHM ( X , C )  

K

(1)

3. Untuk setiap data xi, hitung nilai keanggotaan m(cl|xi) untuk setiap titik pusat klaster cl berdasarkan persamaan : ` m ( cl | xi ) 

|| xi  cl ||  p  2 k

 || xi  cl ||  p  2

(2)

l 1

4. Untuk setiap data xi, hitung nilai bobot w(xi) berdasarkan persamaan K

w( xi ) 

 || xi  cl ||  p 2 l 1

 K || x  c ||  p   i  l  l 1 

2

(3)

5. Untuk setiap titik pusat cj, ulang kembali perhitungan untuk posisi titik pusat klaster dari semua data berdasarkan nilai keanggotaan dan bobot yang dimiliki tiap data. N

cl 

 m(cl | xi ).w( xi ).xi i 1 N

 m(cl | xi ).w( xi )

(4)

i 1

6. Ulangi langkah 2 sampai 5 sampai mendapatkan nilai fungsi tujuan yang tidak terdapat perubahan yang signifikan. ISBN : 978-602-97491-3-7 C-26-2


7. Tetapkan keanggotaan data xi pada suatu klaster dengan titik pusat klaster cj sesuai dengan nilai keanggotaan xi terhadap cj. ARTIFICIAL BEE COLONY Metode Artificial Bee Colony (ABC) merupakan sebuah metode yang diperkenalkan oleh Karaboga pada tahun 2005. Koloni lebah tiruan terdiri dari tiga kelompok yaitu lebah pekerja (employed bee), lebah penunggu (onlooker) dan lebah scout (penjelajah). Metode ABC ini dapat digambarkan seperti pada Gambar 1. Langkah pertama pada metode ABC ini adalah pengiriman lebah pekerja (yang berstatus scout) pada daerah pencarian untuk menghasilkan populasi awal yang didistribusikan secara random. Setelah inisialisasi, penentuan populasi dari posisi solusi berikutnya melalui siklus yang berulang, C = 1, 2, ... , MCN. Setelah semua lebah pekerja menyelesaikan proses pencarian, dilakukan penghitungan nilai fitness dari solusi yang dihasilkan (nilai nektar) dan lebah pekerja membagi informasi nektar dan informasi tentang posisi mereka dengan lebah penunggu di dancing area. Nilai fitness dapat dicari dengan menggunakan persamaan 5. fiti 

1 1  fi

(5)

Variabel fi merupakan nilai cost function dari solusi i. Lebah penunggu mengevaluasi informasi yang diambil dari semua lebah pekerja dan memilih sumber makanan dengan probabilitas yang sesuai jumlah nektarnya. Seperti kasus lebah pekerja, lebah penunggu juga menghasilkan modifikasi pada posisi sumber makanan (solusi) dalam memorinya dan memeriksa jumlah nektar dari kandidat sumber makanan (solusi) yang baru. Jika nilai nektar lebih tinggi dari sebelumnya, lebah akan mengingat posisi yang baru tersebut dan melupakan posisi yang lama. Lebah penunggu memilih sumber makanan berdasarkan pada nilai probabilitas pi dengan menggunakan metode roulette wheel selection [5]. Nilai pi ini dihitung melalui persamaan 6. pi 

fit i SN

 fit i

(6)

i 1

Dalam menghasilkan kandidat posisi makanan baru, ABC menggunakan persamaan 7. v ij  x ij   ij ( x ij  x kj )

(7)

Nilai k  {1, 2, ..., SN} dengan j  {1, 2, .., D} adalah indeks yang dipilih secara random. Meskipun k ditentukan secara random, namun k

Gambar 1. Metode ABC

ISBN : 978-602-97491-3-7 C-26-3


harus berbeda dari i.  ij adalah sebuah bilangan random antara [-1,1], yang mengontrol produksi posisi sumber makanan tetangga di sekitar xij Sumber makanan yang ditinggalkan oleh lebah pekerja, digantikan dengan sumber makanan baru oleh lebah scout. Dalam metode ABC, jika sebuah posisi sumber makanan tidak dapat ditingkatkan lebih lanjut melalui sejumlah siklus (cycle) yang telah ditetapkan, yang disebut dengan limit, maka sumber makanan tersebut diasumsikan untuk ditinggalkan. Misal sumber makanan yang ditinggalkan adalah xi dan j  {1, 2, ..., D}, maka lebah scout akan mencari sumber makanan baru untuk diganti dengan xi. Operasi ini dilakukan dengan menggunakan persarnaan 8. j j j xij  xmin  rand[0,1]( xmax  xmin )

(8)

Setelah masing-masing kandidat posisi sumber makanan vij diproduksi dan dievaluasi oleh lebah artificial, nilai fitnessnya dibandingkan dengan xij. Jika sumber makanan baru mempunyai nektar yang sama atau lebih baik daripada sumber yang lama, maka sumber yang lama tersebut akan digantikan dengan yang baru dalam memori, jika tidak maka yang lama dipertahankan. METODE USULAN Metode ABC-KHM Metode yang diusulkan dalam melakukan proses klasterisasi data dalam penelitian ini adalah Metode ABC-KHM. Metode ini dihasilkan melalui hibridasi antara metode ABC dan metode KHM. Dalam metode ABC-KHM, hasil klaster diperoleh dengan memanfaatkan hubungan timbal balik antara kedua metode yaitu ABC dan KHM. Posisi titik pusat yang dihasilkan pada fase lebah akan dioptimalkan dengan fase update yang terdapat pada metode KHM. Hasil titik pusat yang diperoleh dari fase KHM, akan dimanfaatkan oleh fase lebah sebagai tetangga acuan dari lebah pekerja untuk melakukan ekplorasi dalam ruang pencarian.

Gambar 2. Metode ABC-KHM

ISBN : 978-602-97491-3-7 C-26-4


Dalam implementasi metode ABC-KHM terdapat beberapa variabel yang digunakan untuk membatasi setiap fase yang ada. Parameter Max1 digunakan untuk membatasi jumlah iterasi pada tahapan pencarian titik pusat oleh para lebah. Hasil titik pusat dari tahapan ini akan menjadi titik pusat awal pada tahapan selanjutnya yaitu tahapan KHM. Tahapan iterasi pada KHM ini dibatasi oleh dua hal yaitu threshold selisih posisi titik pusat antar iterasi ( ) dan Max2. Fase lebah dan KHM ini akan dilakukan terus sampai iterasi melampaui batas iterasi maksimum yaitu MaxABCKHM. Data Dataset yang digunakan dalam penelitian ini adalah dataset Iris yang diambil dari UCI Machine Learning Repository (ftp://ftp.ics.uci.edu./pub/machine-learningdatabases/). Dataset iris ini terdiri dari empat fitur, dan tiga kelas. Jumlah total data iris ini sebanyak 150 data. Dalam penelitian ini, 80% data akan digunakan sebagai data training dan sisanya digunakan sebagai data testing. Data training ini digunakan untuk melihat performa dari ketiga metode dalam melakukan klasterisasi data. Penilaian performa ini dilihat dari tiga sudut pandang yaitu nilai fungsi tujuan KHM(X,C), FMeasure, dan running time. Data testing hanya digunakan untuk melihat korelasi secara eksternal (kelas label) yaitu bagaimana hasil klasifikasi data testing dengan memanfaatkan hasil titik pusat klaster dengan menggunakan data training. HASIL Dalam melakukan uji coba pada penelitian ini, nilai parameter yang digunakan untuk metode ABC mengacu pada nilai parameter yang digunakan oleh Zhang. Parameter tersebut antara lain Limit bernilai 10 dan jumlah MCN yang bernilai 2000 [10]. Untuk metode ABC-KHM penentuan, Limit, Max1, Max2 dan MaxABCKHM ditentukan dengan melakukan uji coba nilai-nilai parameter ini. Dari hasil uji coba yang telah dilakukan, didapatkan bahwa hasil terbaik diperoleh dengan menggunakan Max1=20, Limit=3, Max2=10, dan MaxABCKHM=20. Untuk mengetahui performa masing-masing metode maka pada penelitian ini digunakan tiga tolak ukur yaitu nilai fungsi tujuan KHM(X,C), F-measure, dan running time. Uji coba pada penelitian ini dilakukan melalui beberapa sekenario untuk menguji performa dari metode-metode yang ada. Sekenario ini dibuat dengan menggunakan fungsi tujuan yang berbeda-beda. Perbedaan fungsi tujuan ini terletak pada parameter p. Pada penelitian ini, terdapat dua buah sekenario nilai p yaitu p = 2, dan p = 4. Dari sisi penilaian eksternal (kelas label) pada penelitian ini digunakan penilaian F-measure. Nilai F-measure didapat dari persamaan 10 [1]. F(i,j) =

(b 2  1).( p (i, j ).r (i, j )) b 2 . p (i, j )  r (i, j )

(9)

p(i,j) = nij/nj dan r(i,j) = nij/ni dimana ni adalah jumlah data dari kelas i yang diharapkan sebagai hasil query, nj adalah jumlah data dari klaster j yang dihasilkan oleh query, dan nij adalah jumlah elemen dari kelas i yang masuk di klaster j. untuk mendapatkan pembobotan yang seimbang antara precision dan recall maka nilai b = 1 digunakan dalam menghitung nilai F-measure [3]. Untuk mendapatkan kesimpulan akhir hasil klasterisasi menggunakan metodemetode yang ada, maka uji coba klasterisasi dilakukan sebanyak 10 kali untuk tiap-tiap sekenario yang dibuat. Kesimpulan kinerja dari metode akan didapatkan melalui nilai rata-rata (mean) dan standar deviasi dari 10 percobaan tersebut.

ISBN : 978-602-97491-3-7 C-26-5


Dari uji coba yang telah dilakukan, didapatkan hasil bahwa posisi pusat klaster yang dihasilkan oleh ABC-KHM memiliki nilai fungsi tujuan yang paling minimum. Hasil pusat klaster yang dihasilkan juga dapat dikatakan relatif stabil, hal dilihat dari nilai standar deviasi yang kecil. Secara penilaian eksternal, metode ABC-KHM ini juga telah menunjukkan dominasinya dari kedua metode lainnya. Untuk waktu yang dibutuhkan dalam melakukan proses klasterisasi, metode ABC-KHM berada diantara kedua metode pembanding. Metode ABC-KHM membutuhkan waktu yang lebih lama jika dibandingkan dengan metode KHM, tetapi ABC-KHM membutuhkan waktu yang jauh lebih singkat daripada metode ABC. Seperti yang dibahas pada bagian sebelumnya bahwa data testing hanya digunakan untuk melihat secara eksternal bagaimana hasil klasifikasi data testing dari tiap metode. Teknik pengklasifikasian data testing adalah dengan membandingkan jarak antara data tersebut dengan pusat-pusat klaster yang ada. Data testing yang memiliki jarak terdekat dengan suatu titik pusat maka data tersebut akan diklasifikasikan kedalam kelas terdekat dengannya. Hasil uji coba untuk performa setiap metode terhadap tiga tolak ukur dapat dilihat pada Tabel 1. Hasil kesalahan klasifikasi dari ketiga metode dapat dilihat pada Tabel 2. Dari hasil klasifikasi melalui 10 kali uji coba didapatkan bahwa klasifikasi dengan metode KHM dan ABC-KHM relatif stabil jika dibandingkan dengan metode ABC. Tabel 1. Rata-rata dan Standar Deviasi dari 10 Kali Uji Coba Fungsi Tujuan Dataset Pengukuran

F-measure

Waktu

KHM

ABC

ABCKHM

KHM

ABC

ABCKHM

KHM

ABC

ABCKHM 3.42 0.137

p=2

Mean Std. Dev.

152.8758 0.001

164.2891 5.021

152.8691 0

0.8977 0

0.8875 0.012

0.8977 0

0.09 0.027

20.629 0.613

p=4

Mean

231.5938

188.9512

0.8805 0.017

0.61 0.022

4.76

0

0.8977 0

22.480

20.465

167.6143 7.872

0.8914

11.418

0.440

0.245

Std. Dev.

Tabel 2. Jumlah Kesalahan Klasifikasi di setiap uji coba p=2 p=4 Perc. KHM ABC ABC-KHM KHM ABC ABC-KHM 1 3 3 3 3 3 3 2 3 3 3 3 4 3 3 3 2 3 3 3 3 4 3 3 3 3 3 3 5 3 3 3 3 3 3 6 3 3 3 3 3 3 7 3 3 3 3 3 3 8 3 4 3 3 5 3 9 3 5 3 3 4 3 10 3 3 3 3 3 3

KESIMPULAN Dalam penelitian ini diusulkan sebuah metode baru untuk klasterisasi data yang berbasis pada metode ABC dan KHM yaitu ABC-KHM. Metode ABC-KHM ini telah berhasil mengoptimalkan posisi titik pusat klaster dengan mengarahkan hasil klaster menuju solusi global optimal. Hal ini dibuktikan dengan hasil penelitian yang menunjukkan nilai fungsi tujuan objective function dari metode ABC-KHM merupakan yang terkecil dari dua metode pembanding yaitu KHM dan ABC. Dari sisi penilaian

ISBN : 978-602-97491-3-7 C-26-6


hasil klaster secara eksternal menggunakan F-measure, metode ABC-KHM memiliki hasil yang dominan dari kedua metode pembanding. Dari sisi waktu yang dibutuhkan untuk melakukan proses klasterisasi data, metode ABC-KHM berada diantara kedua metode pembanding. Metode ABC-KHM membutuhkan waktu yang relatif jauh lebih lama jika dibandingkan dengan metode KHM, sehingga hal ini dapat dijadikan suatu kelemahan dari ABC-KHM. Optimasi waktu yang dibutuhkan ABC-KHM ini akan menjadi fokus penelitian selanjutnya. REFERENSI Dalli, A 2003, Adaptation of the F-Measure to cluster-based Lexicon quality evaluation, In EACL, Budapest. Hammerly, G., dan Elkan, C. 2002, “Alternatives to The K-Means Algorithm that Find Better Clusterings”, Proceedings of the 11th international conference on information and knowledge management, hal. 600–607. Handl, J., Knowles, J., dan Dorigo, M. 2003, "On the performance of ant-based clustering. Design and Application of Hybrid Intelligent Systems, Vol. 104, hal. 204–213. Karaboga, D. 2005, An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department. Karaboga, D. dan Basturk, B. 2008, “On The Performance of Artificial Bee Colony ABC Algorithm”, Applied Soft Computing, Vol. 8, hal. 687–697. Karaboga, D. dan Akay, B. 2009, “A Comparative Study of Artificial Bee Colony Algorithm”, Applied Mathematics and Computation, Vol 214, hal. 108–132. Tan, P.N., Stainbach, M., dan Kumar, V. 2006, Introduction to Data Mining, 4th edition, Pearson Addison Wesley, New York. Yang, F., Sun, T., dan Zhang, C. 2009, “An Efficient Hybrid Data Clustering Method Based on K-Harmonic Means and Particle Swarm Optimization”, Expert Systems with Applications, Vol. 36, hal. 9847–9852. Zhang, B., Hsu, M., dan Dayal, U. 1999, K-Harmonic Means – A Data Clustering Algorithm, Technical Report HPL-1999-124, Hewlett-Packard Laboratories. Zhang C., Ouyang, D., dan Ning, J. 2009, “An Artificial Bee colony Approach for Clustering”, Expert Systems with Applications, Vol. 37, hal 4761–4767.

ISBN : 978-602-97491-3-7 C-26-7

KLASTERISASI DATA IRIS MENGGUNAKAN METODE BERBASIS ARTIFICIAL BEE COLONY DAN K-HARMONIC MEANS

Recommend Documents