Implementasi Algoritma Genetika pada k-nearest neighbours untuk Klasifikasi Kerusakan Tulang Belakang

Rizki Tri Prasetio, Ali Akbar Rismayadi, Iedam Fardian Anshori

Sari


Abstrak

Kerusakan tulang belakang dialami oleh sekitar dua pertiga orang dewasa serta termasuk ke dalam penyakit yang paling umum kedua setelah sakit kepala. Klasifikasi gangguan tulang belakang sulit dilakukan karena membutuhkan radiologist untuk menganalisa citra Magnetic Resonance Imaging (MRI). Penggunaan Computer Aided Diagnosis (CAD) System dapat membantu radiologist untuk mendeteksi kelainan pada tulang belakang dengan lebih optimal. Dataset vertebral column memiliki tiga kelas sebagai klasifikasi penyakit kerusakan tulang belakang yaitu, herniated disk, spondylolisthesis dan kelas normal yang diambil berdasarkan hasil ekstraksi citra MRI. Dataset akan diolah dalam lima eksperimen berdasarkan validasi dataset menggunakan split validation dengan pembagian data training dan data testing yang bervariasi. Pada penelitian ini diusulkan implementasi algoritma genetika pada algoritma k-nearest neighbours untuk meningkatkan akurasi dari klasifikasi gangguan tulang belakang. Algoritma genetika digunakan untuk fitur seleksi dan optimasi parameter algoritma k-nearest neighbours. Hasil penelitian menunjukan bahwa metode yang diusulkan menghasilkan peningkatan yang signifikan dalam klasifikasi kerusakan pada tulang belakang. Metode yang diusulkan menghasilkan rata-rata akurasi sebesar 93% dari lima eksperimen. Hasil ini lebih baik dari algoritma k-nearest neighbours yang menghasilkan rata-rata akurasi hanya sebesar 82.54%.

 

Kata kunci: algoritma genetika, k-nearest neighbours, kerusakan tulang belakang, vertebral

 

Abstract

Spinal disorder is experienced by about two-thirds of adults and is included in the second most common disease after headaches. Classification of spinal disorders is difficult because it requires a radiologist to analyze Magnetic Resonance Imaging (MRI) images. The use of Computer Aided Diagnosis (CAD) System can help radiologists to detect abnormalities in the spine more optimally. The vertebral column dataset has three classes as a classification of spinal disorders, namely, herniated disk, spondylolisthesis and normal classes taken based on MRI Image extraction. The dataset will be processed in five experiments based on dataset validation using split validation with various training data and testing data. In this study proposed the implementation of genetic algorithms in the k-nearest neighbors algorithm to improve the accuracy of the classification of spinal disorders. Genetic algorithms are used for algorithm feature selection and parameter optimization of k-nearest neighbors. The results showed that the proposed method produced a significant increase in the classification of spinal disorder. The proposed method produces an average accuracy of 93% from five experiments. This result is better than the k-nearest neighbors algorithm which produces an average accuracy of only 82.54%.

 

Keywords: genetic algorithm, k-nearest neighbours, spinal disorder, vertebral column.



Kata Kunci


algoritma genetika, k-nearest neighbours, kerusakan tulang belakang, vertebral

Teks Lengkap:

PDF

Referensi


Abdrabou, E. (2012). A Hybrid Intelligent Classifier for The Diagnosis of Pathology on the Vertebral Column. Bioinformatics Using Intelligent and Machine Learning, 297–310.

Abe, S. (2005a). Modified Backward Feature Selection by Cross Validation. In European Symposium on Artificial Neural Networks (pp. 163–168). Bruges: d-side publishers.

Abe, S. (2005b). Support Vector Machines for Pattern Classification (Advances in Pattern Recognition). Berlin, Heidelberg: Springer-Verlag.

Ansari, S., & Sajjad, F. (2013). Diagnosis of Vertebral Column Disorders Using Machine Learning Classifiers. 2013 International Conference on Information Science and Applications (ICISA), Suwon, 1–6. https://doi.org/10.1109/ICISA.2013.6579446

Bharti, K. K., & Singh, P. K. (2014). A three-stage unsupervised dimension reduction method for text clustering. Journal of Computational Science, 5(2), 156–169. https://doi.org/10.1016/j.jocs.2013.11.007

Blanchet, G., Legendre, P., & Borcard, D. (2008). Forward selection of spatial explanatory variables. Ecology, 89(9), 2623–2632. https://doi.org/10.1890/07-0986.1

Brant-Zawadzki, M. N., Dennis, S. C., Gade, G. F., & Weinstein, M. P. (2000). Low back pain. Radiology, 217(2), 321–330. https://doi.org/10.1102/1470-7330.2005.0028

Da Rocha Neto, A. R., Sousa, R., De A. Barreto, G., & Cardoso, J. S. (2011). Diagnostic of pathology on the vertebral column with embedded reject option. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6669 LNCS, 588–595. https://doi.org/10.1007/978-3-642-21257-4_73

Deepa, T. (2013). An Innovative Optimization Algorithm for Feature Selection – A Comparative study, 3(1), 20–24.

Derksen, S., & Keselman, H. J. (1992). Backward, forward and stepwise automated subset selection algorithms: Frequency of obtaining authentic and noise variables. British Journal of Mathematical and Statistical Psychology, 45(2), 265–282. https://doi.org/10.1111/j.2044-8317.1992.tb00992.x

Dyer, E. L., Sankaranarayanan, A. C., & Baraniuk, R. G. (2013). Greedy Feature Selection for Subspace Clustering. The Journal of Machine Learning Research, 14(1). https://doi.org/10.1109/TDEI.2009.5211872

Eyo, R. A. D., & Einstein, J. N. W. (2001). Low back pain. The Nwe England Journal of Medicine, 344(5), 363–370. https://doi.org/10.1016/j.ajo.2011.04.011

Farahat, A. K., Ghodsi, A., & Kamel, M. S. (2013). Efficient greedy feature selection for unsupervised learning. Knowledge and Information Systems, 35(2), 285–310. https://doi.org/10.1007/s10115-012-0538-1

Gorunescu, F. (2011). Intelligent systems reference library. Gorunescu, Ed.

Guyon, I., & Elisseeff, A. (2003). An Introduction to Variable and Feature Selection. Journal of Machine Learning Research (JMLR), 3(3), 1157–1182. https://doi.org/10.1016/j.aca.2011.07.027

Han, J., Pei, J., & Kamber, M. (2011). Data mining: concepts and techniques. Elsevier.

Harrington, P. (2012). Machine learning in action. Shelter Island, NY: Manning Publications Co.

Jain, A., & Zongker, D. (1997). Feature Selection: Evaluation, Application, and Small Sample Performance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(2), 153–158. https://doi.org/10.1109/34.574797

Jirapech-Umpai, T., & Aitken, S. (2005). Feature selection and classification for microarray data analysis: Evolutionary methods for identifying predictive genes. BMC Bioinformatics, 6, 1–11. https://doi.org/10.1186/1471-2105-6-148

Kataria, A., & Singh, M. D. (2013). A Review of Data Classification Using K-Nearest Neighbour Algorithm. International Journal of Emerging Technology and Advanced Engineering, 3(6), 354–360.

Larose, D. T., & Larose, C. D. (2014). Discovering knowledge in data: an introduction to data mining. John Wiley & Sons.

Liu, Z., Chai, T., Yu, W., & Tang, J. (2015). Multi-frequency signal modeling using empirical mode decomposition and PCA with application to mill load estimation. Neurocomputing, 169, 392–402. https://doi.org/10.1016/j.neucom.2014.08.087

Maimon, O., & Rokach, L. (2005). Data Mining and Knowledge Discovery Handbook. Berlin, Heidelberg: Springer-Verlag.

Prasetio, R. T., & Pratiwi, P. (2015). PENERAPAN TEKNIK BAGGING PADA ALGORITMA KLASIFIKASI UNTUK MENGATASI KETIDAKSEIMBANGAN KELAS DATASET MEDIS. Jurnal Informatika, 2(2), 395–403.

Prasetio, R. T., & Riana, D. (2015). A comparison of classification methods in vertebral column disorder with the application of genetic algorithm and bagging. In 2015 4th International Conference on Instrumentation, Communications, Information Technology, and Biomedical Engineering (ICICI-BME) (pp. 163–168). Bandung. https://doi.org/10.1109/ICICI-BME.2015.7401356

Raymer, M. L., Punch, W. F., Goodman, E. D., Kuhn, L. A., & Jain, A. K. (2000). Dimensionality Reduction Using Genetic Algorithms. IEEE Transactions on Control Systems Technology, 4(2), 164–171. https://doi.org/10.1109/TCST.2011.2171964

Reddy, S. K., & Kodali, S. R. (2012). Classification of Vertebral Column using Naïve Bayes Technique, 58(7), 38–42.

Setiyorini, T., & Wahono, R. S. (2014). Penerapan metode bagging untuk mengurangi data noise pada neural network untuk estimasi tuat tekan beton. Journal of Intelligent Systems, 1(1), 36–41.

Shilaskar, S., & Ghatol, A. (2013). Feature selection for medical diagnosis: Evaluation for cardiovascular diseases. Expert Systems with Applications, 40(10), 4146–4153. https://doi.org/10.1016/j.eswa.2013.01.032

Tiwari, D. (2014). Handling Class Imbalance Problem Using Feature Selection. International Journal of Advanced Research in Computer Science & Technology, 2(2), 516–520.

Unal, Y., & Kocer, H. E. (2013). Diagnosis of pathology on the vertebral column with backpropagation and Naïve Bayes classifier. Technological Advances in Electrical, Electronics and Computer Engineering (TAEECE), 2013 International Conference On, 276–279. https://doi.org/10.1109/TAEECE.2013.6557285

Vafaie, H., & Imam, I. F. (1994). Feature Selection Methods: Genetic Algorithms vs Greedy-like Search. Proceedings of the International Conference on Fuzzy and Intelligent Control Systems, 1(March). Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.9710&rep=rep1&type=pdf

Videman, T., Nummi, P., Battie, M. C., & Gill, K. (1994). Digital assessment of MRI for lumbar disc desiccation. A comparison of digital versus subjective assessments and digital intensity profiles versus discogram and macroanatomic findings. Spine, 19(2), 192–198.

Villar, P., Fernández, A., & Herrera, F. (2010). A genetic algorithm for feature selection and granularity learning in fuzzy rule-based classification systems for highly imbalanced data-sets. Communications in Computer and Information Science. https://doi.org/10.1007/978-3-642-14055-6_78

White, A. A. I., & Gordon, S. L. (1982). Synopsis: Workshop on Idiopathic Low-Back Pain. Spine, 7(2). Retrieved from https://journals.lww.com/spinejournal/Fulltext/1982/03000/Synopsis__Workshop_on_Idiopathic_Low_Back_Pain.9.aspx

Witten, I. H., Frank, E., Hall, M. A., & Pal, C. J. (2016). Data Mining:

Practical machine learning tools and techniques. Morgan Kaufmann.

Wu, X., Kumar, V., Ross, Q. J., Ghosh, J., Yang, Q., Motoda, H., …

Steinberg, D. (2008). Top 10 algorithms in data mining. Knowledge and Information Systems (Vol. 14). https://doi.org/10.1007/s10115-007-0114-2.




DOI: https://doi.org/10.31311/ji.v5i2.4123

##submission.license.cc.by4.footer##

 dipublikasikan oleh LPPM UBSI
Jl. Kamal Raya No. 18 Cengkareng, Jakarta Barat