Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 2, No. 8, Agustus 2018, hlm. 2926-2932
e-ISSN: 2548-964X http://j-ptiik.ub.ac.id
Klasifikasi pada Penyakit Dental Caries Menggunakan Gabungan K-Nearest Neighbor dan Algoritme Genetika Dennes Nur Dwi Iriantoro1, Candra Dewi2, Delvi Fitriani3 1,2
Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Brawijaya Departemen Ilmu Material Kedokteran Gigi, Fakultas Kedokteran Gigi, Universitas Brawijaya Email:
[email protected],
[email protected],
[email protected]
3
Abstrak Penyakit karies gigi merupakan penyakit yang sering ditemui dalam kasus permasalahan pada kedokteran gigi. Indonesia yang menempati peringkat 6 pada kasus karies gigi 60% β 80% pada populasi di Indonesia. Oleh karena itu perawatan dini pada penyakit karies gigi diharapkan dapat mengurangi tingginya penyakit karies di Indonesia. Sistem untuk klasifikasi pada tipe-tipe karies menggunakan program komputer diharapkan akan mempermudah kinerja dalam bidang kedokteran gigi. Pada permasalahan klasifikasi dengan menggunakan metode K-Nearest Neighbor telah banyak diterapkan pada kasus-kasus lain. Namun metode ini memiliki kekurangan pada penentuan nilai K yang harus dicari sendiri nilai K terbaik untuk klasifikasi. Penelitian ini akan membahas tentang optimasi pada nilai K dalam metode KNN. Penelitian ini akan menggunakan Gabungan K-Nearest Neighbor dan Algoritme genetika. Algoritme genetika dapat menghasilkan solusi yang optimal dengan berbagai variasi serta memiliki kelebihan dari segi kemampuan menghasilkan solusi. Penggunaan optimasi dengan algoritme genetika ini membuat metode K-Nearest Neighbor menjadi lebih mudah digunakan karena tidak harus memilih nilai K optimal secara manual. Hasil yang didapatkan pada pengujian akurasi nilai K oleh optimasi algoritme genetika adalah K optimal dengan akurasi 88 % dan fitness 0,9. Klasifikasi penyakit karies gigi akan lebih bagus menggunakan metode gabungan ini Kata kunci: penyakit karies gigi, klasifikasi, optimasi, k-nearest neighbor, algoritme genetika
Abstract Dental caries disease is a disease commonly encountered in cases of dental problems. Indonesia is ranked 6th in dental caries cases 60% - 80% in the population in Indonesia. Therefore, early treatment expected to reduce the high caries disease in Indonesia. Classification Caries using computer programs is expected to improve performance in the field of dentistry. The problem with using the K-Nearest Neighbor method has been widely applied to other cases. This method has a deficiency in determining the value of K that must be sought alone for K. This study will discuss about the optimization of KNN K method. This study will use the combined K-Nearest Neighbor and Genetic Algorithm. Genetic algorithms can produce optimal solutions with various variations and have advantages in terms of ability. The use of optimization with this genetic algorithm makes K-Nearest Neighbor method easier to use because it does not have to choose manually. The results obtained on the accreditation test by Genetics algorithm quality are optimal K with 88% honesty and 0.9 fitness. Classification of dental caries disease would be better to use this combined method Keywords: Dental caries disease, classification, optimization, k-nearest neighbor, genetic algorithm
1.
permukan gigi oleh asam organic yang dapat disebabkan dari makanan yang mengandung gula. Proses terjadinya karies gigi bisa dimulai dengan adanya plak dipermukaan gigi, Dapat berasal dari sukrosa (gula) dari sisa makanan juga dapat berasal dari bakteri yang menempel dan sewaktu-waktu dapat berubah menjadi asam laktat yang akan menurunkan pH mulut.
PENDAHULUAN
Karies gigi penyakit yang sering kita jumpai pada masalah gigi. Hal ini disebabkan karena Indonesia 60%-80% orang dewasa mengidap penyakit karies gigi. Penyakit ini disebabkan demineralisasi jaringan dari Fakultas Ilmu Komputer Universitas Brawijaya
2926
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
Sehingga akan menyebabkan demineralisasi email berlanjut menjadi karies gigi (Suryawati, 2010). Proses karies melalui emal-dentin dapat menyebabkan perubahan warna putih lokal, coklat hingga hitam. Perubahan ini menyebabkan sulitnya pendeteksian karies gigi. Untuk mendeteksi penyakit karies gigi agar lebih mudah dikenali, maka dilakukan pengelompokan atau klasifikasi. Klasifikasi yang dipakai adalah klasifikasi dari penetian G.V Black. Dengan munculnya kedokteran gigi modern, laju pertumbuhan penyakit karies telah berubah karena kemajuan teknologi kedokteran gigi dan perawatan serta pencegahannya. Dokter gigi sekarang dapat mendiagnosa dan mengobati karies awal, sehingga dapat memberi tindakan pencegahan. Namun melihat secara visual atau dengan gambar pencitraan canggih memiliki tingkat sensivitas yang rendah dan memungkinkan terjadi kesalahan. Banyaknya macam-macam bentuk karies gigi yang membuat kita kesulitan untuk mengenalinya. Oleh karena itu pengembangan klasifikasi pada macam-macam karies gigi dengan menggunakan perangkat komputer akan diprioritaskan (Rahman, 2014). Dari macam-macam bentuk kavitas, gejala atau letak plak yang dapat digunakan untuk memperkirakan pada kelas manakah karies tersebut. Tujuan dari klasifikasi ini adalah agar dokter gigi dapat mengetahui secara cepat kelas kavitas yang diderita pasien sehingga dapat melakukan pengobatan, perawatan atau tindakan pencegahan lebih lanjut. Masalah penentuan kelas pada penyakit karies gigi ini, menggunakan G.V Black berdasarkan lokasi, jaringan keras yang terkena dan tingkat laju perkembangan (Meisida, et al., 2014). Klasifikasi merupakan teknik data mining yang mempunyai tujuan untuk memprediksi label kategori dari benda yang tidak diketahui sebelumnya, untuk membedakan antara objek yang satu dengan lainya berasarkan fitur tertentu. K-Nearest Neighbor adalah salah satu teknik yang paling dasar dan sederhana untuk klasifikasi. KNN memiliki keunggulan pelatihan yang sangat cepat dan sederhana sehingga mudah dipelajari. Selain itu KNN juga sangat efektif untuk pelatihan data yang banyak. Di antara keunggulan KNN tersebut metode ini memiliki kekurangan yaitu nilai K yang kita tidak tahu mana nilai K paling bagus, selain itu
Fakultas Ilmu Komputer, Universitas Brawijaya
2927
dengan keterbatasan memori dan atribut yang tidak relevan (Mutrofin, 2014). Dibutuhkan algoritme yang mampu memperbaiki KNN dalam hal akurasi maupun dalam mengoptimalkan nilai K pada KNN. Dengan perbaikan ini di tujukan agar menjadi lebih optimal dan mendapatkan hasil keakuratan yang bagus. Chirici et al. (2016) menemukan tidak ada konfigurasi KNN tertentu yang dapat dianggap optimal untuk semua model kasus, oleh karena itu direkomendasikan fase optimasi pada setiap aplikasi. Demikian pula, PackalΓ©n et al. (2012) melaporkan bahwa pemilihan subset fitur yang optimal akan menguntungkan. Pemilihan optimal subset variabel fitur mampu melakukan komputasi intensif ketika jumlah variabel tersebut begitu besar. Selanjutnya, jika variabel fitur berkorelasi dengan banyak set variabel fitur penginderaan jauh, metode seleksi bertahap tersebut memiliki kinerja buruk (Harrell, 2001). Untuk aplikasi tersebut, Tomppo dan Halme (2004) memperkenalkan algoritme genetika (GA) sebagai teknik untuk mengoptimalkan konfigurasi KNN, dan penyelidikan berikutnya telah menunjukkan mereka memiliki potensi yang cukup besar untuk tujuan ini (McRoberts, 2012;. McRoberts et al, 2015 ; Tomppo et al, 2009;. Latifi et al, 2010). Algoritme genetika adalah pencarian heuristik yang meniru seleksi alam untuk memecahkan masalah optimasi (Holland, 1975). Algorimta ini dimulai dengan populasi individuindividu yang dipilih secara acak, membandingkan setiap individu sesuai dengan kriteria optimasi. Dan menggabungkan individu sehingga dapat menghasilkan individu tambahan yang lebih optimal. Untuk digunakan dengan KNN, individu merupakan suatu komponen dari konfigurasi KNN termasuk kombinasi variabel fitur atau unsur jarak (McRoberts, 2016). Dengan menggunakan algoritme genetika pada optimasi metode KNN menghasilkan nilai K optimal secara otomatis. Sehingga pengambilan keputusan bisa menggunakan hasil dari metode ini karena metode ini akurasinya terbaik jika dibandingkan dengan KNN saja yang haris mengecek satu persatu (jabbar, 2013). Dari beberapa refrensi diatas dapat disimpulkan bahwa Klasifikasi penyakit karies gigi dapat dilakukan dengan metode K-Nearest Neighbor. Metode K-Nearest Neighbor merupakan metode klasifikasi yang masih memiliki kekurangan. Namun dengan penambahan atau perbaikan menggunakan
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
algoritme genetika mampu mengurangi kekurangan tersebut sehingga hasil diharapkan akan lebih optimal. Oleh karena itu peneliti tertarik melakukan penelitian dengan judul βKlasifikasi pada Penyakit Dental Caries Menggunakan Gabungan K-Nearest Neighbor dan Algoritme Genetikaβ. 2.
PENYAKIT KARIES GIGI
Karies merupakan suatu penyakit jaringan keras gigi, yaitu email, dentin dan sementum, yang disebabkan oleh aktivitas bakteri Streptococcus mutans dalam karbohidrat yang terfermentasi. Tandanya adalah adanya demineralisasi jaringan keras gigi yang kemudian diikuti oleh kerusakan bahan organik. Karies adalah suatu penyakit yang disebabkan oleh mikroba yang dimulai dengan demineralisasi komponen organik gigi, kemudian terjadi destruksi komponen organik, yang akan menyebabkan terbentuknya kavitas (Sasmita, 2012). Karies gigi atau biasa disebut dengan gangguan gigi berlubang merupakan gangguan kesehatan yang paling umum. Berdasarkan suatu penelitian yang dilakukan di benua Eropa dan Asia, 80% lebih anak-anak yang berada pada umur dibawah 18 tahun lebih banyak terserang karies gigi. Namun sekarang remaja pun dapat terkena karies gigi. Timbulnya karies gigi disebabkan karena kurangnya perhatian untuk menjaga kesehatan pada gigi. Pola konsumsi makanan yang dapat memicu timbulnya serangan karies gigi harus dikurangi. Bila proses dari karies sudah menembus pada bagian email dan mengenai dentin, prosedur operatif yang sesuai merupakan indikasi dari perawatanya. (Sasmita, 2012). 3.
KLASIFIKASI G.V BLACK
Untuk memudahkan mendeteksi penyakit karies gigi, maka telah dilakukan pengelompokkan atau klasifikasi oleh G.V Black.Berikut adalah klasifikasi gigi menurut G.V. Black: 1. Kelas 1: Kavitas pada semua pit dan fissure gigi, terutama pada premolar dan molar. 2. Kelas 2: Kavitas pada permukaan approksimal gigi posterior yaitu pada permukaan halus / lesi mesial dan atau distal biasanya berada di bawah titik kontak yang sulit dibersihkan. Dapat digolongkan sebagai kavitas MO (mesio-oklusal), DO
Fakultas Ilmu Komputer, Universitas Brawijaya
3.
4. 5.
6.
4.
2928 (disto-oklusal) dan MOD (mesio-oklusaldistal). Kelas 3: Kavitas pada permukaan approksimal gigi- gigi depan juga terjadi di bawah titik kontak, bentuknya bulat dan kecil. Kelas 4: Kavitas sama dengan kelas 3 tetapi meluas sampai pada sudut insisal Kelas 5: kavitas pada bagian sepertiga gingival permukaan bukal atau lingual,lesi lebih dominan timbul dipermukaan yang menghadap ke bibir/pipi dari pada lidah. Selain mengenai email,juga dapat mengenai sementum. Kelas 6: Terjadi pada ujung gigi posterior dan ujung edge insisal incisive. Biasanya pembentukkan yang tidak sempurna pada ujung tonjol/edge incisal rentan terhadap karies. K-NEAREST NEIGHBOR
KNN adalah singkatan dari K-Nearest Neighbor merupakan adalah metode untuk melakukan klasifikasi terhadap objek sesuai dengan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. Data pembelajaran diproyeksikan ke ruang berdimensi banyak, dimana tiap dimensi merepresentasikan fitur dari data. Algoritme ini mengklasifikasikan data baru yang belum diketahui kelasnya atau memprediksi kelas dengan data sejumlah k yang letaknya terdekat dari data baru tersebut. Kelas terbanyak dari data terdekat sejumlah k tersebut dipilih sebagai kelas yang diprediksikan untuk data yang baru. Nilai k umumnya ditentukan dalam jumlah ganjil untuk menghindari munculnya jumlah jarak yang sama dalam pengklasifikasian. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan jarak Euclidean (J. Nilson, 1996). Untuk menghitung jarak antara data latih dan data uji menggunakan Euclidean distance dapat dilihat pada persamaan (1) (Moradian et al., 2009). π
πββπ=1(π2π β π1π)2
(1)
π1π = data latih dan π2π = data uji, dilakukan sebanyak jumlah data dan menghasilkan jarak. Selanjutnya jarak akan diurutkan dimulai dari jarak paling terdekat dengan nilai jarak yang terkecil. Lalu memberikan nilai K untuk menentukan hasil klasifikasi.
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
5.
ALGORITME GENETIKA
Konsep Algoritme Genetika terinspirasi dari ilmu genetika pada makhluk hidup dilihat dari sebagian besar istilah yang dipakai dalam algoritme genetika. Prinsip evolusi yang terjadi pada makhluk hidup yaitu memepertahankan keberadaan suatu individu dengan mencoba beradaptasi secara terus menerus untuk menjadi individu baru yang kuat (Sutojo, 2011). Dapat disimpulkan bahwa jika solusi dari proses optimasi yang dihasilkan adalah baik, maka solusi tersebut akan dipakai sebagai acuan untuk menghasilkan solusi yang lebih optimal. Algoritme Genetika menghasilkan solusi yang optimal dengan berbagai variasi obyektif serta memiliki banyak kelebihan dibandingkan dengan algoritme lainnya dilihat dari segi kemampuannya untuk menghasilkan (Mahmudy, 2013), juga pada penggunaan variable yang bervariasi dan memiliki kerumitan yang tinggi (Mahmudy, 2013), serta adanya pengaruh solusi dari permasalahan yang lain untuk menyelesaikan permasalahan yang sedang diteliti dengan waktu yang relatif singkat (Mahmudy, 2013). 6.
METODE PENELITIAN
Data yang akan diteliti adalah data dari rekap medis penyakit karies gigi di RSUB malang. Data karies gigi adalah data pasien penderita karies gigi yang terdiri dari 8 atribut, 6 kelas dan 100 data. Tahap awal desain sistem adalah merumuskan kontribusi utama dari penelitian ini. Berikut atribut: X1 = karies terdapat pada permukaan aproksimal (mesial dan distal) X2 = karies terdapat pada pit X3 = karies terdapat pada permukaan palatal X4 = karies terdapat pada fasial X5 = karies terdapat pada lingual gigi X6 = posisi gigi anterior X7 = posisi gigi posterior X8 = posisi gigi insisal Langkah-langkah untuk melakukan proses optimasi nilai K menggunakan algoritme genetika yakni sebagai berikut: 1. Masukan data latih misal pada penelitian ini menggunakan 100 data pasien karies gigi dari RSUB malang 2. Menentukan ukuran populasi awal dan ukuran cromosom awal. Misal populasi yang diinginkan adalah 10 dengan panjang ukuran cromosom 6. Fakultas Ilmu Komputer, Universitas Brawijaya
2929
3. Maka akan secara random akan dibangkitakan populasi sebanyak 10 dengan nilai dalam cromosom antara 0 dan 1. Misal hasil yang didapatkan kromosom adalah 000010 maka nilai K tersebut adalah 2 dan 001001 adalah 9. Panjang kromosom akan dibatasi dengan K<100. 4. Dilakukan proses Crossover dan mutasi dengan ketentuan nilai Crossover rate dan Mutation rate. dari proses ini akan didapatkan individu baru. Misal dalam penelitihan ini menggunakan kombinasi Cr 0,2 dan Mr 0,2. 5. Hitung nilai fitnes dengan menggunakan nilai validitas. Rata-rata dari setiap K pada nilai validitas akan menjadi fitnes terbaik. (π, π) {1 a = b 0a β b
(2)
Keterangan: S = nilai similaritas antar data latih a dan b = label kelas antar data latih. Setelah itu dilanjutkan dengan melakukan validasi pada data bergantung pada nilai k terdekat dimana tujuan perhitungan untuk menghitung jumlah titik dengan label yang sama pada latih (Parvin, 2010). Validasi ini nantinya akan digunakan untuk menemukan nilai fitnes. πππππππ‘π¦ (π₯) = 1 π» βπ=1 π(πππ(π₯), πππ(ππ (π₯))) π»
(3)
Dimana: = Jumlah titik terdekat (π₯) = Label kelas titik terdekat Hitung nilai fitness dengan menggunakan rata-rata dari nilai validasi. Rumus validasi terdapat pada persamaan (3).
f ( x ) ο½ ο₯ i ο½ K ο½ V /jml
(4)
Dimana: f(x) = nilai fitness K = jumlah data pertetangga V = validasi i Jml = jumlah data latih 6. Seleksi menggunakan elitism sehingga individu yang memiliki nilai fitnes kecil tidak akan masuk dalam populasi yang baru. 7. Didapatkan individu baru dari nilai fitness terbaik. 8. Ulangi tahapan di operasi genetika hingga sejumlah n generasi dan mendapatkan nilai
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
7.
2930
K optimal. Lalu dari nilai K yang didapatkan masukan dalam algoritma KNN
sehingga diberhentikan. Sehingga populasi yang terbaik adalah 35.
SKENARIO DAN HASIL
7.2 Uji Ukuran Generasi
7.1 Uji Ukuran Populasi Pada pengujian parameter ukuran populasi akan dilakukan dengan menguji dengan jumlah populasi sebanyak kelipatan dari 5. Dimulai dari 10 hingga dilakukan 7 kali pengujian hingga pada jumlah ukuran populasi 40. Pada pengujian ini mengguakan 6 gen pada setiap kromosom. Untukj mendapatkanj hasil yangj lebihj valid makaj setiap percobaanj akan dilakukan sebanyakj 5 kali untuk diambil nilai rata-rata fitnessnya. Pada percobaan ini digunakan jumlah generasi sebanyak 10 kali generasi, cr = 0,2j dan mr = 0,2. Hasil dari skenario uji ukuran populasi dapat di jelaskan menggunakan tabel 1. Tabel 1 Hasil Uji Coba Berdasarkan Jumlah Populasi Ukuran Populasi
1
2
3
4
5
Ratarata fitness
10
0,90
0,86
0,70
0,86
0,71
0,874
15
0,87
0,72
0,92
0,86
0,84
0,874
20
0,90
0,84
0,86
0,92
0,92
0,882
25
0,88
0,87
0,88
0,90
0,87
0,882
30
0,90
0,84
0,84
0,90
0,88
0,89
35
0,90
0,90
0,90
0,90
0,90
0,905
40
0,90
0,90
0,90
0,90
0,90
0,905
Nilai fitness Percobaan ke-
Dari Tabel 1 dapat digambarkan dalam sebuah grafik untuk melihat dengan jelas hasil uji coba pada ukuran populasi terhadapn nilai fitness. Dan grafik hasil uji coba ukuran populasi dapat dilihat pada Gambar 1.
Pengujian pengujian jumlah generasi yang digunakan dalam sistem yang dimulai dari ukuran generasi ke 5 hingga sebanyak 5 kali. Pada pengujian ini menggunakan Cr dan Mr sebanyak 0,2, dengan panjang gen 6 dan jumlah populasi sebanyak populasi terbaik yaitu 35. Hasil dari skenario uji ukuran generasi dapat di jelaskan menggunakan tabel 2. Tabel 2 Hasil Uji Coba Berdasarkan Jumlah generasi Ukuran Generasi
Nilai fitness Percobaan ke1
2
3
4
5
Ratarata fitness
5
0,90
0,87
0,884
0,875
0,883
0,8843
10
0,90
0,90
0,905
0,92
0,715
0,8701
15
0,88
0,87
0,905
0,90
0,92
0,8976
20
0,92
0,92
0,92
0,883
0,92
0,9126
25
0,92
0,92
0,92
0,883
0,92
0,9126
Dari Tabel 2 dapat dibuat sebuah grafik untuk melihat dengan jelas hasil dari uji coba banyaknya generasi terhadap nilai fitness. Dan grafik hasil uji coba jumlah generasi dapat dilihat pada Gambar 2.
0,92
Grafik Percobaan Jumlah Generasi
0,9 0,88 0,86 5
Grafik Percobaan Ukuran Populasi
ukuran
10
15
20
25
Gambar 2. Grafik Percobaan Jumlah Generasi
0,95 0,9 0,85 0,8 0,75 10
15
20
25
30
35
40
Gambar 1. Grafik Percobaan Ukuran Populasi
Berdasarkan Gambar 1 dapat dilihatj bahwa pengujian menggunakan rata-rata fitness tiap percobaan mendapatkan hasil yang meningkat ketika pada awal populasi sekitar 10-20. Setelah pada populasi 35 dan seterusnya hasilnya sama, Fakultas Ilmu Komputer, Universitas Brawijaya
Berdasarkan Gambar 2 pada generasi 10 mendapatkan rata-rata fitness yang meningkat mengalami penurunan pada percobaan generasi 15. Namun generasi yang dicoba selanjutnya sama saja dengan populasi 10 maka selanjutnya akan terjadi konvergensi dini yang dikarenakan nilai fitness yang dihasilkan cenderung sama atau tidak terdapat perbedaan yang signifikan. Sehingga diambil nilai pada saat awal terbaik generasi tersebut didapatkan (Fakhiroh, et al., 2015).
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
2931
7.3 Uji Panjang Ukuran Chromosome
7.4 Uji Kombinasi Cr dan Mr
Pengujian pada panjang ukuran kromosom ini dilakukan dari kromosom yang terpandek hingga paling panjang dalam batasan nilai binner chromosome tidak melebihi jumlah data latih. Pada percobaaan ini dilakukan panjang ukuran chromosome dari 2 hingga 6. Dilakukan dengan nilai 2 karena jika 1 tidak akan dapat dilakukan proses crossover selain itu jika hanya 1 nilai K tidak termasuk. Dilakukan batas dengan panjang kromosom 6, karena jika nilai chromosome 6 jumlah binner maksimal tidak melebihi nilai K. Dilakukan percobaan dengan jumalh populasi 35, banyak generasi 10 dan Cr dan Mr 0,2 dan 0,2. Hasil dari skenario uji panjang ukuran chromosome dapat di jelaskan menggunakan tabel 3.
Pengujian selanjutnya yaitu pengujian nilai Cr dan Mr. Pada pengujian ini menggunakan jumlah generasi sebanyak 10 dengan menggunakan panjang Chromosome 6 dan populasi sebanyak 35. Pada percobaan ini dilakukan sebanyak 5 kali untuk mendapatkan hasil yang lebih valid. Kombinasi dari Cr dan Mr akan digunakan untuk melakukan percobaan ini. Hasil dari skenario uji kombinasi Cr dan Mr dapat di jelaskan menggunakan tabel 4.
Tabel 3. Hasil Uji Coba Panjang Ukuran Cromosom Nilai fitness Percobaan ke-
Ukuran Kromosom
1
2
3
4
5
Ratarata fitness
2
0,905
0,90
0,905
0,90
0,90
0,905
3
0,905
0,90
0,905
0,90
0,90
0,905
4
0,905
0,90
0,905
0,90
0,90
0,905
5
0,905
0,90
0,905
0,90
0,90
0,905
6
0,905
0,90
0,905
0,90
0,90
0,905
Pada penguijian panjang chromosome semua pengujian mendapatkan nilai fitnes yang sama baiknya. Hal ini dapat digambarkan pada gambar 3. Grafik Percobaan Jumlah Chromosome 1
Tabel 4. Hasil Uji Coba Kombinasi Cr dan Mr Ukuran Cr dan Mr
1
2
3
4
5
Ratarata fitness
0,2 :0,6
0,905
0,90
0,905
0,90
0,90
0,905
0,3 :0,5
0,905
0,90
0,905
0,90
0,90
0,905
Nilai fitness Percobaan ke-
0,4 :0,4
0,905
0,90
0,905
0,90
0,90
0,905
0,5 :0,3
0,905
0,90
0,905
0,90
0,90
0,905
0,6 :0,2
0,905
0,90
0,905
0,90
0,90
0,905
Dari tabel 4 dapat dibuat sebuah grafik untuk melihat dengan jelas hasil dari uji coba kombinasi cr dan mr terhadap nilai fitness. Dan grafik hasil uji coba kombinasi cr dan mr dapat dilihat pada Gambar 4. Grafik Percobaan kombinasi CR dan Mr 1 0,8 0,6 0,4 0,2 0 2
0,8 0,6
3
4
5
6
Gambar 4. Grafik Percobaan Jumlah Kombinasi Cr dan Mr
0,4 0,2 0 2
3
4
5
6
Gambar 3. Grafik Percobaan Jumlah Cromosom
Pada percobaan ini terlihat nilai fitnes yang sama saja dalam keadaan terbaik. Namun jika menggunakan kromosom yang pendek kita tidak dapat mendapatkan banyak kemungkinan. Karena jika chromosome pendek maka nilai K juga pendek.
Fakultas Ilmu Komputer, Universitas Brawijaya
Pada grafik diatas menjelaskan bahwa setiap kombinasi dari Cr dan Mr mendapatkan hasil fitness yang terbaik. Sehingga dapat menggunakan berbagai macam kombinasi Cr dan Mr pada algoritma genetika yang telah dibuat karena bebbagai macam kombinasi hasilnya tetap bagus. 7.5 Uji Akurasi Pengujian akurasi akan dilakukan dengan melakukan akurasi pada beberapa metode yang pertama adalah metode tanpa adanya optimasi pada nilai K pada metode KNN. Dibandingankan dengan yang menggunakan
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
optimasi GA. Dengan menggunakan jumlah data latih yang berbeda. Hasil dari skenario uji akurasi dapat di jelaskan menggunakan tabel 5. Tabel 5 Hasil Uji Akurasi Akurasi
Data latih
K
90
2
88%
0,9
3
88%
0,9
5
86%
0,88
10
88%
0,75222
13
94%
0,70085
15
92%
0,65407
25
82%
0,46844
GAKNN
Fitnes
Pada pengujian akurasi diatas menggunakan jumlah data uji sebanyak 50 data uji. Menggunakan jumlah data latih yang berbeda-beda. Nilai K yang optimal yang didapatkan oleh GAKNN adalah pada nilai K=2. Nilai K yang didapatkan GAKNN tidak mendapatkan akurasi yang terbaik, namun GAKNN mendapatkan nilai Fitness yang terbaik. Sehingga nilai K yang didapatkan memiliki kemungkinan lebih bagus. Hal ini dikarenakan fitnes terbaik memiliki banyak kemungkinan data mirip. Klasifikasi penyakit Dental Caries diklasifikasikan menggunakan KNN yang telah teroptimasi oleh algoritme genetika. Pada pengujian akurasi mendapatkan nilai akurasi sebesar 88%. Sedangkan pada akurasi terbesar terletak pada nilai K = 13 dengan akurasi sebesar 94 %. Memang dalam ukuran akurasi GAKNN mendapatkan nilai akurasi lebih kecil. Namun pada penelitihan ini nilai K paling optimal yang didapatkan dari pengukuran nilai fitnes terbesar. Nilai fitness terbesar mendapatkan kemungkinan lebih bagus. Disini nilai fitnes K = 2 adalah 0.9 sedangkan K=13 adalah 0,70085.
menggunakan mutation cut point serta penyeleksian dengan metode elitism selection. 2. Untuk jmengukur kualitasj solusi yang paling baik pada jpermasalahan optimasij nilai K pada metode KNN yaituj dengan jmelihat nilai jfitness tertinggi. Fitnessj yang paling tinggi jadalah individuj yang memilikij solusi yangj palingj optimum dari jsistem. Pada pengujianj diperoleh jnilai fitness tertinggij sebesarj 0.9. 3. Pengujian parameter pada algoritme genetika memilikij pengaruh terhadapj nilai fitnessj yang didapatkan. Dari pengujian yang dilakukan dapat jdisimpulkan bahwaj nilai fitness yang jdihasilkan dipengaruhi oleh ukuranj populasi yangj semakin tinggi, namunj jika ukuran populasi dan generasi jsemakin tinggij tidak didapatkanj kenaikanjj fitness yangj signifikan dan jwaktu komputasinyaj akan berjalan semakin lama. Nilai fitness yang didapatkan oleh setiap individu dipengaruhi oleh pola data latih. Pola data latih yang digunakan sangat mempengaruhi nilai fitnes yang didapatkan karena nilai fitnes yang dipakai adalah nilai dari validasi data latih yang dicari nilai rata-ratanya. Sehingga jika pada pola data latih yang digunakan cenderung memiliki banyak macam pola yang berbeda-beda tiap kelasnya dimungkinkan akan mendapatkan hasil yang berbeda dalam setiap uji coba parameter algoritme genetika yang dilakukan. DAFTAR PUSTAKA Suryawati, P., 2010. 100 Pertanyaan Penting Perawatan Gigi Anak. Dian Rakyat, jakarta. Inne
8.
KESIMPULAN
Kesimpulan jyang diperoleh dari hasil uji coba yangjtelahjdilakukan mengenaijpenerapan algoritma genetika dalam menyelesaikan permasalahan optimasi nilai K pada metode KNN yaitu sebagai berikut: 1. Algoritma jgenetika yang diaplikasikan pada permasalahan optimasi nilai K pada metode KNN dalam kasus penyakit Dental Caries dengan menggunakan representasi kromosom dalam bilangan binner, Crossover dengan cara one cut point dan Fakultas Ilmu Komputer, Universitas Brawijaya
2932
Suherna, A. .2012. Identifikasi, Pencegahan, dan Restorasi sebagai Penatalaksanaan Karies Gigi pada Anak. Fakultas Kedokteran Gigi Universitas Padjadjaran.
Chittu, V, N., 2011. A Modified Genetic Algorithm Initializing K-Means Clustering. Global Journal of Computer Science and Technology, 11(2). Fakhiroh, D., Mahmudy, W., 2015. Optimasi Komposisi Pakan Sapi Perah Menggunakan Algoritma Genetika. Repository Jurnal
Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer
Mahasiswa PTIIK Universitas Brawijaya, Volume 5. Mahmudy, W., 2013. Algoritma Evolusi. malang : program teknologi informasi dan ilmu komputer: Universitas Brawijaya. MD Anisur Rahman, M. Z. I., 2014. A hybrid clustering technique combining a novel genetic algorithm with K-Means. Centre for Research in Complex Systems, School of Computing and Mathematics, pp. 345-365. Meisida, N., Soesanto, O. & Chandra, H. K., 2014. K-Means untuk KLASIFIKASI PENYAKIT KARIES GIGI. Kumpulan jurnaL Ilmu Komputer (KLIK), Volume 01, p. 11. Mount, G. J., 2009. Minimal intervention dentistry : cavity classification & preparation. Scientific, pp. 150-62. R. Gil-Pita, X. Y., 2007. Using a Genetic Algorithm for Editing k-Nearest Neighbor Classifiers. p. 1141β1150. Ronald E. M., 2016. Using genetic algorithms to optimize k-Nearest Neighbors configurations for use with airborne laser scanning data. Remote Sensing of Environment. Siti
M., 2014. Optimization Techniques Modified k Nearest Neighbor Classification Using Genetic Algorithm. Jombang: JURNAL GAMMA.
Sutojo, T. M., 2011. Kecerdasan Buatan. Yogyakarta: Andi Publisher.
Fakultas Ilmu Komputer, Universitas Brawijaya
2933
