IMPLEMENTASI ALGORITMA C4. 5 DAN K-MEANS PADA DIAGNOSIS PENYAKIT GINJAL KRONIS I Gede Aditya Mahardika Pratama. I Made Widiartha. Program Studi Ilmu Komputer. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Udayana. Badung. Bali. adityamahardikapratama17@gmail. , madewidiartha@unud. ABSTRACT The kidneys function to maintain the stability of the body by regulating the balance of electrolytes, body fluids and expenditure of metabolic products. Chronic kidney disease is a form of kidney disorder. This disease is a deadly disease, but it can be avoided with proper precautions. The prevalence of chronic kidney disease is increasing as a person ages. Classification technique is one technique that can be used in diagnosing chronic kidney disease. One of the machine learning algorithms that can be used for classification is the C4. 5 algorithm. The C4. 5 algorithm is one of the algorithms that can be used in the decision tree method . ecision tre. The C4. 5 algorithm can only use categorical data, so data of numerical type needs to be discretized. K-Means Clustering is one method that can be used in data Elbow method is used in determining the optimal number of k on K-Means by comparing the SSE value of each number of k. System testing was carried out using the confusion matrix and the values of accuracy, recall and precision were 97. 92%, 94. 44% and 100%. Keywords : Chronic Kidney Disease. Classification. C4. K-means. Discretization of Data. Elbow Method. ABSTRAK Ginjal berfungsi untuk mempertahankan stabilitas tubuh dengan mengatur keseimbangan elektrolit, cairan tubuh dan pengeluaran hasil metabolisme. Penyakit ginjal kronis adalah salah satu bentuk gangguan pada ginjal. Penyakit ini merupakan penyakit yang mematikan, namun hal ini dapat dihindari dengan tindakan pencegahan yang tepat. Prevalensi penyakit ginjal kronis menjadi kian meningkat, seiring dengan bertambahnya umur seseorang. Teknik klasifikasi merupakan salah satu teknik yang dapat digunakan dalam mendiagnosis penyakit ginjal kronis. Salah satu algoritma machine learning yang dapat digunakan untuk klasifikasi adalah algoritma C4. Algoritma C4. 5 adalah salah satu algoritma yang dapat digunakan dalam metode decision tree . ohon keputusa. Algoritma C4. 5 hanya dapat menggunakan data kategorikal, sehingga data yang bertipe numerikal perlu dilakukan diskritisasi K-Means Clustering merupakan salah satu metode yang dapat digunakan dalam diskritisasi data. Metode elbow digunakan dalam penentuan jumlah k optimal pada K-Means dengan membandingkan nilai SSE masing-masing jumlah k. Pengujian sistem dilakukan dengan menggunakan confusion matrix dan didapatkan nilai accuracy, recall dan precision yaitu 97. 92%, 94. 44% dan 100%. Kata Kunci : Penyakit Ginjal Kronis. Klasifikasi. C4. K-Means. Diskritisasi Data. Metode Elbow. PENDAHULUAN Ginjal merupakan organ tubuh yang berfungsi mempertahankan stabilitas tubuh dengan mengatur keseimbangan elektrolit, cairan tubuh dan pengeluaran hasil metabolisme (Amalia, 2. Ginjal memilki fungsi yang sangat penting bagi kesehatan tubuh, sehingga akan sangat riskan apabila mengalami gangguan pada ginjal. Gangguan tersebut dapat dideteksi dengan melihat adanya kelainan pada darah, urin atau melalui prosedur biopsi ginjal (Kurnianto, et al. , 2. Penyakit ginjal kronis atau Chronic Kidney Disease (CKD) merupakan salah satu bentuk gangguan pada ginjal. Penyakit ini dapat mengakibatkan ketidakmampuan ginjal untuk melakukan fungsinya dengan baik yang disebabkan oleh penurunan kinerja organ ginjal (Kurnianto, et , 2. Menurut Kementerian Kesehatan RI pada tahun 2013, terdapat sebanyak 499. penduduk atau 2 per 1000 penduduk di Indonesia mengalami penyakit ginjal kronis. 414 Jurnal Teknologi Informasi dan Komputer. Volume 7. Nomor 4. Oktober 2021 Prevalensi penyakit ginjal kronis menjadi kian meningkat, seiring dengan bertambahnya umur seseorang (Yulianti, et al. , 2. Teknik klasifikasi merupakan salah satu teknik yang dapat digunakan dalam Klasifikasi merupakan salah satu teknik dari data mining. Dimana data mining merupakan suatu cara yang bertujuan dalam penemuan pola dari data yang dimanfaatkan untuk menyelesaikan suatu masalah melalui berbagai aturan proses (Handayani, 2. Definisi dari klasifikasi adalah pengelompokan yang didasarkan pada data-data yang ada (Fadilla, et , 2. Salah satu algoritma machine learning yang dapat digunakan untuk klasifikasi adalah algoritma C4. Algoritma C4. 5 adalah salah satu algoritma yang dapat digunakan dalam metode decision tree . ohon keputusa. Penelitian terdahulu tentang klasifikasi telah dilakukan dengan membandingkan algoritma C4. 5 dengan Nayve Bayes untuk memprediksi penyakit diabetes. Penelitian ini menunjukan algoritma C4. 5 lebih unggul dengan akurasi sebesar 82,74% (Pujianto, et al. , 2. Kemudian penelitian lainnya komparasi algoritma C4. Nayve Bayes, k-NN. Log-R, dan Deep learning dalam prediksi penyakit liver. Dari perbandingan kelima algoritma. Decision Tree (C4. merupakan algoritma dengan hasil paling baik, dengan tingkat akurasi 2,56% dan AUC 0,594 (Fahdia. Dalam pengklasifikasian dengan C4. diperlukan diskritisasi dari suatu kumpulan Teknik diskritisasi merupakan teknik yang mengkonversi bilangan numerikal menjadi bilangan kategorikal berdasarkan label interval atau label konseptual. Hal ini dilakukan dikarenakan C4. 5 hanya mampu menggunakan data kategorikal dalam proses pelatihan dan pengujian data (Rochman, et al. , 2. Salah satu metode diskritisasi yang dapat digunakan adalah K-Means (Pradana, et al. , 2. Berdasarkan uraian permasalahan tersebut, maka penelitian ini berfokus untuk mengimplementasikan algoritma C4. 5 dan diskritisasi dengan algoritma K-Means Clustering pada diagnosis penyakit ginjal TINJAUAN PUSTAKA K-Means K-Means adalah salah satu algoritma pengklasteran yang cukup sederhana untuk mempartisi data ke dalam beberapa klaster. Algoritma diimplementasikan dan dijalakan, relatif cepat, mudah disesuaikan dan banyak digunakan. Namun kelemahan dari algoritma ini yaitu pada inisialisasi cluster yang sangat sensitif. Berikut urutan proses algoritma K-Means (Rahman, et , 2. Tentukan jumlah k . yang akan Bangkitkan titik pusat . setiap cluster secara acak. Hitung jarak setiap centroid terhadap masing-masing data dengan menggunakan perhitungan jarak Euclidean Distance dengan persamaan sebagai berikut : cu2 , ycu1 ) = ocycuycn=1. cu2 Oe ycu1 )2 . Keterangan: 2, x. : dimensi data . arak dat. ycu1 : centroid ycu2 : posisi objek data Kelompokkan data dengan mencari jarak terdekat antara centroid dengan data. Tentukan nilai centroid yang baru dengan mencari rata-rata dari setiap cluster yang bersesuaian menggunakan rumus berikut : yayco = ycuyco Oc yccycn Keterangan: nk : jumlah data dalam cluster k di : jumlah dari nilai jarak yang masuk dalam masing-masing cluster Lakukan perulangan dari langkah c sampai e hingga anggota tiap cluster tidak ada yang berubah. Dalam menentukan jumlah k optimal dapat menggunakan metode Elbow. Dalam menentukan jumlah cluster yang tepat, metode elbow akan mencari suatu titik yang membentuk siku dengan membandingkan hasil persentase berdasarkan jumlah setiap cluster. Ketika nilai suatu cluster dengan nilai cluster selanjutnya mengalami penurunan paling besar Pratama. Widiartha. Implementasi Algoritma C. 45 Dan K-Means Pada DiagnosisA415 atau menghasilkan sudut pada grafik maka jumlah nilai cluster tersebut yang optimal. Perbandingan didapatkan dengan menghitung Sum of Square Error (SSE) dari setiap nilai Nilai SSE akan semakin kecil ketika nilai cluster semakin besar. Perhitungan SSE menggunakan persamaan berikut (Dewi & Pramita, 2. ycIycIya = Ocya ya=1 Ocycuycn . cuycn Oe ycayco | Keterangan : K = cluster ke-c xi = jarak data ke-i ck = centroid ke-i Algoritma C4. Dalam membangun sebuah pohon keputusan, salah satunya dapat menggunakan algoritma C4. C4. 5 telah diterapkan dalam kasus pada dunia nyata terutama pembuatan keputusan dalam hal medis, karena dapat menghasilkan akurasi klasifikasi yang baik dan dapat direpresentasikan secara sederhana. Kriteria splitting pada algoritma C4. menggunakan gain ratio, pemilihan atribut pertama dipilih berdasarkan atribut yang memiliki informasi penting yang dikomputasi pada training set, kemudian menyeleksi atribut tersebut dan seterusnya (Pradana, et al. , 2. Ada beberapa tahapan dalam membuat sebuah decision tree dengan algoritma C4. 5 yaitu (Yulianti, et al. , 2. n : jumlah partisi S Gain Ratio Gain ratio adalah modifikasi dari information gain yang bertujuan untuk mengurangi bias atribut yang pada algoritma C4. 5, dengan persamaan sebagai berikut: yaycaycnycu ycIycaycycnycu . = . Keterangan: : Atribut Gain. : Nilai gain pada atribut a Split. : Nilai split pada atribut a Split Info Dalam pemilihan akar . terdapat perhitungan split info terlebih dahulu sebelum mencari nilai gain ratio. Perhitungan split info menggunakan persamaan berikut: ycIycyycoycnyc yaycuyceycu . cI, y. = Oe Ocycuycn=1 ycn ycoycuyci2 ycn ycI ycI Keterangan: S : Himpunan kasus A : Atribut Si : Jumalah sampel untuk atribut i METODEOLOGI PENELITIAN Model Yang Diusulkan Information Gain Information Gain dihitung dengan menggunakan persamaan berikut: cIyc. cI, y. = yaycuycycycuycyyc . cI) Oe Ocycuycn=1 O . cI| yaycuycycycuycyyc . cIyc. Keterangan: : himpunan kasus : atribut |S. : jumlah kasus pada partisi ke-i |S| : jumlah kasus dalam S : jumlah partisi atribut A . Entropy Dalam menentukan infomation gain diperlukan nilai entropy dengan menggunakan persamaan berikut: cI) = Ocycuycn=1 Oe ycyycn O log 2 ycyycn Keterangan: S : himpunan kasus Pi : proporsi dari Si terhadap S Gambar 1. Flowchart Model yang Diusulkan Data sekunder penyakit ginjal kronis yang diambil dari UCI Machine Learning akan melewati tahapan preprocessing data terlebih Terdapat beberapa tahapan dalam preprocessing data seperti data cleaning yang digunakan untuk membersihkan data dari missing value, transformasi data untuk mengubah data masih bersifat nominal menjadi numerik serta proses normalisasi data agar rentang data disemua atribut menjadi sama. Selanjutnya dilakukan proses diskritisasi data menggunakan K-Means pada data bertipe numerik . seperti Usia. Blood 416 Jurnal Teknologi Informasi dan Komputer. Volume 7. Nomor 4. Oktober 2021 Pressure. Blood Glucose Random. Blood Urea. Serum Creatinine. Sodium. Potassium. Haemoglobin. Packed Cell Volume. White Blood Cell Count, dan Red Blood Cell Count. Setelah data diskritisasi akan dilakukan pembagain data training dan testing lalu dilanjutkan dengan menggunakan algoritma C4. Dan yang terakhir akan dilakukan perhitungan akurasi. Pengumpulan Data Pada penelitian ini menggunakan data sekunder yaitu dataset Chronic Kidney Disease (CKD) yang didapatkan dari UCI Machine Learning Repository. Dataset ini memiliki 400 sampel data dengan pembagian jumlah data untuk setiap kelas yaitu CKD sebanyak 250 data dan NOTCKD sebanyak 150 data. Dataset ini memilki 25 atribut dimana 11 atribut bertipe numerikal dan 14 atribut bertipe kategorikal. Tabel 1 menunjukan deskripsi dari dataset Chronic kidney disease. Tabel 1. Deskripsi atribut Fitur Age Rbc Pcc Bgr Sod Pot Hemo Pcv Htn Cad Appet Ane Class Deskripsi Usia Blood Pressure Specific Gravity Albumin Sugar Red Blood Cells Pus Cell Pus Cell Clumps Bacteria Blood Glucose Random Blood Urea Serum Creatinine Sodium Potassium Haemoglobin Packed Cell Volume White Blood Cell Count Red Blood Cell Count Hypertension Diabetes Mellitus Coronary Artery Disease Appetite Pedal Edema Anemia Class Domain 2 Ae 90 50 Ae 180 1,005 Ae 1,025 0Ae5 0Ae5 Normal/Abnormal Normal/Abnormal Present/NotPresent Present/NotPresent 22 Ae 490 1,5 Ae 391 0,4 Ae 76 4,5 Ae 163 2,5 Ae 47 3,1 Ae 17,8 9 Ae 54 2200 Ae 26400 2,1 Ae 8 Yes/No Yes/No Yes/No Good/Poor Yes/No Yes/No Ckd/Nockd Pengolahan Data Awal Sebelum data diproses akan dilakukan pengolahan data awal atau preprocessing data dimulai dari data cleaning, transformasi data dan tahapan diskritisasi data dengan K-Means. Data Cleaning Data cleaning dilakukan untuk menghapus missing value pada dataset. Pada dataset Chronic Kidney Disease, terdapat 242 data yang mengandung missing value dari 400 data yang ada. Penanganan terhadap missing value pada dataset dilakukan dengan menghapus data-data yang mengandung missing value. Sehingga didapatkan total data yang tidak mengandung missing value sebanyak 158 data dengan pembagian jumlah data untuk setiap kelasnya yaitu CKD sebanyak 43 data dan NOTCKD sebanyak 115 data. Tranformasi Data Tranformasi dilakukan dengan mengubah data yang bertipe nominal menjadi numerik. Data yang diubah yatitu atribut specific gravity, red blood cells, pus cell, pus cell clumps, bacteria, hypertension, diabetes mellitus, coronary artery disease, appetite, pedal edema dan anemia. Setelah data yang bertipe nominal diubah menjadi numerik, dilanjutkan dengan proses normalisasi data. Pada dataset Chronic kidney disease, rentang nilai pada setiap atribut masih belum sama. Sehingga diperlukan normalisasi agar rentang nilai atau domain tiap atribut menjadi sama dengan rentang nilai . dengan menggunakan persamaan Min-Max Normalization dengan rumus sebagai berikut. ycUOemin. ycUycuyceyc = max. Oemin. Evaluasi Tahap evaluasi sistem dilakukan dengan menggunakan confusion matrix. Perhitungan akan dilakukan dengan membagi data menjadi data training dan data testing dengan perbandingan 70:30. Lalu akan dilanjutkan dengan pengukuran evaluasi dengan confusion matrix. Accuracy merupakan ketepatan dari jumlah data yang diprediksi secara benar dengan menggunakan persamaan . ycNycE ycNycA yaycaycaycycycaycayc = ycNycE ycNycA yaycE yaycA Precision (P) merupakan ketepatan dari kasus yang positif yang diprediksi secara benar dengan menggunakan persamaan . ycNycE ycEycyceycaycnycycnycuycu = ycNycE yaycE Pratama. Widiartha. Implementasi Algoritma C. 45 Dan K-Means Pada DiagnosisA417 Recall (R) merupakan ketepatan dari kasus yang positif yang diidentifikasi secara benar dengan menggunakan persamaan . ycNycE ycIyceycaycaycoyco = ycNycE yaycA IMPLEMENTASI SISTEM Proses K-Means Diskritisasi menggunakan K-Means pada atribut-atribut yang memilki data kontinu. Dimana diskritisasi akan dilakukan pada setiap atribut yang artinya proses K-Means akan dilakukan pada satu Alur dari diskritiasasi dengan menggunakan K-Means dapat dilihat pada nilai centroid sebelumnya. Jika nilainya berbeda maka lakukan perulangan, jika tidak perulangan berhenti. Hasil dari proses tersebut akan menghasilkan data-data yang sudah Dari hasil klaster tersebut akan dibentuk rentang nilai di setiap klasternya dan dilanjutkan dengan mentransformasi data-data kontinu berdasarkan rentang tiap klaster yang Sebagai contoh, akan dilakukan proses diskritisasi pada atribut age. Atribut age memilki data kontinu dengan rentang nilai dari 6 sampai 83 setelah dilakukan preprocesing Selanjutnya data-data dari atribut tersebut akan masuk ke tahapan K-Means dengan nilai k = 3. Sehingga didapatkan hasil klasterisasi yang dapat dilihat pada tabel 2. Tabel 2. Hasil Klasterisasi Klaster Klaster Klaster Klaster Gambar 2. Flowchart Diskritisasi dengan KMeans Langkah pertama dalam K-Means yaitu menentukan jumlah k atau klaster. Dimana jumlah klasiter ini nantinya akan menjadi jumlah instance suatu atribut yang akan digunakan dalam perhitungan C4. Selanjutnya menentukan k-centroid atau titik pusat klaster dengan mengambil data dari dataset secara acak lalu menghitung jarak setiap masing-masing menggunakan rumus Euclidean Distance dengan persamaan . Mengelompokan setiap data ke masing-masing klaster denga mencari jarak terdekat antara centroid dengan data dan menentukan nilai centroid baru berdasarkan nilai rata-rata semua data pada masing-masing klaster dengan menggunakan persamaan . Hal yang sama akan dilakukan ketika terdapat data yang berpindah klaster dengan membandingkan nilai centroid baru dengan Data 6, 12, 15, 17, 20, 21, , 34, 35, 35, 36 37, 37, 38, 38, 39, 39, , 52, 52, 52, 53 55, 55, 55, 56, 56, 58, , 75, 79, 80, 83 Rentang 6 Ou data O 36 37 Ou data O 53 55 Ou data O 83 Dari hasil klasterisasi pada tabel 2, penentuan rentang nilai tiap klaster dilakukan dengan memilih nilai terbesar dan terkecil dari data pada masing-masing klaster. Selanjutnya akan dilakukan transformasi data pada atribut age berdasarkan rentang-rentang yang sudah didapatkan pada tabel 2. Sehingga pada atribut age kini memliki 3 buah instance yaitu 1, 2, dan Untuk menentukan jumlah k yang optimal dari setiap atribut, akan dilakukan perhitungan dengan metode elbow. Metode ini melakukan perbandingan berdasarkan nilai Sum of Square Error (SSE) dari masing-masing persamaan . Ketika nilai suatu cluster dengan nilai cluster selanjutnya mengalami penurunan paling besar atau menghasilkan sudut pada grafik maka jumlah nilai cluster tersebut akan digunakan dalam proses Perhitungan nilai SSE akan dilakukan pada jumlah klaster dari 2 sampai 10. Sebagai contoh, tabel 3 dan gambar 3 akan memperlihatkan nilai SSE beserta selisihnya pada atribut age. 418 Jurnal Teknologi Informasi dan Komputer. Volume 7. Nomor 4. Oktober 2021 Tabel 3. Hasil Perhitungan SSE Jumlah k SSE Selisih Pcv 9-26, 28-37, 39-46, 47-54 3800-8200, 8300-12800, 1-4, 4. 3, 5. Tabel 4 memperlihatkan hasil diskritisasi dari setiap atribut, dimana jumlah k optimal pada atribut Usia. Blood Pressure. Blood Glucose Random. Blood Urea. Serum Creatinine. Sodium. Potassium. Haemoglobin. Packed Cell Volume. White Blood Cell Count, dan Red Blood Cell Count dengan masingmasing nilainya yaitu 3, 3, 6, 4, 3, 3, 3, 3, 4, 3. Proses C4. Setelah selanjutnya adalah proses klasifikasi dengan algoritma C4. 5 untuk membentuk pohon keputusan berdasarkan data training yang digunakan untuk memprediksi kelas dari data Adapun tahapan-tahapan klasifikasi menggunakan algoritma C4. 5 yang dijelaskan pada gambar 4. Gambar 3. Grafik Hasil Perhitungan SSE Berdasarkan hasil perhitungan pada tabel 3 dan gambar 3, bahwa selisih terbesar didapatkan pada jumlah k adalah 3 dengan selisih sebesar 1. Sehingga pada atribut age akan dilakukan proses diskritisasi pada jumlah k = 3. Perhitungan yang sama dilakukan pada seluruh atribut yang memiliki data . Tabel memperlihatkan nilai k optimal beserta rentang dari setiap klasternya pada seluruh atribut yang memiliki data kontinu. Tabel 4. Hasil Diskritisasi Fitur Age Bgr Sod Pot Hemo Rentang 6-36, 37-53, 55-83 50-60, 70-70, 80-110 70-87, 88-106, 107-125, 127176, 210-303, 380-490 10-33, 34-73, 82-158, 309163 7, 3. 5, 9. 111-125, 130-141, 142-150 2, 4. 6, 47-47 5, 12-15. 2, 15. Gambar 4. Flowchart Algoritma C4. Langkah pertama yaitu menentukan data yang akan digunakan dalam proses pembentukan pohon keputusan. Selanjutnya hitung gain ratio dari setiap atribut. Dalam menentukan gain ratio, tentukan lebih dahulu nilai entropy total dan entropy setiap nilai atribut dengan menggunakan persamaan . Dilanjutkan dengan perhitungan information gain dari setiap atribut dengan persamaan . Lalu lakukan perhitungan split info dengan persamaan . dan gain ratio dengan persamaan . pada tiap atribut. Selanjutnya Pratama. Widiartha. Implementasi Algoritma C. 45 Dan K-Means Pada DiagnosisA419 tentukan root node atau node yang terletak pada bagian paling atas dari pohon keputusan dengan cara mencari atribut yang mempunyai nilai gain ratio tertinggi. Kemudian bangun rule berdasarkan atribut yang terpilih tersebut. Langkah selanjutnya dilakukan kembali perhitungan gain ratio pada semua atribut kecuali atribut yang sudah terpilih atau atribut yang sudah menjadi node pada perulangan Untuk langkah perhitungan nilai gain ratio sama seperti langkah 2, hanya saja data yang digunakan sudah terseleksi berdasarkan rule yang sudah dibangun Lalu tentukan nilai gain ratio tertinggi untuk dijadikan internal node atau node dari suatu percabangan. Kemudian bangun rule berdasarkan atribut yang terpilih Jika atribut dari internal node belum signifikan menemukan kelas prediksi atau menghasilkan nilai ambigu, maka lakukan kembali perhitungan gain ratio dan penentuan internal node sampai rule yang dibangun memenuhi kriteria untuk menemukan kelas prediksi yang signifikan. Jika atribut sudah memenuhi kriteria maka perulangan berhenti dan pohon keputusan telah terbentuk. Pengujian Sistem Pengujian sistem dilakukan membagi data menjadi data training dan data testing dengan perbandingan 70:30. Dari 158 data yang digunakan dari hasil preprocessing, jumlah data training yang digunakan yaitu 110 data dan data testing 48 data. Pengujian sistem dilakukan dengan menggunakan confusion matrix dengan menghitung nilai accuracy, recall dan precision. Hasil pengujian dari sistem yang dibangun dapat dilihat pada tabel Tabel 5. Akurasi Sistem Accuracy Recall Precision SIMPULAN Peneltian ini membangun sistem untuk mendiagnosis penyakit ginjal kronis dengan mengunakan algoritma C4. 5 dan K-Means Clustering sebagai diskritisasi data. Diskritisasi dilakukan pada atribut yang memilki data numerik . Dalam penentuan k optimal pada K-Means digunakan metode elbow dengan membandingkan nilai SSE dari setiap jumlah k dengan nilai yaitu 2 sampai 10. Sehingga didapatkan jumlah k optimal pada atribut Usia. Blood Pressure. Blood Glucose Random. Blood Urea. Serum Creatinine. Sodium. Potassium. Haemoglobin. Packed Cell Volume. White Blood Cell Count, dan Red Blood Cell Count dengan masing-masing nilainya adalah 3, 3, 6, 4, 3, 3, 3, 3, 4, 3, 3. Pengujian menggunakan confusion matrix dan didapatkan nilai accuracy, recall dan precision yaitu 92%, 94. 44% dan 100%. DAFTAR PUSTAKA