روشی نوین برای خوشه‌بندی داده‌ها با استفاده از الگوریتم بهینه‌سازی چهارگرگ خاکستری
محورهای موضوعی : مهندسی برق و کامپیوتر
لاله عجمی بختیاروند
1
,
زهرا بهشتی
2
*
1 - دانشگاه آزاد اسلامی واحد نجف آباد،دانشكده مهندسي كامپيوتر
2 - دانشگاه آزاد اسلامی واحد نجف آباد،دانشكده مهندسي كامپيوتر
کلید واژه: الگوریتم‌های فراابتکاری, الگوریتم بهینه‌سازی گرگ خاکستری, الگوریتم بهینه‌سازی چهارگرگ, خوشه‌بندی,
چکیده مقاله :
امروزه، خوشه‌بندی داده‌ها به دلیل حجم و تنوع داده‌ها بسیار مورد توجه قرار گرفته است. مشکل اصلی روش‌های خوشه‌بندهای معمول این است که در دام بهینه محلی گرفتار می‌آیند. الگوریتم‌های فراابتکاری به دلیل داشتن توانایی فرار از بهینه‌های محلی، نتایج موفقی را در خوشه‌بندی داده‌ها نشان داده‌اند. الگوریتم بهینه‌سازی گرگ خاکستری از جمله این دسته الگوریتم‌ها است که قابلیت بهره‌برداری خوبی دارد و در برخی از مسایل راه حل مناسبی ارائه داده است، اما اکتشاف آن ضعیف است و در بعضی از مسایل به بهینه محلی همگرا می‌شود. در این تحقیق برای بهبود خوشه‌بندی داده‌ها، نسخه بهبودیافته‌ای از الگوریتم بهینه‌سازی گرگ خاکستری به نام الگوریتم بهینه‌سازی چهارگرگ خاکستری ارائه شده که با استفاده از بهترین موقعیت دسته چهارم گرگ‌ها به نام گرگ‌های امگای پیشرو در تغییر موقعیت هر گرگ، قابلیت اکتشاف بهبود می‌یابد. با محاسبه امتیاز هر گرگ نسبت به بهترین راه حل، نحوه حرکت آن مشخص می‌شود. نتایج الگوریتم پیشنهادی چهارگرگ خاکستری با الگوریتم‌های بهینه‌سازی گرگ خاکستری، بهینه‌سازی ازدحام ذرات، کلونی زنبور عسل مصنوعی، ارگانیسم‌های هم‌زیست و بهینه‌سازی ازدحام سالپ در مسأله خوشه‌بندی روی چهارده مجموعه دادگان ارزیابی شده است. همچنین عملکرد الگوریتم پیشنهادی با چند نسخه بهبودیافته از الگوریتم گرگ خاکستری مقایسه شده است. نتایج به دست آمده عملکرد قابل توجه الگوریتم پیشنهادی را نسبت به سایر الگوریتم‌های فراابتکاری مورد مقایسه در مسأله خوشه‌بندی نشان می‌دهد. بر اساس میانگین معیار F روی تمام مجموعه دادگان، روش پیشنهادی 82/172% و الگوریتم بهینه ذرات 78/284% را نشان می‌دهد و در مقایسه با نسخه‌های بهبودیافته الگوریتم گرگ، الگوریتم EGWO که در رتبه بعدی است دارای میانگین معیار F برابر 80/656% می‌باشد.
Nowadays, clustering methods have received much attention because the volume and variety of data are increasing considerably.The main problem of classical clustering methods is that they easily fall into local optima. Meta-heuristic algorithms have shown good results in data clustering. They can search the problem space to find appropriate cluster centers. One of these algorithms is gray optimization wolf (GWO) algorithm. The GWO algorithm shows a good exploitation and obtains good solutions in some problems, but its disadvantage is poor exploration. As a result, the algorithm converges to local optima in some problems. In this study, an improved version of gray optimization wolf (GWO) algorithm called 4-gray wolf optimization (4GWO) algorithm is proposed for data clustering. In 4GWO, the exploration capability of GWO is improved, using the best position of the fourth group of wolves called scout omega wolves. The movement of each wolf is calculated based on its score. The better score is closer to the best solution and vice versa. The performance of 4GWO algorithm for the data clustering (4GWO-C) is compared with GWO, particle swarm optimization (PSO), artificial bee colony (ABC), symbiotic organisms search (SOS) and salp swarm algorithm (SSA) on fourteen datasets. Also, the efficiency of 4GWO-C is compared with several various GWO algorithms on these datasets. The results show a significant improvement of the proposed algorithm compared with other algorithms. Also, EGWO as an Improved GWO has the second rank among the different versions of GWO algorithms. The average of F-measure obtained by 4GWO-C is 82.172%; while, PSO-C as the second best algorithm provides 78.284% on all datasets.
[1] M. Jafarzadegan, F. Safi-Esfahani, and Z. Beheshti, "Combining hierarchical clustering approaches using the PCA method," Expert Syst. Appl., vol. 137, pp. 1-10, Dec 2019.
[2] J. Han, J. Pei, and M. Kamber, Data Mining: Concepts and Techniques, Elsevier, 2011.
[3] D. J. Hand, "Principles of data mining," Drug Saf., vol. 30, no. 7, pp. 621-622, Jul. 2007.
[4] D. T. Dinh and V. N. Huynh, "k-PbC: an improved cluster center initialization for categorical data clustering," Appl. Intell., vol. 50, no. 8, pp. 2610-2632, Aug. 2020.
[5] R. Xu and D. Wunsch, "Survey of clustering algorithms," IEEE Trans. Neural Networks, vol. 16, no. 3, pp. 645-678, May 2005.
[6] Z. Beheshti, "A novel x-shaped binary particle swarm optimization," Soft Comput., vol. 25, no. 4, pp. 3013-3042, Feb. 2021.
[7] Z. Beheshti, "UTF: upgrade transfer function for binary meta-heuristic algorithms," Appl. Soft Comput., vol. 106, Article ID: 107346, 28 pp., Jul. 2021.
[8] R. Salgotra, U. Singh, S. Singh, G. Singh, and N. Mittal, "Self-adaptive salp swarm algorithm for engineering optimization problems," Appl. Math. Model., vol. 89, pp. 188-207, Jul. 2021.
[9] Z. Beheshti, "BMNABC: binary multi-neighborhood artificial bee colony for high-dimensional discrete optimization problems," Cybern. Syst., vol. 49, no. 7-8, pp. 452-474, Nov. 2018.
[10] Z. Beheshti, S. M. Shamsuddin, S. Hasan, and N. E. Wong, "Improved centripetal accelerated particle swarm optimization," Int. J. Adv. Soft Comput. its Appl., vol. 8, no. 2, pp. 1-26, Jul. 2016.
[11] I. Aljarah, M. Mafarja, A. A. Heidari, H. Faris, and S. Mirjalili, "Clustering analysis using a novel locality-informed grey wolf-inspired clustering approach," Knowl. Inf. Syst., vol. 62, no. 2, pp. 507-539, Feb. 2020.
[12] H. D. Menendez, F. E. B. Otero, and D. Camacho, "Medoid-based clustering using ant colony optimization," Swarm Intell., vol. 10, no. 2, pp. 123-145, Jul. 2016.
[13] P. Das, D. K. Das, and S. Dey, "A modified bee colony optimization (MBCO) and its hybridization with k-means for an application to data clustering," Appl. Soft Comput., vol. 70, pp. 590-603, Sept. 2018.
[14] R. J. Kuo and F. E. Zulvia, "An improved differential evolution with cluster decomposition algorithm for automatic clustering," Soft Comput., vol. 23, no. 18, pp. 8957-8973, Sept. 2019.
[15] T. Ashish, S. Kapil, and B. Manju, "Parallel bat algorithm-based clustering using mapreduce," In: G. Perez, K. Mishra, S. Tiwari, and M. Trivedi (eds), Networking Communication and Data Knowledge Engineering, Lecture Notes on Data Engineering and Communications Technologies, vol 4. Springer, pp. 73-82, 2018.
[16] O. Tarkhaneh, A. Isazadeh, and H. J. Khamnei, "A new hybrid strategy for data clustering using cuckoo search based on Mantegna levy distribution, PSO and k-means," Int. J. Comput. Appl. Technol., vol. 58, no. 2, pp. 137-149, Jan. 2018.
[17] H. A. Abdulwahab, A. Noraziah, A. A. Alsewari, and S. Q. Salih, "An enhanced version of black hole algorithm via levy flight for optimization and data clustering problems," IEEE Access, vol. 7, pp. 142085-142096, Aug. 2019.
[18] K. W. Huang, Z. X. Wu, H. W. Peng, M. C. Tsai, Y. C. Hung, and Y. C. Lu, "Memetic particle gravitation optimization algorithm for solving clustering problems," IEEE Access, vol. 7, pp. 80950-80968, Jan. 2019.
[19] H. Yu, Z. Chang, G. Wang, and X. Chen, "An efficient three-way clustering algorithm based on gravitational search," Int. J. Mach. Learn. Cybern., vol. 11, no. 5, pp. 1003-1016, May 2020.
[20] A. Kaur, S. K. Pal, and A. P. Singh, "Hybridization of chaos and flower pollination algorithm over K-means for data clustering," Appl. Soft Comput., vol. 97, Article ID: 105523, 17 pp., Dec. 2019.
[21] Y. Zhou, H. Wu, Q. Luo, and M. Abdel-Baset, "Automatic data clustering using nature-inspired symbiotic organism search algorithm," Knowledge-Based Syst., vol. 163, pp. 546-557, Jan. 2019.
[22] G. Drakopoulos, et al., "A genetic algorithm for spatiosocial tensor clustering," Evol. Syst., vol. 11, no. 3, pp. 1-11, Sept. 2019. [23] M. Alswaitti, M. Albughdadi, and N. A. M. Isa, "Density-based particle swarm optimization algorithm for data clustering," Expert Syst. Appl., vol. 91, pp. 170-186, Jan. 2018.
[24] J. Chen, X. Qi, L. Chen, F. Chen, and G. Cheng, "Quantum-inspired ant lion optimized hybrid k-means for cluster analysis and intrusion detection," Knowledge-Based Syst., vol. 203, Article ID: 106167, 10 pp., Sept. 2020.
[25] L. M. Abualigah, A. T. Khader, E. S. Hanandeh, and A. H. Gandomi, "A novel hybridization strategy for krill herd algorithm applied to clustering techniques," Appl. Soft Comput., vol. 60, pp. 423-435, Nov. 2017.
[26] M. Demri, S. Ferouhat, S. Zakaria, and M. E. Barmati, "A hybrid approach for optimal clustering in wireless sensor networks using cuckoo search and simulated annealing algorithms," in Proc. 2nd Int. Conf. on Mathematics and Information Technology, ICMIT’20, pp. 202-207, Adrar, Algeria, 18-19 Feb. 2020.
[27] S. Gavel, P. Joshi, S. Tiwari, and A. S. Raghuvanshi, "An optimized hybrid clustering method using salp swarm optimization with K-means," In: V. Nath and J. Mandal (eds) Nanoelectronics, Circuits and Communication Systems. Nanoelectronics, Circuits and Communication Systems, Lecture Notes in Electrical Engineering, vol. 692, Springer, pp. 247-254, 2020.
[28] S. K. Majhi, "Fuzzy clustering algorithm based on modified whale optimization algorithm for automobile insurance fraud detection," Evol. Intell., vol. 14, no. 1, pp. 35-46, 2021.
[29] E. Rashedi, H. Nezamabadipour, and S. Saryazdi, "GSA: a gravitational search algorithm," Inf. Sci. (Ny), vol. 179, no. 13, pp. 2232-2248, Jan. 2009.
[30] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Adv. Eng. Softw., vol. 69, pp. 46-61, 2014.
[31] G. P. Gupta and S. Jha, "Integrated clustering and routing protocol for wireless sensor networks using Cuckoo and Harmony Search based metaheuristic techniques," Eng. Appl. Artif. Intell., vol. 68, pp. 101-109, Feb. 2018.
[32] G. P. Gupta and B. Saha, "Load balanced clustering scheme using hybrid metaheuristic technique for mobile sink based wireless sensor networks," J. Ambient Intell. Humaniz. Comput., 12 pp., Apr. 2020. (in Press)
[33] M. Shakil, A. Fuad Yousif Mohammed, R. Arul, A. K. Bashir, and J. K. Choi, "A novel dynamic framework to detect DDoS in SDN using metaheuristic clustering," Trans. Emerg. Telecommun. Technol., 12 pp., Apr. 2019. (in Press)
[34] R. J. Kuo, T. C. Lin, F. E. Zulvia, and C. Y. Tsai, "A hybrid metaheuristic and kernel intuitionistic fuzzy c-means algorithm for cluster analysis," Appl. Soft Comput., vol. 67, pp. 299-308, Jan. 2018.
[35] A. Kaur and Y. Kumar, "A new metaheuristic algorithm based on water wave optimization for data clustering," Evol. Intell., 12 pp., Jan. 2021.
[36] M. Ghobaei-Arani and A. Shahidinejad, "An efficient resource provisioning approach for analyzing cloud workloads: a metaheuristic-based clustering approach," J. Supercomput., vol. 77, no. 1, pp. 711-750, 2021.
[37] ح. املشی و ی. بستانی املشی، "روشی جدید به منظور خوشه‌بندی داده‌های سرعت باد در نیروگاه‌های بادی با استفاده از الگوریتم‌های FCM و PSO،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، سال 8، شماره 3، صص. 214-210، پاییز 1389.
[38] م. ع. نژاد و م. خرد، "استفاده از خوشه‌بندی BIRCH و الگوریتم بهینه‌سازی واکنش شیمیایی جهت کشف تقلب در حوزه سلامت،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 17، شماره 2، صص. 160-153، تابستان 1398.
[39] م. یقینی و ج. لسان، "حل مسأله خوشه‌بندی ظرفیت‌دار با استفاده از روش‌های مبتنی بر الگوریتم‌های شبیه‌سازی تبریدی و ژنتیک،" نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، دوره 21، شماره 3، صص. 54-45، پاییز 1389.
[40] ع. فهمی جعفرقلخانلو و م. شمسی، "بخش‌بندی تصاویر رنگی چهره مبتنی بر خوشه‌بند فازی بهینه‌سازی شده با الگوریتم‌های گرگ خاکستری و نهنگ،" مجله علمی رایانش نرم و فناوری اطلاعات، دوره 10، شماره 2، صص. 13-1، تیر 1400.
[41] Y. Li, X. Lin, and J. Liu, "An improved gray wolf optimization algorithm to solve engineering problems," Sustainability, vol. 13, no. 6, Article ID: 3208, 23 pp., 15 Mar. 2021.
[42] M. Kohli and S. Arora, "Chaotic grey wolf optimization algorithm for constrained optimization problems," J. Comput. Des. Eng., vol. 5, no. 4, pp. 458-472, Oct. 2018.
[43] Z. Yue, S. Zhang, and W. Xiao, "A novel hybrid algorithm based on grey wolf optimizer and fireworks algorithm," Sensors, vol. 20, no. 7, Article ID: 2147, 17 pp., Jan. 2020.
[44] ع. محمدزاده، م. مصدری، ف. سلیمانیان قره¬چپق و ا. جعفریان، " ارائه یک الگوریتم بهبودیافته بهینه سازی گرگ های خاکستری برای زمان‌بندی جریان کار در محیط محاسبات ابری،" مجله علمی رایانش نرم و فناوری اطلاعات، دوره 8، شماره 4، صص. 29-17، بهمن 1398.
[45] W. Long, J. Jiao, X. Liang, and M. Tang, "An exploration-enhanced grey wolf optimizer to solve high-dimensional numerical optimization," Eng. Appl. Artif. Intell., vol. 68, pp. 63-80, Feb. 2018.
[46] M. H. Qais, H. M. Hasanien, and S. Alghuwainem, "Augmented grey wolf optimizer for grid-connected PMSG-based wind energy conversion systems," Appl. Soft Comput., vol. 69, pp. 504-515, Aug. 2018.
[47] K. Luo, "Enhanced grey wolf optimizer with a model for dynamically estimating the location of the prey," Appl. Soft Comput., vol. 77, no. ???, pp. 225-235, Apr. 2019.
[48] E. Akbari, A. Rahimnejad, and S. A. Gadsden, "A greedy non‐hierarchical grey wolf optimizer for real‐world optimization," Electron. Lett., vol. 57, no. 13, pp. 499-501, Jan. 2021.
[49] A. Bahrololoum, H. Nezamabadipour, and S. Saryazdi, "A data clustering approach based on universal gravity rule," Eng. Appl. Artif. Intell., vol. 45, pp. 415-428, Oct. 2015.
[50] D. Dua and C. Graff, {UCI} Machine Learning Repository, 2017.
[51] J. Derrac, S. Garcia, D. Molina, and F. Herrera, "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms," Swarm Evol. Comput., vol. 1, no. 1, pp. 3-18, Mar. 2011.