علوم رایانشی

علوم رایانشی

بهینه‌سازی الگوریتم k-میانگین در خوشه‌بندی داده‌ها با استفاده از الگوریتم هوش جمعی بهینه‌سازی گرگ خاکستری و الگوریتم تشخیص داده پرت جنگل جداسازی

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

نویسندگان
1 دانشجوی کارشناسی ارشد گروه مهندسی کامپیوتر، دانشگاه بین‌المللی امام خمینی (ره)، قزوین، ایران
2 استادیار گروه مهندسی کامپیوتر، دانشگاه بین‌المللی امام خمینی (ره)، قزوین، ایران
10.22034/csj.2024.209865
چکیده
امروزه علم داده و خوشه‌بندی داده‌ها به‌عنوان ابزارهای حیاتی برای تحلیل و پردازش داده‌های خام و استخراج دانش به منظور تصمیم‌سازی و تصمیم‌گیری‌های کلان شناخته می‌شوند. یکی از روش‌های اصلی طبقه‌بندی داده‌ها، خوشه‌بندی است که در آن عناصر درون هر خوشه باید با یکدیگر مشابه و با عناصر خوشه‌های دیگر متفاوت باشند. الگوریتم k- میانگین به‌عنوان یکی از روش‌های پرکاربرد در خوشه‌بندی داده‌ها به‌شمار می‌آید و در بسیاری از کاربردهای عملی مورد استفاده قرار می‌گیرد. با این حال، این الگوریتم دارای دو نقص اساسی است: اول، وابستگی شدید کیفیت خوشه‌ها به انتخاب مراکز اولیه، و دوم، تأثیر نقاط پرت بر عملکرد خوشه‌بندی. در این مقاله، یک روش پیشرفته برای بهینه‌سازی الگوریتم  k- میانگین با استفاده از الگوریتم بهینه‌سازی گرگ خاکستری (GWO) برای انتخاب اولیه مراکز خوشه و همچنین الگوریتم جنگل جداسازی (IF) برای حذف نقاط پرت معرفی شده است. در این مقاله آزمایش‌های مختلف بر روی مجموعه داده‌‌های سنتزی و داده‌‌های واقعی انجام شد و هر کدام از آزمایش‌‌ها با دو سنجه شاخص رند اصلاح شده و خطای تعداد خوشه‌‌ها (میانگین اختلاف بین تعداد خوشه‌‌های واقعی و تعداد براورد شده توسط الگوریتم) مورد ارزیابی قرار گرفتند. آزمایش‌های انجام شده نشان داد که الگوریتم پیشنهادی هم از نظر شاخص رند اصلاح شده و هم از نظر خطای تعداد خوشه‌‌ها پیشرفت قابل ملاحظه‌‌ای را در مقایسه با k-میانگین پایه نشان می‌‌دهد. به گونه‌‌ای که در شاخص رند اصلاح شده، امتیاز آن از 74/0 به 93/0 ارتقا یافت. همچنین از نظرمیانگین تعداد خطای خوشه‌‌ها، میانگین خطای آن از عدد 47/0 به 16/0 کاهش یافت این آزمایش‌های گسترده و متعدد بر روی داده‌های متنوع نشان داد که این الگوریتم ترکیبی توانسته است به شکل قابل ملاحظه‌ای الگوریتم  k- میانگین اولیه را از جهات گوناگون بهبود ببخشد و بتواند راه‌حلی نویدبخش برای کاربردهای آتی خوشه‌بندی داده‌ها باشد.
کلیدواژه‌ها
موضوعات

 [1] Gan, G., & Ng, M. K. P. (2017). K-means clustering with outlier removal. Pattern Recognition Letters, 90, 8-14.
 [2] Khan, F. (2012). An initial seed selection algorithm for k-means clustering of georeferenced data to improve replicability of cluster assignments for mapping application. Applied Soft Computing, 12(11), 3698-3700.
 [3] Nazeer, K. A., & Sebastian, M. P. (2009, July). Improving the Accuracy and Efficiency of the k-means Clustering Algorithm. In Proceedings of the world congress on engineering (Vol. 1, pp. 1-3). London, UK: Association of Engineers London.
 [4] Yedla, M., Pathakota, S. R., & Srinivasa, T. M. (2010). Enhancing K-means clustering algorithm with improved initial center. International Journal of computer science and information technologies, 1(2), 121-125.
 [5] Singh, H., & Kaur, K. (2013). Review of existing methods for finding initial clusters in K-means algorithm. International Journal of Computer Applications, 68(14).
 [6] Velmurugan, T., & Santhanam, T. (2011). A survey of partition-based clustering algorithms in data mining: An experimental approach. Information Technology Journal, 10(3), 478-484.
 [7] Younus, Z. S., Mohamad, D., Saba, T., Alkawaz, M. H., Rehman, A., Al-Rodhaan, M., & Al-Dhelaan, A. (2015). Content-based image retrieval using PSO and k-means clustering algorithm. Arabian Journal of Geosciences, 8, 6211-6224.
[8] Pandey, A., & Shukla, M. (2014). Survey performance approach k-Mean and k-Mediod clustering algorithm. Binary Journal of Data Mining & Networking, 4(1), 14-16.
 [9] Patel, A., & Singh, P. (2013). New Approach for K-mean and K-medoids Algorithm. International Journal of Computer Applications Technology and Research, 2(1), 1-5.
 [10] Hariri, S., Kind, M. C., & Brunner, R. J. (2019). Extended isolation forest. IEEE Transactions on Knowledge and Data Engineering, 33(4), 1479-1489.
[11] Wu, M., Li, X., Liu, C., Liu, M., Zhao, N., Wang, J., ... & Zhu, L. (2019). Robust global motion estimation for video security based on improved k-means clustering. Journal of Ambient Intelligence and Humanized Computing, 10, 439-448.
[12] Sinaga, K. P., & Yang, M. S. (2020). Unsupervised K-means clustering algorithm. IEEE access, 8, 80716-80727.
 [13] Sharma, I., Kumar, V., & Sharma, S. (2022). A comprehensive survey on grey wolf optimization. Recent Advances in Computer Science and Communications (Formerly: Recent Patents on Computer Science), 15(3), 323-333.
 [14] Selvaraj, S., & Choi, E. (2020, January). Survey of swarm intelligence algorithms. In Proceedings of the 3rd International Conference on Software Engineering and Information Management (pp. 69-73).
 [15] Purushothaman, R., Rajagopalan, S. P., & Dhandapani, G. (2020). Hybridizing Gray Wolf Optimization (GWO) with Grasshopper Optimization Algorithm (GOA) for text feature selection and clustering. Applied Soft Computing, 96, 106651.
 [16] Tekerek, A. D. E. M., & Dörterler, M. U. R. A. T. (2020). The adaptation of gray wolf optimizer to data clustering. Politeknik Dergisi, 1-1.
 [17] Ahmadi, R., Ekbatanifard, G., & Bayat, P. (2021). A modified grey wolf optimizer-based data clustering algorithm. Applied Artificial Intelligence, 35(1), 63-79.
 [18] Mosavi, S. K., Jalalian, E., Soleimenian, F., & Branch, U. (2018). A comprehensive survey of grey wolf optimizer algorithm and its application. Int. J. Adv. Robot. Expert Syst., 1(6), 23-45.
 [19] Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in engineering software, 69, 46-61.
 [20] Gao, Z. M., & Zhao, J. (2019). An improved grey wolf optimization algorithm with variable weights. Computational Intelligence and Neuroscience.
 [21] Liu, F. T., Ting, K. M., & Zhou, Z. H. (2012). Isolation-based anomaly detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(1), 1-39.
 [22] Karczmarek, P., Kiersztyn, A., Pedrycz, W., & Al, E. (2020). K-Means-based isolation forest. Knowledge-based systems, 195, 105659.
 [23] Guo, T., Yan, J., Chen, J., & Yu, Y. (2023). Overflow Capacity Prediction of Pumping Station Based on Data Drive. Water, 15(13), 2380.
 [24] Xiao, B., Wang, Z., Liu, Q., & Liu, X. (2018). SMK-means: an improved mini batch k-means algorithm based on mapreduce with big data. Computers, Materials & Continua, 56(3).
 [25] Geng, Zhang, Chengchang Zhang, Huayu Zhang. (2018). Improved K-means Algorithm Based on Density Canopy. Knowledge-Based Systems.
 [26] Sukumar, J. A., Pranav, I., Neetish, M. M., & Narayanan, J. (2018, September). Network intrusion detection using improved genetic k-means algorithm. In 2018 international conference on advances in computing, communications and informatics (ICACCI) (pp. 2441-2446). IEEE.
 [27] Yu, S. S., Chu, S. W., Wang, C. M., Chan, Y. K., & Chang, T. C. (2018). Two improved k-means algorithms. Applied Soft Computing, 68, 747-755.
 [28] Xu, H., Yao, S., Li, Q., & Ye, Z. (2020, September). An improved k-means clustering algorithm. In 2020 IEEE 5th international symposium on smart and wireless systems within the conferences on intelligent data acquisition and advanced computing systems (IDAACS-SWS) (pp. 1-5). IEEE.
 [29] Kodinariya, T. (2014). Survey on existing methods for selecting initial centroids in K-means clustering. International journal of Engineering Development And Research, vol. 2, pp. 2865-2868.
 [30] Ay, M., Özbakır, L., Kulluk, S., Gülmez, B., Öztürk, G., & Özer, S. (2023). FC-Kmeans: Fixed-centered K-means algorithm. Expert Systems with Applications, 211, 118656.
 [31] Ye, T., Ye, J., & Wang, L. (2023). Improved rough K-means clustering algorithm based on firefly algorithm. International Journal of Computing Science and Mathematics, 17(1), 1-12.       
 [32] Vu, V. V., & Labroche, N. (2017). Active seed selection for constrained clustering. Intelligent Data Analysis, 21(3), 537-552.
 [33] Chithra, P. L. (2017). Premeditated initial points for K-Means Clustering. IJCSIS, 15(9).
 [34] Hu, H., Liu, J., Zhang, X., & Fang, M. (2023). An Effective and Adaptable K-means Algorithm for Big Data Cluster Analysis. Pattern Recognition, 139, 109404.   
 [35] Cheng, D., Huang, J., Zhang, S., Xia, S., Wang, G., & Xie, J. (2023). K-Means Clustering with Natural Density Peaks for Discovering Arbitrary-Shaped Clusters. IEEE Transactions on Neural Networks and Learning Systems.                                                                                                      
 [36] Kathiresan, V., & Sumathi, P. (2012, January). An efficient clustering algorithm based on Z-score ranking method. In 2012 International Conference on Computer Communication and Informatics (pp. 1-4). IEEE.
 [37] M. Sakthi and A. S. Thanamani. (2011). An effective determination of initial centroids in K-means clustering using kernel PCA. International Journal of Computer Science and Information Technologies, vol. 2, no. 3, pp. 955–959.
 [38] Khorasani, F., Zanjireh, M. M., Bahaghighat, M., & Xin, Q. (2022). A Tradeoff Between Accuracy and Speed for K-Means Seed Determination. Comput. Syst. Sci. Eng., 40(3), 1085-1098.