Jurnal Ilmiah NERO Vol. 1 No. 2
2014
IMPLEMENTASI AUTOMATIC CLUSTERING MENGGUNAKAN DIFFERENTIAL EVOLUTION DAN CS MEASURE UNTUK ANALISIS DATA KEMAHASISWAAN Achmad Yasid[1] Program Studi Manajemen Informatika, Universitas Trunojoyo Jl. Raya Telang, PO BOX 2, Kamal, Bangkalan e-mail:
[email protected] ABSTRAK
Saat ini differential evolution (DE) merupakan salah satu algoritma evolusi yang menjadi perhatian para ahli karena cepat, robust dan effisien dalam melakukan pencarian global.Penelitian ini menerapkan DE pada permasalahan clustering dengan menggunakan studi kasus data akademik pada program studi Manajemen Informatika Universitas Trunojoyo Madura. Berbeda dengan algoritma clustering lainnya, metode ini tidak membutuhkan input jumlah cluster akhir dari pengguna. Lebih jauh, algoritma ini dapat melakukan partisi data dan menghasilkan jumlah cluster optimal akhir secara otomatis.Untuk menguji hasil clustering, digunakan CS Measure dan menjalankan program sebanyak 30 kali.Berdasarkan hasil ujicoba program pada data akademik semester genap 2013-2014, program ini dapat menghasilkan jumlah cluster akhir dan nilai CS measure yang stabil dengan yang ditandai dengan nilai standard deviasi yang sangat kecil. Kata kunci: Differential Evolution, Clustering, CS Measure, Data Akademik
ABSTRACT
Recently differential evolution (DE) is one of the fast, robust and efficient evolutionary algorithms for global search problem of current interest by researcher. This study, intends to propose DE for clustering task using case study of academic data set at Informatics Management of Trunojoyo Madura University. In contrast to other clustering algorithms, this method does not require final clustering number input from the end user. Furthermore, it can partition data and generate an optimal number of final clusters automatically. To validate the clustering results, CS measure was employed and run for 30 times. The computational results in the second semester of 2013-2014 indicate that ACDE algorithm provide accurate final cluster number and stable CS measure value with small deviation standard. Keywords: Differential Evolution, Clustering, CS Measure, Academic data set
1.
PENDAHULUAN
Clustering adalah metode untuk mengelompokkan data yang belum mempunyai label kedalam kelompok-kelompok berdasarkan kemiripan yang dimiliki[2]. Data pada satu kelompok harus mempunyai tingkat kemiripan yang sangat tinggi satu sama lain dan memiliki tingkat perbedaan yang tinggi pula dengan data pada kelompok lainnya. Semakin besar kemiripan data pada satu kelompok, semakin besar ketidaksamaan data pada kelompok yang lain, maka semakin baik pula hasil clustering.Salah satu contoh algoritma clustering yang sangat terkenal dan sampai saat ini sering digunakan oleh para pakar adalah k-means[3]. Inisialisasi k-means dilakukan dengan memilih pusat data secara acak sejumlah cluster yang ditentukan oleh pengguna. Selanjutnya algoritma k-means bekerja dengan cara mengelompokkan data kedalam pusat data yang terdekat.Selanjutnya update pusat data dilakukan dengan menghitung rata-rata semua data yang ada pada suatu kelompok. Proses tersebut diulang sampai suatu kriteria tertentu terpenuhi. Adapun kelebihan dari algoritma k-means yaitu sederhana dengan waktu komputasi yang cepat.Namun salah satu kelemahan yang sangat mempengaruhi kualitas hasil dari k-means adalah penentuan jumlah cluster. Pengguna harus menentukan sendiri jumlah cluster akhir 47 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
sedangkan informasi mengenai jumlah cluster akhir tersebut tidak diketahui oleh pengguna. Disamping itu hasil akhir dari k-means sangat bergantung pada inisialisasi pusat data awal yang dipilih. Beberapa tahun terakhir ini, penelitian automatic clustering menjadi trend yang sangat diminati, karena metode ini dapat menghasilkan jumlah cluster akhir beserta partisi data disetiap kelompok secara otomatis, sehingga pengguna tidak perlu menginputkan jumlah cluster akhir diawal eksekusi program. Beberapa contoh algoritma clustering otomatis yang menggunakan metode metaheuristic diantaranya adalah genetic algorithm (GA)[4], particle swarm optimization (PSO)[4], dan differential evolution (DE) [5]. Terdapat banyak aplikasi yang menggunakan aplikasi data mining, diantaranya pada aplikasi pengelompokan dokumen[6], promosi[7], segmentasi pasar[8] dan lainnya. Pada bidang kemahasiswaan metode clusteringdiantaranya dapat digunakan untuk melakukan prediksi lama studi[9], keberhasilan studi mahasiswa[10], dan penentuan promosi Universitas[7]. Akan tetapi metode clustering yang digunakan masih menggunakan metode non-automatic yaitu jumlah cluster akhir harus diinputkan oleh pengguna diawal algoritma. Sedangkan pada penelitian ini, metode automatic clusteringditerapkan dengan menggunakan differential evolution (DE) dan CS Measure untuk mengolah data akademik kemahasiswaan pada program studi Manajemen Informatika Universitas Trunojoyo Madura. Algoritma ini dapat menentukan jumlah cluster akhir beserta data yang ada pada setiap cluster sehingga dapat digunakan untuk analisis bidang akademik sebagai bahan pertimbangan pengambilan kebijakan oleh pimpinan. Penelitian ini terdiri dari bagian pendahuluan yang memberikan gambaran secara umum penelitian clustering dan penerapannya.Bagian metode menjelaskan algoritma automatic clustering menggunakan differential evolution.Sedangkan pada bagian hasil dan pembahasan memaparkan mengenai penerapan dan hasil dari eksekusi algoritma yang menggunakan data akademik program studi Manajemen Informatika Universitas Trunojoyo Madura. Bagian terakhir membahas mengenai kesimpulan. 2.
METODE
Pengukuran Tingkat Kemiripan
Pada teknik clustering, data yang ada dalam satu kelompok harus memiliki tingkat kemiripan yang sangat tinggi, sedangkan data pada kelompok lain harus memiliki kemiripan yang sangat rendah. Berdasarkan definisi tersebut, maka tingkat kemiripan data merupakan permasalahan yang dasar.Oleh karena itu, pemilihan pegukuran perbedaan yang berupa penghitungan distance antar objek atau data seharusnya dilakukan dengan cermat. Pada penelitian ini, pengukuran distance menggunakan Euclidean Distance dengan Persamaan (1). d(Xi X j )
n 2 X i X j ( X i ,l X j , l ) , l 1
(1)
Euclidean distance, d, adalah jarak antara dua point, objek, atau data Xi and Xj, yang mempunyai atribut dimensi, l, sebanyak nilai tertentu, n. Clustering Validity Measure
Pada dasarnya terdapat dua buah pertanyaan mendasar yang harus terpenuhi pada clustering. Yang pertama adalah berapa jumlah cluster akhir yang diperoleh. Sedangkan yang kedua adalah seberapa baik tingkat partisi data yang dihasilkan.Kedua pertanyaan ini dapat dijawab dengan menggunakan clustering validity measure. pada penelitian ini CS measure[11] digunakan untuk dapat memperoleh jumlah cluster akhir dan melakukan partisi data secara 48 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
otomatis. Metrik jaraj antara dua data, point Xi dan Xq dinyatakan dengan d X , X
Measure dapat didefinisikan sebagai berikut :
CS ( K )
i K
i
q
maka CS
max d X , X K
i 1 i K
1
Ni X i Ci
X q Ci
i
q
min d m , m K
i 1
1 Ni i 1 K K
2014
jK , j i
i
j
max d X i, Xq X C X i Ci q i min d m i, mj j K , j i i 1
(2)
Differential Evolution
DE adalah algoritma evolusi yang diajukan oleh Storn dan Price[12]. Seperti algoritma evolusi lainnya, populasi awal, Vi ,d (t ) , dibangkitkan secara acak. Sebuah vektor individu (chromosome), ith, dari suatu populasi pada suatu waktu, t, mempunya dimensi, d, seperti pada Persamaan (3), kemudian selanjutnya akan bermutasi dan crossover.
Vi ,d (t ) vi ,1 (t ), vi ,2 (t ),..., vi , d (t )
(3)
Mutasi adalah proses untuk membangkitkan parameter baru dengan menambahkan perbedaan bobot antara dua vektor populasi kepada vektor populasi ketiga. Hasil dari mutasi tersebut berupatrial vector, Zi,d(t+1) , yang dibangkitkan dari tiga vektor acak, misalkan : Vj,d (t), Vk,d (t), and Vl,d (t), dari suatu generasi yang sama, i, j, k, berdasarkan scale factor , F, seperti pada persamaan (4).
Z i , d (t 1) V j ,d (t ) F (Vk , d (t ) Vl , d (t ))
(4)
Untuk meningkatkan keragaman vektor parameter, maka dilakukanlah crossover yang menghasilkan trial vector, Uji,d(t+1), seperti pada pada persamaan (5). Crossover rate, CR, dapat ditentukan oleh pengguna, sedangkan randj adalah pembangkit evaluasi acak dengan nilai output [0,1].
Zi , d (t 1) if rand j (0,1) CR or j = rand (d ) U ji ,d (t 1) if rand j (0,1) CR or j rand (d ) Vi ,d (t ),
(5)
Seleksi dilakukan untuk memilih offspring terbaik untuk menjadi populasi pada generasi selanjutnya.Setiap trial vector dibandingkan dengan fungsi tujuan pada Persamaan (2). Apabila offspring baru memiliki nilai yang lebih baik (lebih kecil) maka akan menggantikan parents saat ini kemudian dimasukkan kedalam populasi baru pada generasi selanjutnya.
U (t 1), Vi (t 1) i Vi (t ),
if f U i (t 1) f Vi (t ) if f U i (t 1) f Vi (t )
(6) 49 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
Representasi Chromosome
Sebuah kromoson, Vi,d, mempunyai jumlah cluster maksimum, Kmax,, yang terdiri dari threshold, T, dan dimensi, m. Terdapat dua bagian penting pada representasi chromose pada metode automatic cluster, yaitu activation threshold dan cluster centroids (pusat cluster). Activation threshod akan menentukan jumlah cluster akhir yang dihasilkan. Mekanisme kerja dari activation threshold bertindak sebagai kontrol yang menentukan suatu cluster aktif atau tidak aktif dengan nilai positif antara [0,1]. Untuk mengetahui suatu cluster aktif atau tidak maka persamaan (7) digunakan.
Gambar 1. Representasi chromosome
Gambar 2. Contoh representasi chromosome
IF Ti , j 0.5, THEN the j th cluster center vi , j mk is ACTIVE ELSE vi , j mk is INACTIVE
Adapun keseluruhan langkah-langkah algoritma automatic clustering menggunakan differential evolution (ACDE) dapat diilutrasikan sebagai berikut. 1. Inisiasi setiap kromosom mempunyai sejumlah cluster, K, secara acak dan sejumlah, K, activation threshold yang dipilih secara acak pula pada range [0,1]. 2. Dapatkan cluster aktif dengan menggunakan Persamaan (7) 3. For t=1 sampai tmax a. Hitung jarak setiap vektor data, gunakan Persamaan (1), pada pusat data yang aktif b. Masukkan data vektor dengan jarak terdekat pada pusat data aktif yang terdekat c. Terapkan DE (4-5) d. Hitung fungsi tujuan setiap trial vectordengan Persamaan (2) e. Lakukan pengecekan offspring, gunakan Persamaan (6) 4. Tampilkan hasil yang mempunyai nilai fungsi tujuan terkecil. 3.
HASIL DAN PEMBAHASAN
Penerapan algoritma ACDE dilakukan pada data akademik program studi Manajemen Informatika Universitas Trunojoyo Madura.Adapun atribut yang digunakan yaitu, IP, jumlah sks persemester, jenis kelamin, dan beasiswa. Analisis cluster dilakukan pada setiap semester untuk mengetahui pemetaan hasil belajar mahasiswa.Pada penelitian ini digunakan data pada semester genap tahun akademik 2013/2014 yang terdiri dari 166 mahasiswa. 50 | N E R O
(7)
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
Untuk mendapatkan hasil clustering yang baik, pada algoritma ACDE perlu ditentutkan beberapa parameter seperti pada table 1. Akurasi algoritma dihitung dengan menjalankan program sebanyak 30 kali untuk mendapatkan rata-rata jumlah cluster dan mengetahui hasil dari CS measure. Table 1. Parameter DE Parameter Jumlah populasi F (ACDE) CR (ACDE) kmin ; kmax
Nilai 10 x dimensi 0.5 : 1.0 0.5 : 1.0 2; Npop
Tabel 2. Jumlah kelompok Rata-rata jumlah Set data CS measure±SD kelompok ±SD Kemahasiswaan 3±0.0000 0.4369±0.0089 Tabel 3. Hasil partisi data Kelompok Jumlah Kelompok 1 18 Kelompok 2 20 Kelompok 3 128 Berdasarkan hasil komputasi yang dijalankan sebanyak 30 kali didapatkan data seperti pada Tabel 2. Adapun rata-rata jumlah cluster yang dihasilkan tepat sejumlah 3 cluster dengan standar deviasi 0,0000 sedangkan nilai fungsi tujuan yang menggunakan CS Measure mendapatkan nilai rata-rata 0,4369 dengan nilai standar deviasi 0,0089. Selain dapat menghasilkan jumlah cluster secara otomatis, algoritma ini juga dapat mempartisi data secara otomatis pula dengan jumlah data pada setiap cluster dapat dilihat pada Tabel 3. Apabila data pada Table 3 dikomparasi dengan atribut pada data akademik, maka didapatkan pola seperti berikut: Cluster 1. Berisikan mahasiswa dengan IP rendah, dan jumlah sks yang diambil sedikit pada tiap semester
Cluster 2. Terdiri dari mahasiswa dengan tinggi dan jumlah sks yang banyak pada setiap semester serta juga mendapatkan beasiswa
4.
Cluster 3.Mayoritas data mahasiswa berada pada kelompok ini dengan IP sedang, jumlah sks tiap semester mulai dari sedang sampai maksimal serta ada yang medanapatkan beasiswa.Sedangkan untuk jenis kelamin pada data penelitian ini tidak mempunyai pengarh yang begitu signifikan. KESIMPULAN
Algoritma ACDE dengan menggunakan fungsi tujuan CS Measure telah dilakukan pada penelitian ini. Performa yang didapatkan sangat baik karena mampu memperoleh jumlah cluster yang stabil yang didukung oleh nilai CS measure yang stabil pula apabila dilihat dari nilai standar deviasi pada angka 0.0089. Lebih jauh, lagoritma ini dapat melakukan partisi data secara 51 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
otomatis.Sehingga dapat memberikan informasi ataupun pola yang sangat berguna bagi pihak manajemen pada prodi Manajemen Informatika Universitas Trunojoyo. 5.
[1]
DAFTAR PUSTAKA
Abdule-Wahab, R., Monmarché, N., Slimane, M., Fahdil, M., dan Saleh, H., A Scatter Search Algorithm for the Automatic Clustering Problem, in Advances in Data Mining. Applications in Medicine, Web Mining, Marketing, Image and Signal Mining, P. Perner, Editor. 2006, Springer Berlin Heidelberg. p. 350-364. [2] Jain, A.K., Murty, M.N., dan Flynn, P.J. 1999. Data clustering: a review.ACM computing surveys (CSUR). 31(3): 264-323. [3] MacQueen, J. 1967.Some methods for classification and analysis of multivariate observations. in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics. Berkeley, Calif.: University of California Press. [4] Kuo, R.J., Syu, Y.J., Chen, Z.-Y., dan Tien, F.C. 2012. Integration of particle swarm optimization and genetic algorithm for dynamic clustering.Information Sciences. 195(0): 124-140. [5] Das, S., Abraham, A., dan Konar, A. 2008. Automatic Clustering Using an Improved Differential Evolution Algorithm.Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on. 38(1): 218-237. [6] Akter, R. dan Chung, Y. 2013. An Evolutionary Approach for Document Clustering.IERI Procedia. 4(0): 370-375. [7] Ong, J.O. 2013. Implementasi Algoritma K-Means Clustering Untuk Menentukan Strategi Marketing President University.Jurnal Ilmiah Teknik Industri. 12: 10-20. [8] Kuo, R.J., Akbaria, K., dan Subroto, B. 2012. Application of particle swarm optimization and perceptual map to tourist market segmentation.Expert Systems with Applications. 39(10): 8726-8735. [9] Lindawati. 2008. data mining dengan teknik clustering dalam pengklasifikasian data mahasiswa studi kasus prediksi lama studi mahasiswa universitas bina nusantara.Seminar Nasional Informatika 2008: 174-180. [10] Sirait, T.H. dan Ong, J.O. 2010. Analisis Keberhasilan Mahasiswa Dengan Metode Clustering K-Means SNASTIA Teknik Informatika Universitas Surabaya: 1-6. [11] Chou, C.-H., Su, M.-C., dan Lai, E. 2004. A new cluster validity measure and its application to image compression.Pattern Anal. Appl.7(2): 205-220. [12] Storn, R. dan Price, K. 1997. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces.J. of Global Optimization. 11(4): 341-359.
52 | N E R O
