روشی نوین جهت خوشه بندی داده مبتنی بر ترکیب الگوریتم‌های بهینه‌سازی ژنتیک و کرم شب‌تاب

سامانه‌های پردازشی و ارتباطی چندرسانه‌ای هوشمند

مقاله 4، دوره 2، شماره 4 - شماره پیاپی 6، دی 1400، صفحه 35-43   

نوع مقاله: مقاله پژوهشی

نویسندگان

مهسا افسردیر^{* 1}؛ منصوره افسردیر²

¹دانشگاه آزاد اسلامی واحد علوم تحقیقات، دانشکده فنی مهندسی، گروه مهندسی کامپیوتر، تهران، ایران

²دانشگاه آزاد اسلامی واحد دزفول، دانشکده فنی مهندسی، گروه مهندسی پزشکی دزفول، ایران

چکیده

یکی ازمسائل مهم درداده‌کاوی خوشه‌بندی است که بدون هدف ازپیش تعیین شده‌ای داده‌ها را بر اساس شباهت درون خوشه‌ها تقسیم‌بندی می‌کند. از روش‌های متداول خوشه‌بندی الگوریتم k-means است که بادریافت ورودی، داده‌هارابه k خوشه تقسیم‌بندی می‌کند. یکی ازمعایب این روش حساسیت به شرایط اولیه است که منجربه کاهش دقت درخوشه‌بندی می‌شود. از روش‌های بهبود عملکرد k-means می‌توان استفاده ازالگوریتم‌های فراابتکاری را نام برد. در این پژوهش به دو روش بهینه‌سازی ژنتیک و کرم شب‌تاب پرداخته شده است و الگوریتم جدیدی تحت عنوان الگوریتم ژنتیکی کرم‌شب‌تاب جهت بهینه‌سازی خوشه‌بندی k-means ارائه شده است. الگوریتم کرم‌شب‌تاب از الگوریتم‌های هوش جمعی است که از ویژگی نورچشمک زن کرم‌شب‌تاب الهام گرفته است و الگوریتم ژنتیک نوعی از الگوریتم‌های فراابتکاری است که از تکنیک-های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. در الگوریتم k-means برای اینکه مراکز خوشه به صورت تصادفی انتخاب می شوند، خوشه‌بندی دقت لازم را ندارد. با استفاده از الگوریتم‌های فراابتکاری سعی در بدست آوردن مراکز دقیق خوشه‌ها داشته و در نتیجه آن، خوشه-بندی صحیح می‌باشیم. در روش پیشنهادی، ابتدا الگوریتم k-means را روی داده‌های ورودی اجراکرده و خوشه‌بندی انجام می‌شود. سپس مضربی از مراکز خوشه که دراین الگوریتم بدست آمده است را به عنوان حد پایین و حد بالای الگوریتم پیشنهادی استفاده می‌کنیم. جمعیت اولیه به صورت تصادفی بین حد پایین و حد بالا تولید می‌شود. در حلقه اصلی الگوریتم جمعیت را به دو دسته جمعیت مساوی تقسیم می نماییم، بر روی دسته اول الگوریتم ژنتیک را اجرا می‌کنیم، بر روی دسته دوم بر اساس الگوریتم کرم‌شب‌تاب موقعیت‌های جدید را بدست می‌آوریم. حال جمعیت قبلی و جمعیت جدید بدست امده از الگوریتم ژنتیک و جمعیت جدید بدست امده از الگوریتم کرم‌شب‌تاب را تلفیق کرده وآن‌ها را از خوب به بد مرتب می‌کنیم و به تعداد مورد نیاز از آن‌ها را انتخاب و به ابتدای حلقه می‌رویم. این فرایند را تا برقراری شرط توقف ادامه می‌دهیم. درپایان الگوریتم k-means، الگوریتم کرم‌ شب‌تاب، الگوریتم ژنتیک و الگوریتم پیشنهادی بر روی سه مجموعه داده اعمال شده و نتایج مورد مقایسه قرار گرفته است.نتایج شبیه‌سازی نشان می‌دهد که الگوریتم ژنتیکی کرم‌شب‌تاب عملکرد بهتری در مقایسه با سایر روش‌ها داشته است.

کلیدواژه‌ها

داده کاوی؛ الگوریتم ژنتیک؛ الگوریتم کرم شب تاب؛ الگوریتم ژنتیکی کرم شب تاب؛ خوشه بندی k-means

مراجع

• [1] Yaghini, M., and Ghazanfari, N. "Tabu-KM: a hybrid clustering algorithm based on tabu search approach." International Journal of Industrial Engineering & Production Research 21, no. 2 (2010)
• [2] Jiawei, H., Kamber, M., Han, J., Kamber, M. and Pei, J. "Data Mining: Concepts and Techniques Elsevier." (2006).
• [3] Taber, R. "Clustering (Xu, R. and Wunsch II, DC; 2009) [Book review]." IEEE Computational Intelligence Magazine 4, no. 3 (2009): 92-95.
• [4] Berzal, F. and Matín, N. "Data mining: concepts and techniques by Jiawei Han and Micheline Kamber." ACM Sigmod Record 31, no. 2 (2002): 66-68.
• [5] Jain, A. K., and Dubes, R. C. Jain, Anil K., and Richard C. Dubes. "Algorithms for clustering data." Prentice-Hall, Inc., 1988.
• [6] Jain, A.K., "Data clustering: 50 years beyond K-means." Pattern recognition letters 31, no. 8 (2010): 651-666.
• [7] Hassanzadeh, T. and Meybodi, M.R. "A new hybrid approach for data clustering using firefly algorithm and K-means." In The 16th CSI international symposium on artificial intelligence and signal processing (AISP 2012), pp. 007-011. IEEE, 2012.
• [8] Yang, X. S. "Firefly algorithms for multimodal optimization." In International symposium on stochastic algorithms, pp. 169-178. Springer, Berlin, Heidelberg, 2009.
• [9] Moscato, P. "On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms." Caltech concurrent computation program, C3P Report 826 (1989): 1989.
• [10] Dianati, M., Song, I. and Treiber, M. An introduction to genetic algorithms and evolution strategies. Technical report, University of Waterloo, Ontario, N2L 3G1, Canada, 2002.
• [11] Wahid, F., Ghazali, R. & Ismail, L.H. Improved Firefly Algorithm Based on Genetic Algorithm Operators for Energy Efficiency in Smart Buildings. Arab J Sci Eng 44, 4027–4047 (2019).
• [12] Mahshwar, Keshva Kaushik, Vikram Arora. A Hybrid Data Clustering Using Firefly Algorithm Based Improved Genetic Algorithms. Sciencedirect. Procedia Computer Science 58 (2015) 249-256.
• [13] M A El-Shorbagy, Adel M El-Refaey, A hybrid genetic–firefly algorithm for engineering design problems, Journal of Computational Design and Engineering, Volume 9, Issue 2, April 2022, Pages 706-730,
• [14] Mustafa Servet Kiran, Ahmet Babalik. Improved Artificial Bee Colony Algorithm for Continuous Optimization Problems. Journal of Computer and Communications, 2014, 2, 108-116.
• [15] Abdullah, A., Deris, S., Mohamad, M.S., Hashim, S.Z.M. (2012). A New Hybrid Firefly Algorithm for Complex and Nonlinear Problem. In: Omatu, S., De Paz Santana, J., González, S., Molina, J., Bernardos, A., Rodríguez, J. (eds) Distributed Computing and Artificial Intelligence. Advances in Intelligent and Soft Computing, vol 151. Springer, Berlin, Heidelberg.
• [16] Hassanzadeh. t, meybodi.m, “A new hybrid Approach for Data clustering using firefly Algorithm and k-means”
• [17] J. senthilnath, S.N.omkar, “clustering using firefly algorithm:performance study”,swarm and Evolutionary Computation, volume1,ISSue3, pp 164-171,September 2011.
• [18] Hassanzadeh,Tahereh, Meybodi ,Mohammad Reza, A New Hybrid Approach For Data Clustering Using Firefly Algorithm And K-Means, The 16th CSI International Symposium On Artificial Intelligence And Signal Processing (AISP), 2012,007-011.
• [19] Binlu, Fangyuan Ju, An Optimized Genetic K-Means Clustering Algorithm, Computer Science and Information Processing (CSIP),2012,1296-1299.