Genetic Algorithm to Optimize k-Nearest Neighbor Parameter for Benchmarked Medical Datasets Classification

Rizki Tri Prasetio

doi:10.15575/join.v5i2.656

Genetic Algorithm to Optimize k-Nearest Neighbor Parameter for Benchmarked Medical Datasets Classification

Rizki Tri Prasetio

Abstract

Computer assisted medical diagnosis is a major machine learning problem being researched recently. General classifiers learn from the data itself through training process, due to the inexperience of an expert in determining parameters. This research proposes a methodology based on machine learning paradigm. Integrates the search heuristic that is inspired by natural evolution called genetic algorithm with the simplest and the most used learning algorithm, k-nearest Neighbor. The genetic algorithm were used for feature selection and parameter optimization while k-nearest Neighbor were used as a classifier. The proposed method is experimented on five benchmarked medical datasets from University California Irvine Machine Learning Repository and compared with original k-NN and other feature selection algorithm i.e., forward selection, backward elimination and greedy feature selection. Experiment results show that the proposed method is able to achieve good performance with significant improvement with p value of t-Test is 0.0011.

Keywords

feature selection; parameter optimization; k-nearest neighbor; genetic algorithm

Full Text:

PDF

References

C. V. Subbulakhsmi and S. N. Deepa, "Medical Dataset Classification: A Machine Learning Paradigm Integrating Particle Swarm Optimization with Extreme Learning Machine Classifier," The Scientific World Journal, vol. 2015, pp. 1-12, 2015.

Y. Unal and E. Kocer, "Diagnosis of Pathology on the Vertebral Column with Backpropagation and Naive Bayes Classifier," Turkey, 2013.

R. T. Prasetio and E. Ripandi, "Optimasi Klasifikasi Jenis Hutan Menggunakan Deep Learning Berbasis Optimize Selection," Jurnal Informatika, pp. 100-106, 2019.

G. S. Babu and S. Suresh, "Meta-cognitive RBF network and its projection based learning algorithm for classification problems," Applied Soft Computing Journal, vol. 13, no. 1, pp. 654-666, 2013.

H. H. Inbarani, A. T. Azar and G. Jothi, "Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis," Computer Methods and Programs in Biomedicine, vol. 113, no. 1, pp. 175-185, 2014.

P.-C. Chang, J.-J. Lin and C.-H. Liu, "An attribute weight assignment and particle swarm optimization algorithm for medical database classifications," Computer Methods and Programs in Biomedicine, vol. 107, no. 3, pp. 382-392, 2012.

M. L. Raymer, W. F. Punch, E. D. Goodman, L. A. Kuhn and A. K. Jain, "Dimensionality reduction using genetic algorithms," IEEE Transactions on Evolutionary Computation, vol. 4, no. 2, pp. 164-171, 2000.

J. Yang and V. Honavar, "Feature Subset Selection Using a Genetic Algorithm," Feature Extraction, Construction and Selection, pp. 117-136, 1998.

S. Shah and A. Kusiak, "Cancer gene search with data-mining and genetic algorithms," Computers in Biology and Medicine, vol. 37, no. 2, pp. 251-261, 2007.

M. A. Mazurowski, P. A. Habas, J. M. Zurada, J. Y. Lo, J. A. Baker and G. D. Tourassi, "Training neural network classifiers for medical decision making: The effects of imbalanced datasets on classification performance," Neural Networks, vol. 21, no. 2, pp. 427-436, 2008.

M. Brameier and W. Banzhaf, "A comparison of linear genetic programming and neural networks in medical data mining," IEEE Transactions on Evolutionary Computation , vol. 5, no. 1, pp. 17-26, 2001.

F. Amato, A. Lopez, E. M. Pena-Mendez, P. Vanhara, A. Hampi and J. Havel, "Artificial neural networks in medical diagnosis," Journal of Applied Biomedicine, vol. 11, no. 2, pp. 47-58, 2013.

R. T. Prasetio and Pratiwi, "Penerapan Teknik Bagging pada Algoritma Klasifikasi untuk Mengatasi Ketidakseimbangan Kelas pada Dataset Medis," Informatika, vol. 2, no. 2, pp. 395-403, 2015.

N. Suguna and K. Thanushkodi, "An Improved k-Nearest Neigbor Classification Using Genetic Algorithm," IJCSI International Journal of Computer Science, vol. 7, no. 2, pp. 18-44, 2010.

M. A. Jabbar, B. L. Deekshatulu and P. Chandra, "Classification of Heart Disease Using K- Nearest Neighbor and Genetic Algorithm," Procedia Technology, vol. 10, pp. 85-94, 2013.

X. Wu and V. Kumar, The Top Ten Algorithms in Data Mining, Boca Raton: Taylor & Francis Group, LLC, 2009.

P. Harrington, Machine Learning in Action, New York: Manning Publication, 2012.

R. T. Prasetio, A. A. Rismayadi and I. F. Anshori, "Implementasi Algoritma Genetika pada k-nearest neighbours untuk Klasifikasi Kerusakan Tulang Belakang," Jurnal Informatika, pp. 186-194, 2018.

D. T. Larose, Discovering Knowledge in Data: An Introduction to Data Mining, New Jersey: John Wiley & Sons, Inc., 2005.

X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh and Q. Yang, "Top 10 Algorithms in Data Mining," Springer-Verlag, London, 2008.

F. Gorunescu, Data Mining: Concepts, Models, and Techniques, Verlag Berlin Heidelberg: Springer, 2011.

J. Han, M. Kamber and J. Pei, Data Mining Concepts and Techniques, San Fransisco: Morgan Kauffman, 2012.

R. T. Prasetio and S. Susanti, "Prediksi Harapan Hidup Pasien Kanker Paru Pasca Operasi Bedah Toraks Menggunakan Boosted k-Nearest Neighbor," JURNAL RESPONSIF: Riset Sains & Informatika, pp. 64-69, 2019.

K. K. Bharti and P. K. Singh, "A three-stage unsupervised dimension reduction method for text clustering," Journal of Computational Science, vol. 5, no. 2, pp. 156-169, 2014.

O. Maimon and L. Rokach, Data Mining and Knowledge Discovery Handbook, Second Edition ed., New York: Springer, 2010.

Z. Liu, T. Chai and J. Tang, "Multi-frequency signal modeling using empirical mode decomposition and PCA with application to mill load estimation," Neurocomputing, vol. 169, pp. 392-402, 2015.

T. Jirapech-Umpai and S. Aitken, "Feature selection and classification for microarray data analysis: evolutionary methods for identifying predictive genes," BMC Bioinformatics, vol. 6, p. 148, 2005.

S. Shilaskar and A. Ghatol, "Dimensionality Reduction Techniques for Improved Diagnosis of Heart Disease," International Journal of Computer Applications , vol. 61, no. 5, pp. 1-8, 2013.

A. Jain and D. Zongker, "Feature Selection: Evaluation, Application and Small Sample Performance," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 2, pp. 153-158, 1997.

I. H. Witten, E. Frank and M. A. Hall, Data Mining: Practical Machine Learning Tools and Technique, Third Edition ed., Amsterdam: Elsevier Inc., 2011.

R. T. Prasetio and D. Riana, "A Comparison of Classification Methods in Vertebral Column Disorder with the Application of Genetic Algorithm and Bagging," Bandung, 2015.

O. L. Mangasarian, W. N. Street and W. H. Wolberg, "Breast cancer diagnosis and prognosis via linear programming," Operations Research, vol. 43, no. 4, pp. 570-577, 1995.

B. Antal and A. Hajdu, "An ensemble-based system for automatic screening of diabetic retinopathy," Knowledge-Based Systems, vol. 60, pp. 20-27, 2014.

D. Ayres-de-campos, J. Bernardes, A. Garrido, J. Marques-de-Sa and L. Pereira-Leite, "SisPorto 2.0: A Program for Automated Analysis of Cardiotocograms," The Journal of Maternal-Fetal Medicine, vol. 9, pp. 311-318, 2000.

L. A. Kurgan, K. J. Cios, R. Tadeusiewicz, M. Ogiela and L. S. Goodenday, "Knowledge discovery approach to automated Cardiac SPECT Diagnosis," Artificial Intelligence in Medicine, vol. 23, pp. 149-169, 2001.

A. Nowe, Genetic Algorithms, Encyclopedia of Astrobiology ed., Berlin: Springer, 2014.

J. H. Holland, Adaption in Natural and Artificial Systems, Cambridge: MIT Press, 1975.

K. F. Man, K. S. Tang and S. Kwong, "Genetic Algorithms: Concepts and Applications," IEEE Transactions on Industrial Electronics, vol. 43, no. 5, pp. 519-534, 1996.

D. T. Larose, Data Mining Methods and Models, New Jersey: John Wiley & Sons, Inc., 2006.

I. Guyon and A. Elisseeff, "An Introduction to Variable and Feature Selection," Journal of Machine Learning Research, vol. 3, pp. 1157-1182, 2003.

S. Abe, "Modified Backward Feature Selection by Cross Validation," Bruges, 2005.

S. Derksen and H. J. Keselman, "Backward, Forward and Stepwise Automated Subset Selection Algorithms," British Journal of Mathematical and Statistical Psychology, vol. 45, pp. 265-282, 1992.

F. G. Blanchet, P. Legendre and D. Borcard, "Forward Selection of Explanatory Variables," Ecology, vol. 89, no. 9, pp. 2623-2632, 2008.

S. Abe, Support Vector Machine for Pattern Classification, Second Edition ed., New York: Springer London, 2010.

E. L. Dyer, A. C. Sankaranarayanan and R. G. Baraniuk, "Greedy Feature Selection for Subspace Clustering," Journal of Machine Learning Research, vol. 14, pp. 2487-2517, 2013.

H. Vafaie and I. F. Imam, "Feature Selection Method: Genetic Algorithms vs Greedy-like Search," Louisville, 1994.

A. K. Farahat, A. Ghodsi and M. S. Kamel, "Efficient Greedy Feature Selection for Unsupervised Learning," Knowledge Information System, vol. 35, pp. 285-310, 2013.

T. Setiyorini and R. S. Wahono, "Penerapan Metode Bagging untuk Mengurangi Data Noise pada Neural Network untuk Estimasi Kuat Tekan Beton," Journal of Intelligent Systems, vol. 1, no. 1, pp. 37-42, 2015.