The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification

A new emerging nature-inspired algorithm named Bacterial Foraging Optimisation Algorithm (BFOA) that mimics the foraging behaviour of E. coli bacteria has drawn lots of attention from other researchers due to its high convergence rate and global search capability compared to others. Technically, BFO...

Full description

Saved in:
Bibliographic Details
Main Author: Faizol, Bin Mohd Suria
Format: Thesis
Language:English
Published: 2020
Subjects:
Online Access:http://ir.unimas.my/id/eprint/30023/1/The%20Bacterial..ft.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-unimas-ir.30023
record_format uketd_dc
institution Universiti Malaysia Sarawak
collection UNIMAS Institutional Repository
language English
topic QA75 Electronic computers
Computer science
spellingShingle QA75 Electronic computers
Computer science
Faizol, Bin Mohd Suria
The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
description A new emerging nature-inspired algorithm named Bacterial Foraging Optimisation Algorithm (BFOA) that mimics the foraging behaviour of E. coli bacteria has drawn lots of attention from other researchers due to its high convergence rate and global search capability compared to others. Technically, BFOA has been applied as supplementary algorithm for optimizing weight, parameters for other classifier algorithms and selecting optimised features for other classifiers. However, none of the available works had proposed BFOA as a classification algorithm despite of its good performance. Thus, this study aims to adopt and modify the BFOA into Instance Selection (IS) classifier by manipulating its global search capability and high convergence rate for data classification problem. There are two modified instance-based classifiers of BFOA were developed in this study. Both classifiers are inspired based on Prototype Selection (PS) and Prototype Generation (PG) known as BFOA-S and BFOA-G respectively. BFOA-G statistically outperformed BFOA-S by achieving 80.73% in the average testing accuracy with 5.16% average storage requirement, and 3 times faster in term of time complexity against BFOA-S in the benchmark experiment using 42 datasets. In addition, BFOA-G also performed well against ten existing IS algorithms by obtaining 83.1% in the average accuracy with 95.51% reduction rate and ranked first in the comparison study. On the other hand, BFOA-S showed competitive performance in the comparison against ten existing IS algorithms by obtaining 96.25% in reduction rate and ranked third in the ranking. Therefore, we conclude that the proposed BFOA-G is the best algorithm in the study, and PG approach is recommended for further development of BFOA as an IS algorithm.
format Thesis
qualification_level Master's degree
author Faizol, Bin Mohd Suria
author_facet Faizol, Bin Mohd Suria
author_sort Faizol, Bin Mohd Suria
title The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
title_short The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
title_full The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
title_fullStr The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
title_full_unstemmed The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification
title_sort bacterial foraging optimisation algorithm using prototype selection and prototype generation for data classification
granting_institution Universiti Malaysia Sarawak (UNIMAS)
granting_department Faculty of Computer Science and Information Technology
publishDate 2020
url http://ir.unimas.my/id/eprint/30023/1/The%20Bacterial..ft.pdf
_version_ 1783728375045554176
spelling my-unimas-ir.300232023-03-14T07:15:13Z The Bacterial Foraging Optimisation Algorithm using Prototype Selection and Prototype Generation for Data Classification 2020-06-22 Faizol, Bin Mohd Suria QA75 Electronic computers. Computer science A new emerging nature-inspired algorithm named Bacterial Foraging Optimisation Algorithm (BFOA) that mimics the foraging behaviour of E. coli bacteria has drawn lots of attention from other researchers due to its high convergence rate and global search capability compared to others. Technically, BFOA has been applied as supplementary algorithm for optimizing weight, parameters for other classifier algorithms and selecting optimised features for other classifiers. However, none of the available works had proposed BFOA as a classification algorithm despite of its good performance. Thus, this study aims to adopt and modify the BFOA into Instance Selection (IS) classifier by manipulating its global search capability and high convergence rate for data classification problem. There are two modified instance-based classifiers of BFOA were developed in this study. Both classifiers are inspired based on Prototype Selection (PS) and Prototype Generation (PG) known as BFOA-S and BFOA-G respectively. BFOA-G statistically outperformed BFOA-S by achieving 80.73% in the average testing accuracy with 5.16% average storage requirement, and 3 times faster in term of time complexity against BFOA-S in the benchmark experiment using 42 datasets. In addition, BFOA-G also performed well against ten existing IS algorithms by obtaining 83.1% in the average accuracy with 95.51% reduction rate and ranked first in the comparison study. On the other hand, BFOA-S showed competitive performance in the comparison against ten existing IS algorithms by obtaining 96.25% in reduction rate and ranked third in the ranking. Therefore, we conclude that the proposed BFOA-G is the best algorithm in the study, and PG approach is recommended for further development of BFOA as an IS algorithm. Universiti Malaysia Sarawak, (UNIMAS) 2020-06 Thesis http://ir.unimas.my/id/eprint/30023/ http://ir.unimas.my/id/eprint/30023/1/The%20Bacterial..ft.pdf text en validuser masters Universiti Malaysia Sarawak (UNIMAS) Faculty of Computer Science and Information Technology RENCES Aha, D. W., Kibler, D., & Albert, M. K. (1991). Instance-based Learning Algorithms. Machine Learning, 6(1), 37-66. Ahmad, S. S. S. (2014, December). Feature and Instances Selection for Nearest Neighbor Classification via Cooperative PSO. In 2014 4th World Congress on Information and Communication Technologies, 45-50. AL-Hadi, I. A. A., Hashim, S. Z. M., & Shamsuddin, S. M. H. (2011). Bacterial Foraging Optimization Algorithm for Neural Network Learning Enhancement. In 2011 11th International Conference on Hybrid Intelligent Systems, 200-205. Bensujin, B., Vijila, C. K., Hemanth, J., & Hubert, C. (2016). Frequency Dependent Adaptive Chemotaxis in Bacterial Foraging Optimization for ST Segment Elevation Myocardial Infarction Prediction. Indian Journal of Science and Technology, 9(1), 1-9. Bezdek, J. C., & Kuncheva, L. I. (2001). Nearest Prototype Classifiers Design: An Experimental Study. International Journal of Intelligent Systems, 16(12), 1445-1473. Brighton, H., & Mellish, C. (2002). Advances in Instance Selection for Instance-Based Learning Algorithms. Data Mining and Knowledge Discovery, 6(2), 153-172. Cano, J., Herrera, F., & Lozano, M. (2005). A Study on the Combination of Evolutionary Algorithms and Stratified Strategies for Training Set Selection in Data Mining. Applied Soft Computings, 6(3), 323-332. Cano, J. R., Herrera, F., & Lozano, M. (2003). Using Evolutionary Algorithms as Instance Selection for Data Reduction in KDD : An Experimental Study. IEEE Transactions on Evolutionary Computation, 7(6), 561-575. 129 Cano, J. R., Herrera, F., & Lozano, M. (2005). Stratification for Scaling up Evolutionary Prototype Selection. Pattern Recognition Letters, 26(7), 953-963. Carter, J. H. (2000). The Immune System as a Model for Pattern Recognition and Classification. Journal of the American Medical Informatics Association, 7(1), 28-41. Cervantes, A., Galván, I., & Isasi, P. (2007). An adaptive Michigan Approach PSO for Nearest Prototype Classification. In International Work-Conference on the Interplay Between Natural and Artificial Computation, 287-296. Cervantes, A., Galvain, I., & Isasi, P. (2005). A Comparison between the Pittsburgh and Michigan Approaches for the Binary PSO Algorithm. 2005 IEEE Congress on Evolutionary Computation, 1, 290-297. Cervantes, A., Galván, I. M., & Isasi, P. (2009). AMPSO : A New Particle Swarm Method for Nearest Neighborhood Classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(5), 1082-1091. Chakrabarty, A., Choudhury, O., Sarkar, P., Paul, A., & Sarkar, D. (2012). Hyperspectral Image Classification Incorporating Bacterial Foraging-optimized Spectral Weighting, Artificial Intelligent Research, 1(1), 63-83. Chen, C. H., Su, M. T., Lin, C. J., & Lin, C. T. (2014). A Hybrid of Bacterial Foraging Optimization and Particle Swarm Optimization for Evolutionary Neural Fuzzy Classifier. International Journal of Fuzzy Systems, 16(3), 422-433. Cho, J. H., & Kim, D. H. (2011). Intelligent Feature Selection by Bacterial Foraging Algorithm and Information Theory. In International Conference on Advanced Communication and Networking, 238-244. 130 Chuang, L. Y., Tsai, S. W., & Yang, C. H. (2011). Catfish Binary Particle Swarm Optimization for Feature Selection. In International Conference on Machine Learning and Computing IPCSIT, 3, 40-44. Damodaram, R., & Phil, M. (2013). Bacterial Foraging Optimization for Fake Website Detection. International Journal of Computer Science & Applications, 1(11), 116-127. Darvishi, M., Javadi, H. H. S., Pedram, M. M., & Erfani, H. (2012). Using Regression in Bacterial Foraging Algorithm to Improve Robots Routing. Research Journal of Applied Sciences, Engineering and Technology, 4(20), 405-4054. Das, S., Biswas, A., Dasgupta, S., & Abraham, A. (2009). Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications. Foundations of Computational Intelligence, 3, 23-55. Decaestecker, C. (1997). Finding Prototypes for Nearest Neighbour Classification by Means of Gradient Descent and Deterministic Annealing. Pattern Recognition, 30(2), 281-288 Demsar, J. (2006). Statistical Comparisons of Classifiers over Multiple Data Sets. Journal of Machine Learning Research, 7, 1-30. Derrac, J., García, S., & Herrera, F. (2010). A Survey on Evolutionary Instance Selection and Generation. International Journal of Applied Metaheuristic Computing, 1(1), 60-92. Feng, H., Horng, J.-H., & Jou, S.-M. (2012). Algorithm Based Fuzzy-VQ Compression Systems. Journal of Information Hiding and Multimedia Signal Processing, 3(3), 227-239. 131 Figueredo, G., Ebecken, N., Augusto, D., & Barbosa, H. (2012). An Immune-Inspired Instance Selection Mechanism for Supervised Classification. Memetic Computing, 4(2), 135-147. Fister Jr, I., Yang, X.-S., Fister, I., Brest, J., & Fister, D. (2013). A Brief Review of Nature-Inspired Algorithms for Optimization. Electrotechnical Review, 80(3), 1-7. Frank, A., & Asuncion, A. (2011). UCI Machine Learning Repository Irvine [Data file]. Retrieved from http://archive.ics.uci.edu/ml/datasets.html Garcia-Pedrajas, N., Del Castillo, J. A. R., & Ortiz-Boyer, D. (2010). A Cooperative Coevolutionary Algorithm for Instance Selection for Instance-based Learning. Machine Learning, 78(3), 381-420. Garcia, S., Derrac, J., Cano, J. R., & Herrera, F. (2012). Prototype Selection for Nearest Neighbor Classification: Taxonomy and Empirical Study. IEEE Transactions on Pattern Analysis & Machine Intelligence, 34(3), 417-435. García, S., Cano, J. R., & Herrera, F. (2008). A Memetic Algorithm for Evolutionary Prototype Selection: A Scaling Up Approach. Pattern Recognition, 41(8), 2693-2709. Geva, S., & Sitte, J. (1991). Adaptive Nearest Neighbor Pattern Classification. IEEE Transactions on Neural Networks, 2(2), 318-322. Gil-Pita, R., & Yao, X. (2007). Using A Genetic Algorithm for Editing K-Nearest Neighbor Classifiers. In International Conference on Intelligent Data Engineering and Automated Learning, 1141-1150. Hamamoto, Y., Uchimura, S., & Tomita, S. (1997). A Bootstrap Technique for Nearest Neighbor Classifier Design. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(1), 73-79. 132 He, H., & Garcia, E. a. (2009). Learning from Imbalanced Data. IEEE Transactions on Knowledge and Data Engineering, 21(9), 1263-1284. Ho, S. Y., Liu, C. C., & Liu, S. (2002). Design of an Optimal Nearest Neighbor Classifier Using an Intelligent Genetic Algorithm. Pattern Recognition Letters, 23(13), 1495-1503. Hossin, M. H., Mahudin, F., Din, I. J., & Mat, A. R. (2017). Analysis of Nine Instance-Based Genetic Algorithm Classifiers Using Small Datasets. Journal of Telecommunication, Electronic and Computer Engineering, 9(3-11), 67-71. Hongwei, Z., & Liwei, T. (2015). Cooperative Approaches to Bacterial Foraging Algorithm for Clustering. International Journal of Database Theory and Application, 8(4), 81–90. Hu, W., & Tan, Y. (2015). Prototype Generation Using Multiobjective Particle Swarm Optimization for Nearest Neighbor Classification. IEEE Transactions on Cybernetics, 46(12), 2719-2731. Ishibuchi, H., Nakashima, T., & Murata, T. (1997). Comparison of the Michigan and Pittburgh Approaches to Design of fuzzy classification system. Electronics and Communications in Japan, 80(2), 379-387. Jakhar, R., Kaur, N., & Singh, R. (2011). Face Recognition Using Bacteria Foraging Optimization-Based Selected Features. International Journal of Advanced Computer Science and Applications, 1(3), 106-111. Kaur, R., & Kaur, B. (2014). Artificial Neural Network Learning Enhancement Using Bacterial Foraging Optimization Algorithm. International Journal of Computer Applications, 102(10), 27-33. 133 Kim, D. H., & Cho, J. H. (2005). Adaptive Tuning of PID Controller for Multivariable System Using Bacterial Foraging Based Optimization. In International Atlantic Web Intelligence Conference, 231-235. Kohonen, T. (1990). The Self-Organizing Map. Proceedings of the IEEE, 78(9): 1464–1480. Koplowitz, J., & Brown, T. A. (1981). On the Relation of Performance to Editing in Nearest Neighbor Rules. Pattern Recognition, 13(3), 251-255. Kora, P., & Kalva, S. R. (2015). Hybrid Bacterial Foraging and Particle Swarm Optimization for detecting Bundle Branch Block. Springer Plus, 4(1), 1-19. Kruatrachue, B., & Hongsamart, M. (2008). Prototype Selection based on Minimal Consistent Subset and Genetic Algorithms. In SICE Annual Conference, 682-686. Kumar, D. P. (2014). Ground Water Prediction Using Bacterial Foraging Optimization Technique. American Journal of Computing Research Repository, 2(3), 44-48. Kuncheva, L. I. (1995). Editing for the k-Nearest Neighbors Rule by a Genetic Algorithm. Pattern Recognition Letters, 16(8), 809-814. Kuncheva, L. I. (1997). Fitness functions in Editing k-NN Reference Set by Genetic Algorithms. Pattern Recognition, 30(6), 1041-1049. Kuncheva, L. I., & Bezdek, J. C. (1998). Nearest Prototype Classification: Clustering, Genetic Algorithms, or Random Search? IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 28(1), 160-164. Lei, X., Wu, S., Ge, L., & Zhang, A. (2011). Clustering PPI Data Based on Bacteria Foraging Optimization Algorithm. In 2011 IEEE International Conference on Bioinformatics and Biomedicine, 96-99. Li, J. (2014). Analysis and Improvement of the Bacterial Foraging Optimization Algorithm. Journal of Computing Science and Engineering, 8(1), 1-10. 134 Li, J., Manry, M. T., Yu, C., & Wilson, D. R. (2005). Prototype Classifier Design with Pruning. International Journal on Artificial Intelligence Tools, 14(1–2), 261–280. Liu, H., & Motoda, H. (2002). On Issues of Instance Selection. Data Mining and Knowledge Discovery, 6(2), 115-130. Lozano, M., Sotoca, J. M., Sánchez, J. S., Pla, F., Pekalska, E., & Duin, R. P. W. (2006). Experimental Study on Prototype Optimization Algorithms for Prototype-Based Classification in Vector Spaces. Pattern Recognition, 39(10), 1827-1838. Lv, X., Chen, H., Zhang, Q., Li, X., Huang, H., & Wang, G. (2018). An Improved Bacterial-Foraging Optimization-Based Machine Learning Framework for Predicting The Severity of Somatization Disorder. Algorithms, 11(2), 1-18. Miloud-Aouidate, A., & Baba-Ali, A. R. (2013). An Efficient Ant Colony Instance Selection Algorithm for KNN Classification. International Journal of Applied Metaheuristic Computing, 4(3), 47-64. Miloud-Aouidate, A., & Baba-Ali, A. R. (2012). A Hybrid KNN-Ant Colony Optimization Algorithm For Prototype Selection. In International Conference on Neural Information Processing, 307-314. Mitra, S., Pal, S. K., & Mitra, P. (2002). Data mining in Soft Computing Framework: A Survey. IEEE Transactions on Neural Networks, 13(1), 3-14. Nanni, L., & Lumini, A. (2009). Particle swarm optimization for prototype reduction. Neurocomputing, 72(4–6), 1092-1097. Nanni, L., & Lumini, A. (2011). Prototype Reduction Techniques: A Comparison Among Different Approaches. Expert Systems with Applications, 38(9), 11820-11828. 135 Olesen, J., Cordero H, J., & Zeng, Y. (2009). Auto-Clustering Using Particle Swarm Optimization and Bacterial Foraging. In International Workshop on Agents and Data Mining Interaction, 69-83. Pal, M., Bhattacharyya, S., Roy, S., Konar, A., Tibarewala, D. N., & Janarthanan, R. (2014). A Bacterial Foraging Optimization and Learning Automata Based Feature Selection for Motor Imagery EEG Classification. In 2014 International Conference on Signal Processing and Communications, 1-5. Parpinelli, R. S., Lopes, H. S., & Freitas, A. A. (2002). Data Mining with an Ant Colony Optimization Algorithm. IEEE Transactions on Evolutionary Computation, 6(4), 321-332. Passino, K. M. (2002). Biomimicry of Bacterial Foraging for Distributed Optimization and Control. IEEE Control Systems Magazine, 22(3), 52-67. Putra, I. M. B. P., Hartati, R. S., Putra, I. K. G. D., & Wirdiani, N. K. A. (2014). Optimized Back Propagation Learning in Neural Networks with Bacterial Foraging Optimization to Predict Forex Gold Index (XAUUSD). Applied Mathematical Sciences, 8(38), 1847-1854. Rani, B., Goel, A. K., & Kaur, R. (2016). A Modified Approach for Lung Cancer Detection Using Bacterial Forging Optimization Algorithm. International Journal of Scientific Research Engineering & Technology, 5(1), 39-42. Rani, D., & Mangat, V. (2013). An Efficient Technique for Disease Diagnosis Using Bacterial Foraging Optimization and Artificial Neural Network. In 2013 International Symposium on Computational and Business Intelligence, 100-104. 136 Rosales-Pérez, A., Escalante, H. J., Coello, C. A. C., Gonzalez, J. A., & Reyes-Garcia, C. A. (2014, July). An Evolutionary Multi-Objective Approach for Prototype Generation. In 2014 IEEE Congress on Evolutionary Computation, 1100-1107. Rosales-Pérez, A., Gonzalez, J. A., Coello, C. A. C., Reyes-Garcia, C. A., & Escalante, H. J. (2016). EMOPG+ FS: Evolutionary Multi-Objective Prototype Generation and Feature Selection. Intelligent Data Analysis, 20(1), 37-51. Al-Shalabi, L. (2011). Knowledge Discovery Process: Guide Lines for New Researchers. Journal of Artificial Intelligence, 4(1), 21-28. Shivakumar, B. L., & Amudha, T. (2012). A Hybrid Bacterial Foraging Algorithm For Solving Job Shop Scheduling Problems. Global Journal of Computer Science and Technology, 12(10), 1-11. Sindhu, V. (2016). An Efficient Technique to Cancer Classification Using Fast Improved Bacterial Foraging. International Journal of Recent Trends in Engineering & Research, 2(4), 436-441. Skalak, D. B. (1994). Prototype and Feature Selection by Sampling and Random Mutation Hill Climbing Algorithms. In Machine Learning Proceedings 1994, 293-301. Song, Q., Guo, X., & Li, H. (2016). Bacterial Foraging Optimization Based on LS-SVM for BTP Forecasting. International Journal of Hybrid Information Technology, 9(1), 387-396. Song, Q., & Wang, A.-M. (2013). A Hybrid Algorithm Based on LS-SVM and Bacterial Foraging Approach for Burning-Through-Points (BTP) Prediction in Sintering Process. Journal of Theoretical & Applied Information Technology, 49(1), 231-240. 137 Suguna, N., & Thanushkodi, K. (2010). An Improved K-Nearest Neighbor Classification Using Genetic Algorithm. International Journal of Computer Science Issues, 7(2), 18-21. Szabo, A., & de Castro, L. N. (2013). A Constructive Data Classification Version of the Particle Swarm Optimization Algorithm. Mathematical Problems in Engineering 2013, 1-13. Triguero, I., Derrac, J., Garcıa, S., & Herrera, F. (2011). Prototype Generation for Nearest Neighbor Classification: Survey of Methods. Technical Report, Department of Computer Science and Artificial Intelligence, University of Granada, Spain. Triguero, I., Derrac, J., García, S., & Herrera, F. (2012). A Taxonomy and Experimental Study on Prototype Generation for Nearest Neighbor Classification. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 42(1), 86-100. Triguero, I., García, S., & Herrera, F. (2011). Differential Evolution for Optimizing the Positioning of Prototypes in Nearest Neighbor Classification. Pattern Recognition, 44(4), 901-916. Tripathy, M., Mishra, S., Lai, L. L., & Zhang, Q. P. (2006). Transmission Loss Reduction Based On FACTS and Bacteria Foraging Algorithm. Parallel Problem Solving from Nature-PPSN IX, 222-231. Varghese, T., Kumari, R. S., Mathuranath, P. S., & Singh, N. A. (2012). Performance Evaluation of Bacterial Foraging Optimization Algorithm for the Early Diagnosis and Tracking of Alzheimer’s Disease. In International Conference on Swarm, Evolutionary, and Memetic Computing, 41-48. 138 Wan, M., Li, L., Xiao, J., Wang, C., & Yang, Y. (2012). Data Clustering Using Bacterial Foraging Optimization. Journal of Intelligent Information Systems, 38(2), 321–341. Wilson, D. R., & Martinez, T. R. (2000). Reduction Techniques for Instance-Based Learning Algorithms. Machine Learning, 38(3), 257-286. Wu, X., Kumar, V., Quinlan, J. R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., & Zhou, Z. H. (2008). Top 10 Algorithms in Data Mining. Knowledge and Information Systems, 14(1), 1-37. Xie, Q., Laszlo, C. A., & Ward, R. K. (1993). Vector Quantization Technique for Nonparametric Classifier Design. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(12), 1326-1330. Zhang, Y., & Wang, D. (2013). A Cost-Sensitive Ensemble Method for Class-Imbalanced Datasets. Abstract and Applied Analysis, 2013, 1-6. Zhang, Y., & Wu, L. (2012). Bacterial Foraging Optimization Used in Cluster Analysis. International Journal of Digital Content Technology and Its Applications, 6(22), 345-354.