Seminar Nasional Matematika dan Aplikasinya 2013
Jaringan Syaraf Tiruan dengan Pembelajaran Algoritma Genetika dan Diversitas untuk Deteksi Kelas Penyakit Abidatul Izzah 1), Ratih Kartika Dewi 2) 1)2)
Jurusan Teknik Informatika ITS Surabaya Jl. Teknik Kimia Kampus Teknik Informatika ITS Surabaya 1)
2)
[email protected] [email protected]
Abstract— Dewasa ini pendeteksian suatu penyakit tidak hanya dilakukan oleh ahli medis namun juga dapat dilakukan oleh sistem cerdas. Perkembangan ilmu ini dapat membantu kinerja ahli medis sebagai pertimbangan untuk pengambilan keputusan dalam diagnosa suatu penyakit. Seiring perkembangan dari soft computing, maka metode tersebut dapat digunakan untuk mendiagnosa suatu penyakit. Diantara soft computing yang pernah dikembangkan adalah Jaringan Syaraf Tiruan (JST) dan Algoritma Genetika (GA). JST memiliki keunggulan dengan adanya proses pembelajaran sedangkan GA merupakan algoritma evolusioner untuk optimasi yang memiliki kelemahan terjebak pada lokal optimum. Untuk mengatasi permasalahan pada algoritma evolusioner ini maka digunakan fase eksplorasi dan eksploitasi milik Diversity-guided Evolutionary Algorithm (DGEA) yang memanfaatkan ukuran diversitas populasi. Penelitian ini bertujuan untuk mendeteksi kelas penyakit menggunakan JST dengan algoritma pembelajaran GA-Diversitas (GAD) untuk menentukan kombinasi bobot dan bias optimal pada JST yang digunakan untuk mengklasifikasi kelas penyakit positif atau kelas penyakit negatif. Studi kasus yang digunakan sebagai uji coba adalah klasifikasi dataset penyakit kanker payudara yang diperoleh dari UCI Machine Learning. Penelitian ini menggunakan 3 skenario dan menunjukkan bahwa JST dengan algoritma pembelajaran GAD secara rata-rata menghasilkan akurasi tertinggi dibandingkan dengan GA dan backpropagation, yaitu 97,75 %. Keywords— Algoritma Genetika, Jaringan Syaraf Tiruan, Klasifikasi
Diversitas,
I. PENDAHULUAN Kesehatan menjadi hal yang penting dalam kehidupan manusia. Seiring perkembangan zaman, penyakit makin banyak dan beragam sehingga diperlukan sistem cerdas untuk mendeteksi penyakit secara otomatis. Pendeteksian penyakit dengan sistem cerdas diperlukan untuk otomatisasi deteksi penyakit misalnya membuat prediksi kelas penyakit positif atau negatif untuk kanker payudara (Saxena dkk, 2013). Deteksi kelas penyakit juga dapat dilakukan dengan teknologi soft computing. Dalam soft computing, proses prediksi dapat dilakukan dengan
sebelumnya melakukan proses pembelajaran dari dataset. Salah satu teknologi dalam soft computing adalah algoritma Jaringan Saraf Tiruan (JST). Jaringan saraf tiruan dapat dioptimalkan performanya dengan menggunakan Algoritma Genetika (GA) untuk optimasi nilai bobot pada JST (Saxena, 2013). JST memiliki keunggulan dengan adanya proses pembelajaran sedangkan GA merupakan algoritma evolusioner untuk permasalahan optimasi. Namun sebagai algoritma evolusi, GA memiliki kelemahan yaitu terjebak pada lokal optimum (Cutello dkk, 2014). Untuk mengatasi permasalahan pada GA, maka fase eksplorasi dan eksploitasi pada Diversity-guided Evolutionary Algorithm (DGEA) dapat dimanfaatkan. Dua fase ini dijalankan berdasarkan ukuran diversitas populasi. Sebelumnya telah dilakukan Hybrid DGEA dengan Algoritma Artificial Bee Colony (ABC) untuk mengatasi permasalahan konvergensi dini dan terjebak pada lokal optimum (Lee dan Cai, 2011). Dalam makalah ini diusulkan Hybrid Algoritma hybrid GA-Diversitas (GAD) permasalahan klasifikasi penyakit. GAD ini kemudian digunakan sebagai algoritma pembelajaran pada JST. Algoritma pembelajaran digunakan untuk menentukan kombinasi bobot dan bias optimal pada JST yang digunakan untuk mengklasifikasi kelas penyakit positif atau kelas penyakit negatif. Dengan menggunakan pendekatan metode ini diharapkan hasil diagnosa yang diperoleh dapat dijadikan sebagai alat bantu oleh ahli medis dalam mendiagnosis suatu penyakit. Penelitian ini bertujuan untuk mendeteksi kelas penyakit menggunakan JST dengan algoritma pembelajaran GAD. II. STUDI PUSTAKA A. Jaringan Syaraf Tiruan JST terinspirasi dari susunan sel syaraf (neuron) manusia. JST merupakan algoritma supervised learning yang memetakan data input terhadap data output atau targetnya. JST mampu memodelkan permasalahan non linier kompleks yang sulit dipecahkan dengan menggunakan persamaan matematis biasa. Struktur JST terdiri
Seminar Nasional Matematika dan Aplikasinya 2013
dari lapisan input, lapisan hidden, dan lapisan output. Masing-masing node antar lapisan dihubungkan dengan bobot dan dipengaruhi oleh bias. (Jin dan Shu, 2013). Terdapat banyak macam struktur JST. Salah satunya adalah JST single layer dimana terdapat satu lapisan tersembunyi yang terdiri dari beberapa neuron hidden. Contoh struktur JST single layer dapat dilihat pada Gambar 1. Input layer
Hidden layer
Output layer
Input Input
Output
Input w
Gambar 1. Struktur Neural Network Single Layer
Struktur tersebut menggambarkan JST single layer dengan lapisan input yang terdiri dari 3 neuron, lapisan tersembunyi yang terdiri dari 4 neuron, dan satu output. B. Algoritma Genetika GA ditemukan pertama kali oleh Holland pada tahun 1960. Algoritma ini terinspirasi dari fenomena yang terjadi pada sistem biologis makhluk hidup. (Obitko, 1998). Langkah pertama penyelesaian masalah adalah inisialisasi populasi kromosom. Inisialisasi populasi ini dilakukan secara random. Kemudian dilakukan perhitungan nilai fitness pada masing-masing kromosom pada populasi tersebut. Langkah kedua adalah melakukan seleksi kromosom berdasarkan evaluasi fitness.Semakin baik atau semakin tinggi nilai fitness suatu kromosom, semakin besar kemungkinan kromosom tersebut terpilih. Beberapa teknik seleksi yang bisa dipakai dalam seleksi adalah roulette wheel, turnamen, dan elitism. Inisialisasi
Langkah selanjutnya adalah melakukan operator genetika yaitu crossover dan mutasi pada kromosom yang terseleksi. Tahapan ini didasarkan pada probabilitas terjadinya crossover (Pc) dan probabilitas terjadinya mutasi (Pm). Hasil crossover dan mutasi adalah terbentuknya anakan. Langkah terakhir adalah pembentukan populasi baru dari induk dan anakan yang terbentuk. Proses evolusi akan terus berlangsung sampai kriteria penghentian tercapai (Gen dan Cheng, 1997). Prosedur GA dapat dilihat pada Gambar 2. C. Algoritma Diversitas DGEA merupakan algoritma yang digunakan untuk memperbaiki performa dari algoritma evolusi untuk mengetahui kondisi kekonvergenan (Ursem, 2002). Strategi ini digunakan untuk mengatasi populasi dengan nilai diversitas atau keberagaman data yang kecil sehingga cenderung menyebabkan terjadinya kovergensi yang terlalu cepat dan terjebak pada lokal optimu. Pengukuran diversitas data dilakukan untuk memilih fase eksplorasi atau eksploitasi dalam GA. Ukuran diversitas data diperoleh dengan menggunakan Persamaan 1. (1) dimana P menyatakan populasi data, N adalah dimensi permasalahan, |L| adalah panjang diagonal pada ruang pencarian dengan , adalah nilai ke-j dari individu ke-i,dan adalah nilai ratarata yang ke-j (Ursem, 2002). Jika dhigh merupakan suatu ambang batas dari ukuran diversitas, maka jika P > dhigh menunjukkan bahwa ukuran diversitas populasi tinggi sehingga dapat menyebabkan konvergensi yang lambat dan perlu dilakukan eksplorasi lebih lanjut. Namun jika P < dhigh menunjukkan bahwa kondisi diversitas populasi rendah sehingga dapat menyebabkan konvergensi dini dan perlu dilakukan fase eksploitasi (Ursem, 2002). Bagan prosedur pemilihan fase dapat dilihat pada Gambar 3. Hitung P dan dhigh
Evaluasi
P >dhigh
Seleksi
N
eksploitasi
Y Crossover
Mutasi
eksplorasi Gambar 3. Prosedur Pemilihan Fase
Populasi Baru Gambar 2. Prosedur Algoritma Genetika
Seminar Nasional Matematika dan Aplikasinya 2013
III. METODE A. Hybrid Algoritma Genetika – Diversitas Algoritma diversitas dilakukan setelah proses evolusi genetika selesai untuk satu kali generasi. Ukuran diversitas populasi N kromosom dapat ditentukan dengan Persamaan 1. Sedangkan batas diversitas dari populasi akan berkurang setiap waktu yang dinyatakan dengan Persamaan 2. (2) dimana C menyatakan iterasi saat ini, MNC menyatakan jumlah iterasi maksimum atau epoch dan nilai dari winitial adalah 0.5 dan nilai wfinal adalah 0. Bila nilai diversitas P lebih kecil dari nilai line (t) maka akan dilakukan fase eksplorasi dengan menggunakan Persamaan 3. Dimana dan adalah indeks random yang dipilih, dan merupakan nilai random antara [0,1]. (3) Sebaliknya, bila P lebih besar dari nilai line(t) maka akan dilakukan fase eksploitasi. Pada fase eksploitasi untuk menentukan posisi solusi baru menggunakan Persamaan 4. Sedangkan untuk mencari solusi baru yang lain digunakan Persamaan 5. Dimana , , k dan j adalah indeks yang dipilih secara random, adalah nilai random antara [-0.5, 0.5] dan nilai random antara [0,1]. ,
(4) (5)
B. GAD sebagai Algoritma Pembelajaran pada JST Langkah pertama adalah melakukan preprocessing data dan membagi data menjadi data latih dan data uji. Kemudian dilakukan normalisasi data sehingga data bernilai antara 0 dan 1. Selain itu menentukan parameter yang digunakan, antara lain adalah Pc, Pm, PopSize, jumlah neuron hiden, dan maxEpoh.
Gambar 4. Struktur Kromosom
Langkah selanjutnya adalah membangkitakan kromosom yang merupakan kombinasi bobot dan
bias. Struktur kromosom dapat dilihat pada Gambar 4. Pengkodean bobot dan bias yang digunakan adalah pengkodean matriks dimana kromosom i menyatakan solusi ke-i yang terdiri dari merupakan bobot dari layer input ke layer hidden, adalah bobot dari layer hidden ke layer output, adalah bias pada layer input dan merupakan bias pada layer hidden. Sebelumnya, Mirjalili dkk (2012) telah menjelaskan tentang fungsi aktifasi dan fungsi fitness yang digunakan untu pembelajaran dalan JST. Fungsi aktifasi yang digunakan di hidden layer sesuai dengan Persamaan 6. .
(6)
Sedangkan fungsi fitness yang digunakan adalah MSE yang sesuai dengan Persamaan 7. (7) IV. UJI COBA DAN ANALISIS A. Data Uji Coba Data yang digunakan dalam penelitian ini adalah dataset Breast Cancer yang diambil dari UCI Machine Learning Repository. Dataset tersebut terdiri dari 699 record, dengan 15 record mengandung missing value. Oleh karena itu perlu dilakukan preprocessing untuk menangani data dengan missing value tersebut. Preprocessing data dilakukan dengan cara menghapus 15 record dengan missing value sehingga dataset yang awalnya berjumlah 699 record tereduksi menjadi 684 record. Kelimabelas record itu masingmasing adalah 13 record dari kelas Benign (kelas 0), dan 2 record dari kelas Malignant (kelas 1). Pada akhirnya digunakan 684 record yang terdiri dari 445 record kelas Benign dan 239 record kelas Malignant. B. Skenario Uji Coba Uji coba dilakukan dengan 3 skenario. Skenario pertama, menjadikan dataset sebagai data latih sekaligus data uji. Skenario ini bertujuan untuk mengetahui kebaikan akurasi dari model yang ada. Skenario ini dilakukan sebanyak 20 replikasi. Skenario kedua adalah dengan mempertimbangkan running time untuk masingmasing metode. Skenario terakhir adalah dengan menggunakan metode 10-fold cross validation, yaitu membagi masing-masing dataset menjadi 10 fold yang sama. Kemudian kombinasi 9 fold yang berbeda akan digunakan sebagai data latih, sedangkan 1fold yang lain digunakan sebagai data uji. Skenario ini juga dilakukan sebanyak 20 replikasi.
Seminar Nasional Matematika dan Aplikasinya 2013
Parameter yang digunakan adalah Pc = 0.6, Pm = 0.1, PopSize = 10, jumlah neuron hiden = 2, dan maxEpoh = 50. Metode pembelajaran hybrid GAD akan dibandingkan dengan metode pembelajaran menggunakan GA dan backpropagation. Selanjutnya dari hasil yang diperoleh dilakukan uji statistik one-way ANOVA dan uji lanjutan Turkey untuk mengetahui pengaruh adanya algoritma diversitas untuk algoritma genetika.
1) Skenario 1: Pada skenario ini secara rata-rata akurasi model menggunakan metode GAD memiliki nilai paling tinggi yakni 97.745%. Sementara akurasi model menggunakan metode GA dan Backpropagation diperoleh nilai masingmasing sebesar 97.701% dan 97.222%. Grafik akurasi model masing masing metode dapat dilihat pada Gambar 5 dengan indeks 1 adalah GAD, 2 adalah GA, dan 3 adalah Backpropagation. Grafik Akurasi Model 97.74524
97.70132
97.5
97.222745
97
96.5 1
2
9E-10
3
Gambar 5. Grafik Akurasi Model dari 3 Metode
Selanjutnya dari hasil yang diperoleh dilakukan uji statistik one-way ANOVA diperoleh nilai pvalue 0.00 sehingga dilakukan uji lanjutan Turkey dengan nilai masing-masing p-value dapat dilihat pada Tabel 1.
7.5E-10 7E-10
7E-10 6E-10 1
2
3
Selanjutnya dari hasil yang diperoleh dilakukan uji statistik one-way ANOVA diperoleh nilai pvalue > alpha sehingga dapat disimpulkan bahwa walaupun secara rata-rata nilai running time Backpropagation paling cepat namun tidak signifikasn secara statistik. 3) Skenario 3: Pada skenario ini dilihat dua nilai akurasi yakni akurasi dari pembentukan model dari yakni proses pelatihan dan nilai akurasi dari penggunaan model yakni proses pengujian. secara rata-rata akurasi model menggunakan metode GAD memiliki nilai paling tinggi yakni 97.749% untuk pembelajaran dan 97.545% untuk pengujian. Sementara akurasi model menggunakan metode GA dan Backpropagation pada saat pembelajaran masing-masing bernilai 97.749% dan 96.991%, sedangkan pada saat pengujian masing-masing bernilai 97.274% dan 96.499%. Grafik akurasi hasil dari 10 Cross Validation dapat dilihat pada Gambar 7. Selanjutnya dari hasil yang diperoleh dilakukan uji statistik one-way ANOVA diperoleh nilai pvalue > alpha sehingga dapat disimpulkan bahwa walaupun secara rata-rata nilai akurasi dari 1- cross validation GAD memiliki akurasi paling tinggi namun tidak signifikan secara statistik.
Grafik Akurasi 10 Cross Validation
TABEL 1. PERBANDINGAN P-VALUE SKENARIO 1 Metode
8E-10
8E-10
Gambar 6. Grafik Running Time dari 3 Metode
C. Hasil dan Analisis Uji Coba
98
Grafik Run Time Model
98
p-value GAD
GA
BP
97.5
GAD
-
.846
.000
97
GA
.846
-
.000
96.5
BP
.000
.000
-
97.749085
97.749085 96.99071
97.545605
97.27439 96.499545
96
2) Skenario 2: Pada skenario ini secara ratarata running time metode GAD memiliki nilai paling tinggi yakni 8x1010. Sementara waktu yang dibutuhkan metode GA dan Backpropagation diperoleh nilai masing-masing sebesar 7.5x1010 dan 7x1010. Hal ini menunjukkan bahwa metode GAD membutuhkan waktu yang relatif lebih lama daripada metode yang lain dan Backpropagation membutuhkan waktu paling cepat. Grafik waktu yang dibutuhkan masing masing metode dapat dilihat pada Gambar 6.
95.5
1
2
3
Gambar 7. Grafik Akurasi dan Pengujian Model dari 3 Metode
V. KESIMPULAN Hasil pembelajaran untuk JST menggunakan algoritma GAD memberikan model dengan hasil akurasi yang lebih baik jika dibandingkan dengan GA dan Backpropagation yakni 97,75 %. Dengan pengujian menggunakan metode 10 cross
Seminar Nasional Matematika dan Aplikasinya 2013
validation, nilai akurasi model dan pengujian juga menunjukkan nilai paling tinggi yakni 97.749% untuk pembelajaran dan 97.545% untuk pengujian. Namun jika ditinjau dari running time yang dibutuhkan, secara rata-rata GAD cenderung memakan waktu lebih lama. Dari hasil yang telah didapatkan, dapat disimpulkan bahwa GAD mampu memberikan nilai akurasi yang lebih baik jika dibandingkan dengan GA. Namun, pengaruh dari adanya algoritma diversitas tidak terlihat signifikan untuk GA sebagai metode pembelajaran pada JST untuk masalah dengan data yang kecil atau berdimensi rendah. Penelitian selanjutnya diharapkan dapat memanfaatkan JST dengan pembelajaran GAD untuk kasus data yg lebih besar dengan dimensi yang lebih tinggi. DAFTAR PUSTAKA Cutello, dkk, 2014, Escaping Local Optima via Parallelization and Migration. Nature Inspired Cooperative Strategies for Optimization, Vol. 512, pp 141-152
Gen, M. Cheng, R. 1997, Genetic Algorithms and Engineering Design, Wiley, New York Jin, F., Shu, G., 2013, Back Propagation Neural Network Based on Artificial Bee Colony Algorithm, Strategic Technology, Seventh International Forum, pp. 1-4 Mirjalili, S., dkk, 2012, Training feedforward neural networks using hybrid particle swarm optimization and gravitational search algorithm. Applied Mathematics and Computation , Vol. 218, pp. 11125–11137 Lee, W. P., Cai, W. T., 2011, A novel artificial bee colony algorithm with diversity strategy. In Natural Computation (ICNC), Seventh International Conference, Vol. 3, pp. 1441-1444 Obitko, M. 1998, Genetic Algorithms, Czech Technical University, Prague., Czech Republic Saxena, dkk., 2013, A Survey on Neural Network Techniques for Classification of Breast Cancer Data. International Journal of Engineering And Advanced Technology, Vol. 2, pp. 234-237 Ursem, R., 2002, Diversity- guided evolutionary algorithms. Parallel Problem Solving from Nature—PPSN VII, pp. 462–471
