Pendiskritan Kelas Kontinyu dengan Algoritma K-Mean Cluster Kusrini Dosen STMIK AMIKOM YOGYAKARTA
[email protected] Abstract
Dalam proses pembentukan pengetahuan sering ditemui algoritma yang menyaratkan data dalam bentuk kelas diskrit, padahal dalam dunia nyata sering ditemui data dalam bentuk kelas kontinyu. Proses pengubahan data dalam kelas kontinyu menjadi data dalam kelas diskrit dapat dilakukan dengan cara manual,yaitu analis mendefinisikan interval nilai data kelas kontinyu yang akan dimasukkan dalam suatu kelas diskrit. Kelemahan dari pengubahan data dalam kelas kontinyu menjadi data dalam kelas diskrit diantaranya:1. tingkat akurasi tidak pasti, tergantung pada kepiawaian analis dalam menentukan kelas diskrit. 2. adanya data dalam kelas kontinyu yang memiliki kelas diskrit ganda. 3. adanya data dalam kelas kontinyu yang tidak memiliki kelas dalam kelas diskrit. 4. diperlukan usaha dari analis Dalam makalah ini, penulis memaparkan suatu metode pengubahan data kelas kontinyu menjadi data dalam kelas diskrit dengan menggunakan algoritma k-mean cluster. Metode ini berhasil diimplementasikan dengan script PHP dan DBMS My Sql. Hasil implementasi mampu mengubah tabel berisi data kelas kontinyu menjadi tabel berisi data kelas diskrit. Kata kunci : diskrit, kontinyu, k-mean cluster Pendahuluan Dalam proses pembentukan pengetahuan seringkali para peneliti dihadapkan pada algoritma yang hanya manangani data kelas diskrit, sementara data yang tersedia merupakan data kelas kontinyu(Quinlan, J.R, 1993). Yang dimaksud dengan data diskrit adalah data yang sifatnya terputus-putus, nilainya utuh (bukan pecahan), misalnya data jumlah penduduk dan jumlah kendaraan. Sedangkan data kontinyu adalah data yang sifatnya sinambung atau kontinyu, nilainya bisa berupa pecahan. Contoh data kontinyu yaitu data tentang panjang jalan dan data berat badan seorang anak(Kuswadi dan Mutiara, E., 2004).
Proses pendiskritan kelas kontinyu akan mengubah data kelas kontinyu menjadi data kelas diskrit. Misalnya temperatur nilainya tidak lagi 30,7 oC atau 36 oC tetapi teperatur rendah, sedang dan tinggi. Pengkonversian data kelas kontinyu kedalam kelas diskrit memerlukan pendefinisian interval nilai data kelas kontinyu untuk masing-masing kelas diskrit. Misalnya kelas diskrit temperatur rendah adalah konversi dari kelas kontinyu temperatur dengan nilai data antara 30 oC sampai dengan 34 oC. Pembentukan kelas diskrit dapat dilakukan secara manual. Pembuat sistem akan mendefinisikan terlebih dahulu interval-interval kelas kontinyu yang masuk dalam suatu kelas diskrit. Tetapi hal ini dapat menyebabkan pembagian kelas yang tidak seimbang, suatu nilai dalam kelas kontinyu masuk ke beberapa kelas diskrit atau suatu nilai dalam kelas kontinyu tidak masuk dalam salah satu kelas diskrit. Selain itu, proses pembentukan kelas diskrit secara manual memerlukan usaha dari analis. Tentu saja hal ini tidak efektif dan tidak efisien. Penulis pernah melakukan proses pembentukan kelas diskrit secara manual dalam pra proses pembentukan pengetahuan dengan menggunakan pohon keputusan. Algoritma yang penulis gunakan dalam pembentukan pohon keputusan adalah algoritma C4.5 dan algoritma nearest neighbor. Dengan proses pembentukan kelas diskrit secara manual ini ternyata menyulitkan untuk mendapatkan performa algoritma pembentukan pohon keputusan. Hal ini disebabkan nilai akurasi dari pengetahuan yang terbentuk sangat tergantung pada proses pembentukan kelas diskritnya(Kusrini dan Harjoko, A., 2008)(Kusrini dah Hartati, S, 2007). Berdasarkan pengalaman penulis tersebut, penulis menganggap perlu dibuat sebuah algoritma pembentukan kelas diskrit secara otomatis. Pada makalah ini, penulis ingin memaparkan hasil penelitian untuk melakukan proses pembentukan kelas diskrit secara otomatis. Proses ini memanfaatkan algoritma clustering k-mean cluster. Algoritma K-Mean Cluster K-Means merupakan salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster/kelompok. Metode ini mempartisi data ke dalam cluster/kelompok sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain.
Adapun tujuan dari data clustering ini adalah untuk meminimalisasikan objective function yang diset dalam proses clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster. Data clustering menggunakan metode K-Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut(Agusta, Y., 2007): 1. Tentukan jumlah cluster 2. Alokasikan data ke dalam cluster secara random 3. Hitung centroid/rata-rata dari data yang ada di masing-masing cluster 4. Alokasikan masing-masing data ke centroid/rata-rata terdekat 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan di atas nilai threshold yang ditentukan Rancangan Sistem Dalam makalah ini akan ditunjukkan proses pengubahan tabel dengan data berisi kelas kontinyu menjadi tabel dengan data berisi kelas diskrit. Skema pengubahan tabel akan ditunjukkan pada Gambar 1.
Gambar 1. Skema pengubahan tabel dengan kelas kontinyu menjadi tabel dengan kelas diskrit Pada algoritma k-mean asli, nilai centroid awal ditentukan secara acak. Namun dengan pertimbangan kecepatan, peneliti menetapkan nilai awal centroid kelas dengan suatu nilai dengan menggunakan rumus 1:
ci =
min + (i − 1) x(max − min) max − min + n 2 xn
[1]
dimana ci
: centroid
min
: nilai terkecil dari data kelas kontinyu
max
: nilai terbesar dari data kelas diskrit
n
: jumlah kelas diskrit
dari kelas ke i
Misalnya dimiliki data dalam kelas kontinyu dengan nilai : 2, 4, 5, 7, 10, 12, 20. Akan dibuat 2 kelas diskrit. Besarnya centroid kelas diskrit pertama adalah:
2 + (1 − 1) x(20 − 2) 20 − 2 + 3 2 x3 2 18 c1 = + 3 6 c1 = 3,33 c1 =
2 + (2 − 1) x(20 − 2) 20 − 2 + 3 2 x3 20 18 + c2 = 3 6 c 2 = 12.6 c2 =
2 + (3 − 1) x(20 − 2) 20 − 2 + 3 2 x3 38 18 c3 = + 3 6 c3 = 18.67 c3 =
Proses pembentukan kelas diskrit dilakukan dengan langkah-langkah sebagai berikut:
1.
Tentukan kolom ($kolom_variabel) dan tabel ($tabel_variabel) asal data kelas kontinyu
2.
Tentukan jumlah kelas diskrit yang diinginkan ($n)
3.
Definisikan array dengan nama $data
4.
Ambil data dari $kolom_variabel
SQL : select `$kolom_variabel` from `$tabel_variabel` 5.
Masukkan hasil SQL ke dalam $data
6.
Cari nilai terendah dari nilai-nilai pada array $data ($min)
7.
Cari nilai tertinggi dari nilai-nilai pada array $data ($max)
8.
Tentukan $delta, yaitu nilai error yang bisa ditoleransi
9.
Hitung $error = $delta * ($max-$min)
10. Cari centroid awal dengan menggunakan rumus 1 11. Tentukan $keluar = false 12. $keluar = false, lakukan langkah berikut: a.
$l = 1
b.
Jika $l <= $n, lakukan $jml_elemen [$l] = 0, jika tidak loncat ke langkah 12.d
c.
$l = $l + 1, kembali ke langkah 2.b.
d.
$k = 0
e.
Jika $k < jumlah elemen array $data, lakukan: i. $jarak = $max ii. $l = 1 iii. Jika $l <= $n, lakukan Jika $jarak >= |$data[$k]-$c[$l]|, lakukan: $kelas_terpilih = $l $jarak = |$data[$k]-$c[$l]|
iv. $jml_elemen[$kelas_terpilih] = $jml_elemen[$kelas_terpilih] +1 v. $kelas[$kelas_terpilih][$jml_elemen[$kelas_terpilih]] $data[$k]
=
Jika tidak loncat ke langkah 12.g f.
$k = $k+1, kembali ke langkah 12.e
g.
$keluar = true
h.
$k = 1
i.
Jika $k <= $jml_kelas, lakukan i. Jika (count($kelas[$k]) > 0) lakukan $mean[$k] = array_sum($kelas[$k])/count($kelas[$k]) Jika tidak $mean[$k] = $c[$k]; ii. Jika abs($mean[$k]-$c[$k]) > $error lakukan $keluar = false Jika tidak loncat ke langkah 12.k
j.
$k = $k+1, kembali ke langkah 12.i
k.
$k = 1
l.
Jika $keluar = false, lakukan i. $k= 1 ii. Jika $k <= $jml_kelas, unset $kelas[$k], jika tidak loncat ke langkah 12.l.iv iii. $k = $k + 1, kembali ke langkah 12.l.ii iv. $k = 1 v. Jika $k <= $jml_kelas, $c[$k] = $mean[$k], jika tidak loncat le langkah 12.m
vi. $k = $k + 1, kembali ke langkan 12.i.v m. Kembali ke langkah 12 Jika tidak loncat ke langkah 13 13. $k = 1 14. Jika $k <= $jml_kelas, masukkan data kedalam database : "insert into kategori (`variabel`, `kelas`, `centroid`) values ('".$kolom_variabel."',".$k.",".$c[$k].")" Jika tidak loncat ke langkah 16 15. $k = $k + 1, kembali ke langkah 14 16. selesai. Hasil dan Pembahasan Peneliti mengimplementasikan algoritma pengubahan tabel dengan variabel kontinyu menjadi tabel dengan kelas diskrit dengan menggunakan script PHP dan software pengelola database MY SQL. Dalam mengimplementasikan, peneliti membuat tiga buah tabel, yaitu: 1.
Tabel kasus_kontinyu, merupakan tabel dengan variabel kontinyu. Tabel ini diasumsikan sudah berisi data. Sebagai contoh dibuat tabel dengan nama tabel kasus_kontinyu. Struktur tabel kasus_kontinyu ditunjukkan pada tabel 1 dan isi tabel kasus kontinyu ditunjukkan pada tabel 2. Tabel 1. Struktur tabel kasus_kontinyu Variabel
Tipe
Konstraint
Kode
Integer
Primary key
Data
Decimal (15,2)
-
Tabel 2. Isi tabel kasus_kontinyu
2.
Kode
Data
1
2
2
4
3
5
4
7
5
10
6
12
7
20
Tabel Kasus_diskrit, merupakan tabel dengan variabel diskit. Pada awalnya tabel ini harus merupakan tebel kosong, yang kemudian akan diisi dengan dengan data dari tabel kasus_kontinyu yang telah dikonversi dalam bentuk diskrit. Struktur tabel kasus_diskrit ditunjukkan pada tabel 3. Tabel 3. Struktur tabel kasus_diskrit
3.
Variabel
Tipe
Konstraint
Kode
Integer
-
Data
Decimal (15,2)
-
Tabel Kategori, merupakan tabel pemetaan kelas diskrit dengan interval yang ada pada kelas kontinyu. Struktur tabel kategori ditunjukkan pada tabel 4. Tabel 4. Struktur tabel kasus_diskrit Variabel
Tipe
Konstraint
variabel
Varchar (30)
-
kelas
integer
-
centroid
decimal (15,2)
-
Peneliti malakukan ujicoba dengan menetapkan delta sebesar 0,1 dan jumlah kelas 3. Setelah proses konversi, isi tabel kategori ditunjukkan pada tabel 5, dan isi tabel kelas_diskrit ditunjukkan pada tabel 6. Tabel 5. Isi Tabel Kategori variabel
kelas
Centroid
Data
1
4.5
Data
2
11
data
3
20
Tabel 5. Isi Tabel kasus_diskrit kode
data
1
1
2
1
3
1
4
1
5
2
6
2
7
3
Penutup Berdasarkan hasil ujicoba yang peneliti lakukan ternyata algoritma k-mean cluster dapat digunakan untuk mengubah tabel kelas kontinyu menjadi tabel kelas variabel. Peneliti telah berhasil mengimplementasikan algoritma untuk mengubah tabel kelas kontinyu menjadi tabel kelas diskrit dengan menggunakan script PHP dan software pengelola database MY SQL.
Daftar Pustaka Agusta, Y., 2007, ”K-Means – Penerapan, Permasalahan dan Metode Terkait”, Jurnal Sistem dan Informatika Vol. 3, 2007, 47-60 Kusrini dan A. Harjoko, 2008, “Decision Tree As Knowledge Management Tool in Image Classification”, Proceedinds of Knowledge Management International Conference 2008. Malaysia Kusrini dan S. Hartati, 2007, “Penggunaan Pohon Keputusan untuk Menganalisis Kemungkinan Pengunduran Diri Calon Mahasiswa Baru di STMIK AMIKOM Yogyakarta”, Prosiding Seminar Nasional Teknologi 2007 Kusrini dan S. Hartati, 2007, “Implementation of C4.5 Algorithm to evaluate the Cancellation Possibility of New Student Applicants”,
Procedings of The
International Conference on Electrical Engineering and Informatics Kuswadi dan Mutiara, E., 2004, DELTA: Delapan Langkah dan Tujuh Alat Statistik untuk Peningkatan Mutu Berbasis Komputer, PT. Elex Media Komputindo Quinlan, J.R, 1993, C4.5 Programs for Machine Learning, Morgan Kaufman Publisher
