DETEKSI MAHASISWA BERPRESTASI DAN BERMASALAH DENGAN METODE K- MEANS KLASTERING YANG DIOPTIMASI DENGAN ALGORITMA GENETIKA

LPPM Politeknik Bengkalis

DETEKSI MAHASISWA BERPRESTASI DAN BERMASALAH DENGAN METODE KMEANS KLASTERING YANG DIOPTIMASI DENGAN ALGORITMA GENETIKA Akmal Hidayat1) & Entin Martiana2) 1)

Teknik Elektro Politeknik Bengkalis Jl. Bathin Alam Sei.Alam Bengkalis-Riau [email protected] 2)

Politeknik Elektronika Negeri Surabaya ITS Surabaya Jl. Kampus ITS, Keputih Sukolilo Surabaya, 60111

Abstrak Penelitian ini membahas pendeteksian mahasiswa berprestasi dan bermasalah dengan metode kmeans klastering dan centroid awal yang dioptimasi dengan algoritma genetika. K-means klastering dilakukan untuk mengklaster data akademik mahasiswa menjadi empat buah klaster, yaitu klaster mahasiswa berprestasi, berpotensi berprestasi, berpotensi bermasalah, dan klaster mahasiswa bermasalah. Selain melakukan penngklasteran data akademik mahasiswa, pada penelitian ini juga dilakukan pendeteksian data outlier pada masing-masing klaster. Hal ini dilakukan untuk melihat mahasiswa-mahasiswa yang akan mengalami perubahan tingkat kemampuan akademik kearah negatif maupun ke arah posisitif. Individu mahasiswa dikatakan akan mengalami perubahan kemampuan akademik kearah positif bila menjadi outlier dengan jarak yang lebih dekat kepada klaster dengan tingkat kemampuan akademik yang lebih tinggi dari klasternya, sedangkan dikatakan berubah kearah yang negatif bila menjadi outlier dengan jarak yang lebih dekat kepada klaster dengan tingkat kemampuan akademik yang lebih rendah dari klasternya. Kata kunci : algoritma genetika, kmeans, euclidean distance, data outlier, perubahan positif, perubahan negative

I. PENDAHULUAN Dalam pembahasan pattern classification, clustering merupakan metode pengelompokan di mana data yang akan dikelompokan belum membentuk kelompok sehingga klaster yang akan dilakukan bertujuan agar data yang terdapat di dalam kelompok yang sama relatif lebih homogen daripada data yang berada pada kelompok yang berbeda. Klasterisasi yang dilakukan pada sekelompok data, sering menggunakan metode yang didasarkan pada jarak antar kelompok. Beberapa metode tersebut, antara lain : metode pautan tunggal (single linkage method), metode pautan lengkap (complete linkage method), metode pautan pusat (centroid

linkage method) dan juga metode pautan rerata (group average lingkage method). Pendekatan lain dalam proses klasterisasi adalah dengan menggunakan algoritma genetika. Penerapan diberbagai bidang sudah dilakukan antara lain klaster pada data geografis di Negara portugal, data vowel, iris dan crude oil . 2. ALGORITMA GENETIKA Algoritma genetika dikembangkan oleh John Holland (1975). Algoritma genetika adalah algoritma yang mengemulasikan proses biologi dari rekombinasi genetika, mutasi dan seleksi natural untuk membangkitkan solusi suatu permasalahan. Algoritma genetika digunakan untuk permasalahan pencarian dengan melakukan minimisasi biaya dan

Disampaikan pada Seminar Nasional Industri dan Teknologi [SNIT] 2008 Bengkalis, 03-04 Desember 2008

24


probabilitas yang tinggi untuk mendapatkan solusi global optimal. Isi dari genetika yang disebut feature direpresentasikan sebagai suatu gen. Kumpulan dari gen disebut dengan kromosom. Kromosom direpresentasikan dengan solusi sebagai bit string yang disebut individu. Setiap solusi diasosiasikan dengan nilai fitness. Terjadi perubahan feature dari spesies yang disebut evolusi dimana gen dengan fitness terbaik akan bertahan, sedangkan gen dengan fitness terendah akan mati. Kombinasi dari gen akan dibangkitkan dari induk yang disebut crossover. Perubahan terhadap individu sebagian besar disebabkan oleh crossover dan sedikit mutasi. Gambaran umum dari algoritma genetika dasar :

2.1 Representasi kromosom

[Start] Membangkitkan populasi random dari n kromosom. [Fitness] Evaluasi fitness f(x) dari setiap kromosom x pada populasi. [New population] Membuat populasi baru dengan mengulangi langkah-langkah berikut sampai populasi baru ditemukan : a) [Selection] Memilih dua kromosom induk dari suatu populasi berdasarkan nilai fitness (semakin baik fitness, semakin besar kemungkinan dipilih) b) [Crossover] Dengan probabilitas crossover melakukan crossover dengan induk untuk membentuk anak baru (offspring). Apabila tidak ada crossover yang dibentuk, offspring merupakan copy dari induk. c) [Mutasi] Dengan probabilitas mutasi melakukan mutasi offspring baru pada setiap posisi dalam kromosom. d) [Accepting] Menempatkan offspring baru dalam populasi baru. e) [Replace] Menggunakan populasi generasi baru untuk menjalankan algoritma selanjutnya f) [Loop] Ke langkah 2

merepresentasikan ke tiga pusat klaster, dimana (51.6, 72.3) merupakan pusat klaster pertama, (18.3, 15.7) pusat klaster kedua dan (29.1, 32.2) merupakan pusat klaster ketiga.

Algoritma genetika ini digunakan untuk melakukan optimasi pada pusat klaster dengan metode k-means.

Kromosom merupakan kumpulan dari gen yang berupa barisan dari bilangan real yang merepresentasikan K pusat cluster. Untuk kasus yang berisi N variabel, maka panjang kromosom adalah N*K, di mana posisi N pertama merepresentasikan N dimensi pusat klaster yang pertama, posisi N berikutnya merepresentasikan pusat cluster yang kedua, dan seterusnya. Berikut ini, sebagai suatu ilustrasi : Bila N=2 dan K= 3, yaitu kasus yang berisi dua variabel dan klaster sebanyak tiga. Maka kromosom dapat dinyatakan berikut ini :

2.2 Pembangkitan populasi awal K pusat klaster yang dikodekan pada setiap kromosom dibangkitkan secara acak dengan berdasarkan pada data asli yang akan diklaster. Langkah-langkahnya adalah sebagai berikut : 1. Urutkan nilai dari yang tertinggi hingga terendah untuk masing-masing gen dengan berdasarkan pada data asli yang akan diklaster 2. Menentukan nilai setiap gen dengan mengambil nilai pada suatu urutan data yang telah diurutkan pada langkah 1. nilai urutan data yang diambil adalah data pada urutan pertama untuk centroid 1, data pada urutan ke 25 % dari jumlah data asli untuk centroid ke 2, data pada urutan ke 50 % dari jumlah data asli untuk centroid ke 3, dan data pada urutan ke 75 % dari jumlah data asli untuk centroid ke 4 3. Ulangi langkah ke dua untuk individu berikutnya dengan menambahkan nilai urutan data yang akan diambil dengan 1 2.3 Evaluasi Fitness Evaluasi fitness dilakukan untuk memilih inidvidu yang terbaik. Individu yang terpilih


25


akan selanjutnya akan mengalami proses algoritma genetika berikutnya. Pada proyek akhir ini fungsi fitness yang digunakan adalah sebagai berikut:

3. K-MEANS KLASTERING

Seleski dilakukan dalam rangka untuk mendapatkan calon induk yang baik. Karena induk yang baik akan menghasilkan keturunan yang baik. Sehingga semakin tinggi nilai fitness suatu individu maka semakin besar kemungkinannya untuk terpilih. Dalam tahap seleksi ini dilakukan dengan menggunakan mesin roullete.

Hasil dari optimasi titik pusat awal dengan menggunakan algoritma genetika, selanjutnya hasil optimasi ini akan dimasukan kedalam algoritma k-means sebagai titik pusat awalnya. Dengan harapan melalui titik pusat awal yang telah dioptimasi ini akan menghasilkan hasil klaster yang lebih baik dibanding dengan klasterisasi dengan titik pusat awal tanpa dilakukan optimasi. Adapun langkah-langkah klasterisasi K-means dalam tugas akhir ini adalah sebagai berikut : a) Nilai k klaster ditentukan sebanyak empat, yaitu klaster mahasiswa berprestasi, klaster mahasiswa berpotensi berprestasi, klaster mahasiswa berpotensi bermasalah, klaster mahasiswa bermasalah b) Ambil centroid awal klaster dari hasil optimasi c) Hitung setiap data ke masing-masing centroid d) Setiap data memilih centroid yang terdekat e) Tentukan posisi centroid baru dengan menghitung nilai rata-rata data yang memilih centroid yang sama f) kembali ke langkah 3 apabila centroid baru tidak sama dengan centroid lama.

2.5 Kawin silang (Cross Over)

4. DETEKSI DATA OUTLIER

Cross over dilakukan dengan mengawinkan gen antar individu, ada banyak teknik cross over yang dikenal dalam algoritma genetika, diantaranya cross over secara langsung dan cross over secara aritmatika. Pada tugas akhir ini menggunakan cross over aritmatik, dengan menggunakan persamaan berikut : Induk [n] = r . induk [n] + (1- r) . induk [n+1] Induk [n+1] = r . induk [n+1] + (1- r) . induk [n] Dimana : r adalah bilangan random diantara 0 dan 1

Deteksi data outlier dilakukan untuk mencari individu data yang memiliki karakteristik yang jauh berbeda dibanding dengan data yang berada pada klaster yang sama. Pada tugas akhir ini data outlier tersebut berupa data individu mahasiswa yang memiliki data yang berada jauh dari titik centroid suatu klaster, jauh melebihi besarnya rata-rata jarak data lain yang berada pada klaster yang sama terhadap centroidnya.

N

J = ∑ minr d(xi, wr) I=1

Dimana : J = minimum distance xi = Data ke i wr = Centroid ke r N = Jumlah Data d(a,b) = Jarak dari a ke b Sehingga :

Nilai fitness = 1/J

2.4 Seleksi

2.6 Mutasi Setiap individu mengalami mutasi gen dengan probabilitas mutasi yang telah ditentukan. Mutasi dilakukan dengan menggeser nilai gen pada gen yang terpilih untuk dimutasi.

Data outlier pada tugas akhir ini merupakan data dari individu mahasiswa yang akan mengalami pergeseran kemampuan akademik, baik itu ke arah yang positif maupun ke arah yang negatif. Pergeseran data outlier dikatakan ke arah positif, bila data tersebut bergeser ke arah yang lebih dekat kepada klaster dengan tingkat kemampuan akademik yang lebih


26


tinggi di banding dengan tingkat kemampuan akademik klaster yang ditempatinya. Data outlier dikatakan bergerak ke arah yang negatif bila data tersebut bergerak kerah yang lebih dekat pada klaster yang memiliki tingkat kemampuan akademik yang lebih rendah dari tingkat kemampuan akademik klaster yang ditempatinya. Sebagai ilustrasi dari penjelasan di atas dapat dilihat dari gambar ilustrasi berikut ini:

setiap klaster terlampir). Nilai tertinggi dari penjumlahan setiap atribut data pada masingmasing centroid akan diberi label klaster mahasiswa berprestasi, berturut-turut hingga nilai terendah dari hasil penjumlahan ini diberi label klaster mahasiswa bermasalah Dengan menggunakan media pengolahan data Microsoft excel didapat hasil perhitungan nilai rata-rata data pada masing-masing klaster sebagai berikut : Perbandingan Titik Centroid Setiap Klaster Sebelum Dilakukan klasterisasi Dengan K-means 120 100

Centroid klaster berprestasi

Nilai

80

Centroid klaster berpotensi berprestasi

60

centroid klaster potensi bermasalah

40

centroid klaster bermasalah

20 0 1

3

5

7

9

11

13

15

17

19

Matakuliah dan Absensi

Perbandingan Titik Centroid Setiap Klaster Setelah Dilakukan klasterisasi Dengan K-means

5. EKSPERIMEN DAN PEMBAHASAN 120 100

Centroid klaster berprestasi

80 nilai

Dari keseluruhan pengujian hasil algoritma genetika, dapat ditentukan nilai prob.co dan prob mutasi yang optimal untuk digunakan pada aplikasi ini, dengan mengacu pada grafik berikut didapat bahwa nilai probabilitas cros over yang ideal adalah 0,8 dan probabilitas mutasi sebesar 0,3.

Centroid klaster potensi berprestasi

60

Centroid klaster potensi bermasalah

40

Centroid klaster bermasalah

20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 index matakuliah dan absensi

Hasil keseluruhan pengujian algoritma genetika

6. KESIMPULAN

0.000012 0.0000119 0.0000118

prob.co 0.5 dan prob.mut 0.3 prob.co 0.6 dan prob.mut 0.3 prob.co 0.7 dan prob.mut 0.3

fitn e s s

0.0000117 0.0000116

prob.co 0.8 dan prob.mut 0.3 prob.co 0.85 dan prob.mut 0.3 prob.co 0.9 dan prob.mut 0.3

0.0000115 0.0000114 0.0000113 0.0000112

12 0 15 0 18 0 21 0 24 0 27 0 30 0 33 0 36 0 39 0

60 90

1 30

0.0000111

iterasi

Pengujian hasil klastering dilakukan untuk melihat ketepatan pemberian label pada masing-masing klaster. Label pada setiap klaster ditentukan dengan mengurutkan total data pada setiap atribut data pada nilai masing-masing centroid klaster (data anggota

Berdasarkan hasil percobaan dan analisa yang dilakukan pada penelitian ini, maka dapat disimpulkan bahwa Hasil optimasi titik centroid awal dengan algoritma genetika dapat berjalan dengan: [a] Baik, namun masih menemui kelemahan di sisi kecepatannya dalam menemukan titik centroid yang paling optimal [b] Keanggotaan individu mahasiswa pada suatu klaster ditentukan oleh keserupaan setiap parameter data terhadap titik centroid masing-masing klaster.


27


DAFTAR PUSTAKA David E. Goldberg, Genetic Algorithm: in search, optimization & machine learning. Ridho Ali, Deteksi Mahasiswa Berprestasi Dan Bermasalah Dengan Metode Clustering. Ridho Ali, Optimasi Titik centroid awal Kmeans klastering dengan algoritma genetika. Basuki Ahmad, Strategi Algoritma Genetika. Basuki Ahmad, Tips dan trik Algoritma Genetika. Kadir Abdul, Dasar Pemerograman Java 2. Indrajani, Martin, Pemerograman Berbasis Objek Dengan Bahasa Java. Purnomo Untung, Membuat Aplikasi Database Dengan Java 2.


28

DETEKSI MAHASISWA BERPRESTASI DAN BERMASALAH DENGAN METODE K- MEANS KLASTERING YANG DIOPTIMASI DENGAN ALGORITMA GENETIKA

Recommend Documents