Improved Firefly Algorithm with Variable Neighborhood Search for Data Clustering
Main Article Content
Abstract
Among the metaheuristic algorithms, population-based algorithms are an explorative search algorithm superior to the local search algorithm in terms of exploring the search space to find globally optimal solutions. However, the primary downside of such algorithms is their low exploitative capability, which prevents the expansion of the search space neighborhood for more optimal solutions. The firefly algorithm (FA) is a population-based algorithm that has been widely used in clustering problems. However, FA is limited in terms of its premature convergence when no neighborhood search strategies are employed to improve the quality of clustering solutions in the neighborhood region and exploring the global regions in the search space. On these bases, this work aims to improve FA using variable neighborhood search (VNS) as a local search method, providing VNS the benefit of the trade-off between the exploration and exploitation abilities. The proposed FA-VNS allows fireflies to improve the clustering solutions with the ability to enhance the clustering solutions and maintain the diversity of the clustering solutions during the search process using the perturbation operators of VNS. To evaluate the performance of the algorithm, eight benchmark datasets are utilized with four well-known clustering algorithms. The comparison according to the internal and external evaluation metrics indicates that the proposed FA-VNS can produce more compact clustering solutions than the well-known clustering algorithms.
Received 6/10/2020
Accepted 14/2/2021
Published Online First 20/9/2021
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
References
Al-behadili HNK, Ku-Mahamud KR, Sagban R. Hybrid Ant Colony Optimization and Iterated Local Search for Rules-Based Classification. J Theor Appl Inf Technol. 2020;98(04):657–71.
Kuo RJ, Zulvia FE. An improved differential evolution with cluster decomposition algorithm for automatic clustering. Soft Comput. 2019;23(18):8957–73.
Xu D, Tian Y. A Comprehensive Survey of Clustering Algorithms. Ann Data Sci. 2015;2(2):165–93.
Mandala SR, Kumara SRT, Rao CR, Albert R. Clustering social networks using ant colony optimization. Oper Res. 2013;13(1):47–65.
Jabbar AM, Ku-Mahamud KR, Sagban R. Modified ACS Centroid Memory for Data Clustering. J Comput Sci. 2019;15(10):1439–49.
Gupta A, Datta S, Das S. Fast automatic estimation of the number of clusters from the minimum inter-center distance for k-means clustering. Pattern Recognit Lett. 2018;116(September):72–9.
Budiaji W. Medoid-based shadow value validation and visualization. Int J Adv Intell Informatics. 2019;5(2):76–88.
Tung AKH, Han J, Lakshmanan LVS, Ng RT. Constraint-based clustering in large databases. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2001.
Panasenko A, Khandeev V. Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem. Int Conf Math Optim Theory Oper Res. 2020;30–5.
Davidson I, Gourru A, Ravi S, Davidson I, Gourru A, The SR, et al. The Cluster Description Problem -Complexity Results , Formulations and Approximations To cite this version : HAL Id : hal-02060574 The Cluster Description Problem - Complexity Results , Formulations and Approximations. 2019;
Arunkumar N, Mohammed MA, Abd Ghani MK, Ibrahim DA, Abdulhay E, Ramirez-Gonzalez G, et al. K-Means clustering and neural network for object detecting and identifying abnormality of brain tumor. Soft Comput. 2019;23(19):9083–96.
Obaid OI, Mohammed MA, Abd Ghani MK, Mostafa SA, Al-Dhief FT. Evaluating the performance of machine learning techniques in the classification of Wisconsin Breast Cancer. Int J Eng Technol. 2018;7(4.36 Special Issue 36):160–6.
Reddy TN. Optimization of K-Means Algorithm: Ant Colony Optimization. In: International Conference on Computing Methodologies and Communication (ICCMC). 2017. p. 530–5.
Maghawry AM, Omar Y, Badr A. Initial Centroid Selection Optimization for K-Means with Genetic Algorithm to Enhance Clustering of Transcribed Arabic Broadcast News Documents. In: Silhavy R, Silhavy P, Prokopova Z, editors. Applied Computational Intelligence and Mathematical Methods. Cham: Springer International Publishing; 2018. p. 86–101.
Ghany KKA, AbdelAziz AM, Soliman THA, Sewisy AAEM. A hybrid modified step Whale Optimization Algorithm with Tabu Search for data clustering. J King Saud Univ - Comput Inf Sci. 2020;(February).
Zulvia RJKFE. Automatic clustering using an improved artificial bee colony optimization for customer segmentation. Knowl Inf Syst. 2018;(43).
Kumar V, Chhabra JK, Kumar D. Grey Wolf Algorithm-Based Clustering Technique. J Intell Syst. 2017;26(1):153–68.
Ezugwu AE. Nature-inspired metaheuristic techniques for automatic clustering: a survey and performance study. Vol. 2, SN Applied Sciences. Springer International Publishing; 2020.
Kittaneh R, Abdullah S, Abuhamdah A. terative Simulated Annealing for Medical Clustering Problems. Trends Appl Sci Res. 2012;(7):103–17.
Franzin A, Stützle T. Comparison of acceptance criteria in randomized local searches. Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinformatics). 2018;10764 LNCS(August):16–29.
Abuhamdah A. Adaptive Acceptance Criterion (AAC) algorithm for optimization problems. J Comput Sci. 2015;11(4):675–91.
Zhao F, He X, Yang G, Ma W, Zhang C, Song H. A hybrid iterated local search algorithm with adaptive perturbation mechanism by success-history based parameter adaptation for differential evolution (SHADE). Eng Optim. 2020;52(3):367–83.
Ayvaz D, Topcuoglu H, Gurgen F. Performance evaluation of evolutionary heuristics in dynamic environments. Appl Intell. 2012 Jul 1;37(1):130-44.
Xie H, Zhang L, Lim CP, Yu Y, Liu C, Liu H, et al. Improving K-means clustering with enhanced Firefly Algorithms. Appl Soft Comput J. 2019;
Abshouri AA, Bakhtiary A. A new clustering method based on Firefly and KHM. J Commun Comput. 2012;9:387–91.
Hansen P, Mladenović N. Variable neighborhood search. In: Handbook of Heuristics. 2018.
Wang H, Cui Z, Sun H, Rahnamayan S, Yang XS. Randomly attracted firefly algorithm with neighborhood search and dynamic parameter adjustment mechanism. Soft Comput. 2017;21(18):5325–39.
Huang KW, Girsang AS, Wu ZX, Chuang YW. A hybrid crow search algorithm for solving permutation flow shop scheduling problems. Appl Sci. 2019;9(7).
Jensen JH. A graph-based genetic algorithm and generative model/Monte Carlo tree search for the exploration of chemical space. Chem Sci. 2019;10(12):3567–72.
Yu S, Yang S, Su S. Self-adaptive step firefly algorithm. J Appl Math. 2013 Nov;2013.
Fan C, Fu Q, Long G, Xing Q. Hybrid artificial bee colony algorithm with variable neighborhood search and memory mechanism. J Syst Eng Electron. 2018;29(2):405–14.
Tang R, Fong S, Yang XS, Deb S. Integrating nature-inspired optimization algorithms to K-means clustering. In: 7th International Conference on Digital Information Management, ICDIM 2012. 2012.
Gao X, Wu S. CUBOS: An Internal Cluster Validity Index for Categorical Data. Teh Vjesn - Tech Gaz. 2019;26(2):486–94.
Lubis MDS, Mawengkang H, Suwilo S. Performance Analysis of Entropy Methods on K Means in Clustering Process. J Phys Conf Ser. 2017;930(1).
Nizam T, Hassan SI. Exemplifying the effects of distance metrics on clustering techniques: F-measure, accuracy and efficiency. In: Proceedings of the 7th International Conference on Computing for Sustainable Global Development, INDIACom 2020. 2020.
Zabihi F, Nasiri B. A Novel History-driven Artificial Bee Colony Algorithm for Data Clustering. Appl Soft Comput J. 2018;71:226–41.
Maulik U, Bandyopadhyay S. Genetic algorithm-based clustering technique. Pattern Recognit. 2000;33(9):1455–65.
Selim SZ, Alsultan K. A simulated annealing algorithm for the clustering problem. Pattern Recognit. 1991;24(10):1003–8.
Das P, Das DK, Dey S. A modified Bee Colony Optimization (MBCO) and its hybridization with k-means for an application to data clustering. Appl Soft Comput J. 2018;70:590–603.
Niknam T, Amiri B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Appl Soft Comput J. 2010;10(1):183–97.