PENINGKATAN KINERJA ALGORITMA K-MEANS DENGAN FUNGSI KERNEL POLYNOMIAL UNTUK KLASTERISASI OBJEK DATA

Prosiding Seminar Nasional Manajemen Teknologi XVI Program Studi MMT-ITS, Surabaya 14 Juli 2012

PENINGKATAN KINERJA ALGORITMA K-MEANS DENGAN FUNGSI KERNEL POLYNOMIAL UNTUK KLASTERISASI OBJEK DATA Heri Awalul Ilhamsah Jurusan Teknik Industri Universitas Trunojoyo Madura Kampus Universitas Trunojoyo Madura Jl. Raya Telang Kamal-Bangkalan Email: [email protected] ABSTRAK Penelitian ini membahas modifikasi algoritma K-Means dalam klasterisasi suatu objek data. Tujuan dari modifikasi ini adalah untuk meningkatkan kinerja algoritma tersebut, karena seringkali algoritma K-Means terjebak dalam lokal optima ketika menghadapi data yang tidak linier. Data test yang digunakan untuk menguji efektifitas modifikasi algoritma menggunakan set data Iris. Modifikasi algoritma dilakukan dengan menambahkan fungsi kernel polynomial. Fungsi kernel akan membawa data dari space lama ke space baru sehingga dimungkinkan untuk dipisah secara linier. Hasil penelitian ini mengkonfirmasikan bahwa nilai β antara 0.09 sampai 1 pada fungsi kernel polynomial memberikan tingkat missclass terendah sebesar 2% pada klasterisasi data Iris. Kata kunci : Fungsi Kernel Polynomial, Klasterisasi, K-Means, Set Data Iris

PENDAHULUAN Metode pengelompokkan data dalam data mining di kenal dengan istilah klastering. Klastering merupakan usaha mengelompokkan data kedalam beberapa klaster atau kelas berdasarakan tingkat kemiripannya, semakin mirip nilai dari suatu titik data maka akan menempati kelas yang sama. Metode klastering ini menggunakan dua pendekatan utama yaitu berdasarakan herarki dan partisi. Metode klastering dengan pendekatan herarki dilakukan dengan membuat suatu hirarki, biasanya berupa dendrogram dengan menempatkan data yang memiliki tingkat kemiripan sama pada satu hirarki akibatnya data yang memiliki tingkat kemiripan rendah akan menempati hirarki yang berjauhan. Klastering dengan pendekatan partisi (partition-based clustering) dilakukan dengan mengelompokkan data serta memilahmilah data yang dianalisa ke dalam klaster-klaster yang ada. Salah satu metode klastering yang umum digunakan di bidang data mining adalah metode K-Meansclustering. K-Meansadalah suatu metode penganalisaan data dalam data mining dengan melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi (Agusta, 2007). Metode tersebut dilakukan dengan mengelompokkan obyek ke dalam k klaster atau kelas. Untuk melakukan klastering ini, nilai k harus ditentukan terlebih dahulu. Biasanya user atau pemakai sudah memiliki informasi awal tentang obyek yang dipelajari, termasuk berapa jumlah klaster yang paling tepat (Santosa, 2007). Tujuan dari klasterisasi data menjadi k kelas adalah meminimalisasi variasi di dalam suatu kelas dan memaksimalkan variasi antar kelas. Usaha untuk meningkatkan kinerja algoritma K-Means dalam mengklasterkan kumpulan data terus dilakukan. Zhang et, all.(1999) mengusul K Harmonic Means dalam algoritma K-Means untuk mengatasi terjadinya lokal optima ketika inisialisasi pusat klaster. Penelitian tersebut disempurnakan lagi oleh Zhang et, all.(2009) dengan diusulkannya penggunaan algoritma Bee Colony untuk inisialisasi pusat klaster. Pada penelitian ini akan ISBN : 978-602-97491-5-1 A-1-1


digunakan fungsi kernel Polynomial untuk menghindar dari terjadinya lokal optima pada inisialisasi pusat klaster. Hal tersebut dilakukan dengan memetakan data dari space lama ke space yang baru sehingga data bisa dipisahkan secara linier. METODOLOGI Langkah pertama dari algoritma K-Means adalah dengan menentukan parameter input, k, dimana parameter tersebut akan berfungsi sebagai banyaknya klaster yang dikehendaki. Data yang ada sebanyak n data atau obyek akan di klaster ke dalam k klaster tadi sehingga diharapkan menghasilkan similarity intra klaster tinggi namun similarity antar klaster rendah. Untuk mengukur kemiripan bisa dipakai cosinus, kovarian, dan korelasi, sedangkan untuk mengukur ketidakmiripan bisa digunakan jarak (Santosa, 2007). Ketidakmiripan dapat diterjemahkan dalam konsep jarak, semakin dekat jaraknya berarti semakin tinggi kemiripannya, dan sebaliknya (Santosa, 2007). Pada penelitian ini akan digunakan konsep perhitungan jarak eucledian. Jarak euclidean (L2-norm) jarak dua titik x dan y menurut euclidean dirumuskan sebagai:

d ( x, y)  x  y  2

n

 x

i

i 1

 yi 

2

Algoritma K-Meanssecara sederhana menurut Han & Kamber (2006) adalah: 1. Definisikan secara random jumlah klaster (k) yang akan digunakan sebagai pusat klaster awal. 2. Untuk semua obyek data, tempatkan pada klaster yang paling mirip, berdasarkan pada jarak antara obyek dengan pusat klaster awal. 3. Tentukan nilai mean dari klaster-klaster yang terbentuk, sebagai pusat klaster baru. Proses ini berlangsung iteratif. 4. Lakukan lagi langkah 2 dan 3 sampai fungsi kriteria konvergen. Umumnya, kriteria yang digunakan adalah square-error yang dirumuskan sebagai berikut: k

E    p  mi

2

i 1 pCi

dimana E adalah sum of square error untuk semua obyek dalam data set, p adalah koordinat tiap titik yang mewakili obyek yang ada, dan mi adalah mean dari klaster Ci (p dan mi adalah multidimensional). Fungsi kriteria ini mencoba menghasilkan k klaster yang padat dan terpisah sebaik mungkin. Secara ringkas, metode K-Means dapat dilihat pada Gambar 1.1.

ISBN : 978-602-97491-5-1 A-1-2


Kernel K-Means adalah pegembangan dari algoritma K-Means dengan cara memetakan data ke space baru menggunakan metode kernel. Hal tersebut dilakukan untuk meningkatkan akurasi hasil klaster. Didalam kernel K-Means diharapkan data bisa dipisahkan dengan lebih baik karena data yang overlap atau nonlinier bisa menjadi linier di ruang dimensi baru. Fungsi kernel yang digunakan adalah fungsi polynomial. Nilai β pada persamaan kernel polynomial berperan sebagai derajat dan akan ditentukan melalui serangkaian ujicoba. Nilai y terbaik akan memberikan tingkat missclass terendah. K=(x.x'+1)β Alur klusterisasi algoritma K-Means dengan fungsi kernel dapat dilihat pada gambar dibawah. Data set Iris Pengurutan atribut / variabel

Membentuk Matrik Kernel dengan Fungsi Kernel Polynomial Tentukan Jumlah Klaster/Kelas Yang dikehendaki

Inisialisasi Pusat Klaster

Tempatkan Setiap Objek Data ke Pusat Klaster Terdekat Berdasarkan Jaraknya

Hitung Jarak Rata-Rata Anggota Klaster dengan Pusat Klaster

Tugaskan Lagi Setiap Obyek ke Pusat Klaster Baru, Sampai Pusat Klaster Tidak Berubah

Gambar 1. Alur Algoritma Kernel K-Means

Untuk menentukan tingkat keberhasilan dalam melakukan proses klastering ada beberapa ukuran yang bisa dipakai. Menurut Santosa (2007), untuk menentukan jarak antara dua klaster A dan B dapat digunakan salah satu dari beberapa ukuran: 1. Complete linkage clustering (jarak maksimum antara elemen dalam klaster) Jarak antara dua klaster didefinisikan sebagai: d (A,B) = max S xy  xA, yB

dimana Sxy adalah jarak dua data x dan y masing-masing dari klaster A dan B. 2. Single linkage clustering (jarak minimum antara elemen dari setiap klaster) Jarak antara dua klaster didefinisikan sebagai d (A,B) = min S xy  xA, yB

3. Average linkage clustering (rata-rata jarak antara elemen dari setiap klaster) Jarak antara dua klaster didefinisikan sebagai 1 d (A,B) =   S x, y n A n B xA yB dimana nA dan nB masing-masing adalah banyaknya data dalam set A dan B. ISBN : 978-602-97491-5-1 A-1-3


4. Centroid linkage Jarak antara dua klaster didefinisikan sebagai d (A,B) = sx , y  1 dimana: x  x, n A xA 1 y y n B xB 5. Ward linkage Jarak antara dua klaster didefinisikan sebagai 2 n A nB s AB d (A,B) = , n A  nB 2 dimana s AB adalah jarak antara klaster A dan B menggunakan centroid linkage.

PEMBAHASAN Untuk melihat efektifitas algoritma ini dalam melakukan klasterisasi data, akan digunakan data test. Data test yang digunakan adalah data set iris yang bisa diambil dari UCI Machine Learning Repository (ftp://ftp.ics.uci.edu./pub/machine-learning-database/). Jumlah total data iris ini sebanyak 150 data terdiri dari empat fitur, dan tiga kelas. Dalam penelitian ini, 40% data akan digunakan sebagai data training dan sisanya digunakan sebagai data testing. Salah satu parameter yang akan di buat berubah-ubah guna mendapatkan hasil klaster terbaik adalah nilai β pada fungsi kernelnya. Jumlah iterasi ditentukan sebesar 1000 didapatkan hasil sebagai berikut : Tabel 1. Hasil Missclass Klasterisasi Data Iris Menggunakan Algoritma Kernel K-Means No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

β 2 1.9 1.8 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0.1 0.09 0.07 0.05 0.03

Missclass 14.67% 14.67% 14% 12.67% 12% 11.3% 11.3% 10% 6% 4% 2.6% 2% 2% 2.6% 2.6% 2.6%

Nilai β terbaik yang mampu memberikan tingkat missclass terendah berada pada kisaran 0.09 sampai 1, dengan prosentase missclass 2%. Nilai missclass sebesar 2% ini

ISBN : 978-602-97491-5-1 A-1-4


menunjukkan algoritma Kernel K-Means kurang tepat dalam menentukan kelas dari 3 titik data dari 150 titik data. KESIMPULAN Hasil komputasi dari Algoritma Kernel K-Means menunjukkan bahwa fungsi Kernel Polynomial dengan tingkat degree pada kisaran 0.09 sampai 0.1 mampu mengklasterkan data Irish dengan tingkat kesalahan 2%. Dengan demikian dapat disimpulkan bahwa penambahan fungsi kernel polynomial mampu meningkatkan kinerja algoritma K-Means. Untuk penelitian selanjutnya bisa diuji cobakan fungsi-fungsi kernel lainnya sehingga bisa di lihat pengaruhnya terhadap kinerja algoritma K-Means dalam usaha klasterisasi objek data. DAFTAR PUSTAKA Zhang C., Ouyang, D., dan Ning, J. (2009), An Artificial Bee Colony Approach for Clustering, Expert Systems with Applications, Vol. 37, hal 4761–4767. Agusta, Y. (2007), K-means, Penerapan, Permasalahan dan Metode Terkait, Jurnal Sistem dan Informatika, Vol, 3 (Pebruari 2007), 47-60. Santosa, B. (2007), Data Mining Teknik Pemanfaatan Data untuk Keperluan Bisnis, Graha Ilmu, Jakarta. Zhang, B., Hsu, M., dan Dayal, U. (1999), K-Harmonic Means–A Data Clustering Algorithm, Technical Report HPL-1999-124, Hewlett-Packard Laboratories. Han, J. dan Kamber, M. (2006), Data mining: Concepts and Techniques (2nd ed,), Elsevier Inc. Ulya, M. (2010), Klastering Varietas Padi Menggunakan Modifikasi Metode KMeansBerbasis OWA(Oriented Weighted Averaging), Thesis Jurusan Teknik Industri, Institut Teknologi Sepuluh Nopember, Surabaya.

ISBN : 978-602-97491-5-1 A-1-5

PENINGKATAN KINERJA ALGORITMA K-MEANS DENGAN FUNGSI KERNEL POLYNOMIAL UNTUK KLASTERISASI OBJEK DATA

Recommend Documents