Графові алгоритми кластеризації: виділення зв'язкових компонент та оптимізація методів групування

Н. Бойко

doi:10.24144/2616-7700.2025.46(1).149-165

Автор(и)

Н. Бойко Національний університет "Львівська політехніка", Україна https://orcid.org/0000-0002-6962-9363

DOI:

https://doi.org/10.24144/2616-7700.2025.46(1).149-165

Ключові слова:

кластеризація, BFS, машинне навчання, оптимізація алгоритму, аналіз даних, викиди, порогове значення

Анотація

У даній роботі досліджено методи кластеризації даних, зокрема алгоритм BFS (обхід у ширину) та його оптимізацію для підвищення ефективності. Кластеризація є важливим етапом аналізу великих обсягів інформації, що використовується у різних сферах, зокрема у медичних дослідженнях, аналізі ринкових тенденцій та машинному навчанні. Метою дослідження було виявлення сильних і слабких сторін BFS у задачах групування даних, а також розробка методів його покращення. Для цього було проаналізовано особливості різних підходів до кластеризації, визначено їхні переваги та недоліки, а також проведено порівняння BFS із іншими методами, такими як KNN (метод k найближчих сусідів). Результати дослідження показали, що BFS є ефективним для групування даних, особливо у випадках, коли об’єкти мають природну кластерну структуру. Основними перевагами алгоритму є його здатність працювати з розрідженими даними, обробляти аномальні значення (викиди) та легко адаптуватися до різних порогових значень. Однак основним недоліком залишається його обмежена масштабованість при обробці великих наборів даних. Проаналізовано що BFS у модифікованій формі є потужним інструментом для кластеризації, який може бути застосований у різних сферах аналізу даних. Однак подальші дослідження необхідні для розширення його можливостей, зокрема шляхом впровадження механізмів автоматичного налаштування параметрів, а також адаптації алгоритму для роботи з великими даними за допомогою розподілених обчислень.

Спонсор дослідження

Національний фонд досліджень України

Біографія автора

Н. Бойко, Національний університет "Львівська політехніка"

Доцент кафедри системи штучного інтелекту. Кандидат економічних наук

Посилання

Sarker, A., Shamim, S. M., Shahiduz Zama, Dr. Md., & Mustafizur Rahman Md. (2018). Employee’s performance analysis and prediction using K-means clustering & decision tree algorithm. Global Journal of Computer Science and Technology, 18, 1–4.
Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O. P., Tiwari, A., & Lin, C. T. (2017). A review of clustering techniques and developments. Neurocomputing, 26. 664–681.
Hossain, M. Z., Akhtar, M. N., Ahmad, R. B., & Rahman, M. (2016). A dynamic K-means clustering for data mining. Indonesian Journal of Electrical Engineering and Computer Science, 3(2), 521–526. https://doi.org/10.11591/ijeecs.v13.i2.pp521-526
Yim, O., & Ramdeen, K. T. (2015). Hierarchical Cluster Analysis: Comparison of Three Linkage Measures and Application to Psychological Data. The Quantitative Methods for Psychology, 11(1), 8–21. https://doi.org/10.20982/tqmp.11.1.p008
Sneath, P., & Sokal, R. (2015). Hierarchical Cluster Analysis: Comparison of Three Linkage Measures and Application to Psychological Data. The Quantitative Methods for Psychology. 11(1), 8–21. https://doi.org/10.20982/tqmp.11.1.p008
Fraley, C., & Raftery, A. E. (1998). How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis. Technical Report. Department of Statistics University of Washington, 41(8), 578–588. https://doi.org/10.1093/comjnl/41.8.578
Murtagh, F. (2020). A survey of recent advances in hierarchical clustering algorithms which use cluster centers. Computer Journal, 26(4), 354–359.
Ptitsyn, A., Hulver, M., Cefalu, W., York, D., & Smith, S. R. (2016). Unsupervised clustering of gene expression data points at hypoxia as possible trigger for metabolic syndrome. BMC Genomics, 7(1), 318. https://doi.org/10.1186/1471-2164-7-318
Tung, A. K., Hou, J., & Han, J. (02–06 April, 2001). Spatial clustering in the presence of obstacles. In Proceedings 17th International Conference on Data Engineering. Heidelberg: Germany. https://doi.org/10.1109/ICDE.2001.914848
Boehm, C., Kailing, K., Kriegel, H., & Kroeger, P. (01–04 November, 2004). Density connected clustering with local subspace preferences. In Fourth IEEE International Conference on Data Mining (ICDM’04). Brighton: UK. https://doi.org/10.1109/ICDM.2004.10087
Boyko, N., Hetman, S., & Kots, I. (2021). Comparison of Clustering Algorithms for Revenue and Cost Analysis. In Proceedings of the 5th International Conference on Computational Linguistics and Intelligent Systems (COLINS 2021). Lviv: Ukraine. Retrieved from https://ceur-ws.org/Vol-2870/paper136.pdf
Procopiuc, C. M., Jones, M., Agarwal, P. K., & Murali, T. M. (4–6 June, 2002). A Monte Carlo algorithm for fast projective clustering. In ACM SIGMOD Intern. conf. on management of data. Madison, Wisconsin: USA.
Boyko, N. (2016). Application of mathematical models for improvement of “cloud” data processes organization. Mathematical Modeling and Computing, 3(2), 111–119. https://doi.org/10.23939/mmc2016.02.111
Slamet, C., Rahman, A., Ramdhani, M. A., & Darmalaksana, W. (2016). Clustering the verses of the Holy Qur’an using K-means algorithm. Asian Journal of Information Technology, 15(24), 5159–5162. http://doi.org/10.3923/ajit.2016.5159.5162
Boyko, N., Kmetyk-Podubinska, K., & Andrusiak, I. (2021). Application of Ensemble Methods of Strengthening in Search of Legal Information. Lecture Notes on Data Engineering and Communications Technologies, 77, 188–200. https://doi.org/10.1007/978-3-030-82014-5_13
Bekiros, S., Nguyen, D. K., Sandoval, J. L., & Uddin, G. S. (2017). Information diffusion, cluster formation and entropy-based network dynamics in equity and commodity markets. European Journal of Operational Research, 256(3), 945–961. https://doi.org/10.1016/j.ejor.2016.06.052