Вязкий гравитационный алгоритм кластеризации неточных данных

Павел Абрамович Головинский

doi:10.17308/sait.2022.1/9203

Павел Абрамович Головинский Воронежский государственный технический университет https://orcid.org/0000-0002-7527-0297

DOI: https://doi.org/10.17308/sait.2022.1/9203

Ключевые слова: кластеризация данных, неточные данные, гравитационный алгоритм, вязкость, отталкивание Паули

Аннотация

Кластеризация является одной из базовых задач машинного обучения, наряду с распознаванием образов, классификацией и прогнозированием. Особенно существенна роль кластеризации в анализе больших данных, работа с которыми может быть эффективной только с использованием компьютерных технологий. При этом, задача автоматического разбиения на кластеры с учетом погрешностей исходных данных не получила однозначного решения и требует поиска более адекватных подходов, включающих автоматическое определение числа кластеров. В работе предложен новый метод кластеризации данных, основанный на модификации гравитационного алгоритма, использующего аналогию с формированием звездных кластеров за счет притяжения масс в соответствии с законом всемирного тяготения. При применении такого подхода к кластеризации данных реальные физические массы заменяются точками в многомерном пространстве данных, а движение этих точек с учетом их притяжения приводит к формированию кластеров. Недостатком такого способа является проявление эффектов инерции, которые могут затруднять процесс завершения кластеризации и приводить к выбросу ускоренных частиц из кластера на стадии его формирования. Для исключения таких нежелательных событий в работе используется модель динамики вязкого движения частиц, представляющих данные, и естественное ограничение размеров кластеров за счет отталкивания частиц. Силы отталкивания частиц взяты в виде обменного взаимодействия Паули для фермионов при гауссовом распределении плотностей погрешностей. Записаны основные уравнения, описывающие работу представленной модификации гравитационного алгоритма. На численном примере продемонстрированы особенности и преимущества вязкого гравитационного алгоритма в сравнении с методом k-средних и основанном на плотностях методом DBSCAN, включая автоматическую остановку процедуры при завершении процесса кластеризации. Полученные результаты позволяют проводить слепую кластеризацию больших данных и допускают обобщение на решение задач многомерной оптимизации.

Скачивания

Данные скачивания пока не доступны.

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

Павел Абрамович Головинский, Воронежский государственный технический университет

д-р физ.-мат. наук, профессор кафедры инноватики и строительной физики им. И. С. Суровцева Воронежского государственного технического университета

Литература

1. Evans R., Pfahringer B. and Holmes G. (2011) Clustering for classification. 2011 7th International Conference on Information Technology in Asia. Kuching, Sarawak. P. 1–8.
2. Shirkhorshidi A. S., Aghabozorgi S., Wah T. Y. and Herawan T. (2014) Big Data clustering: A review. In: Murgante B. et al. (eds) Computational Science and Its Applications – ICCSA 2014. Lecture Notes in Computer Science. Springer, Cham. 8583. P. 707–720.
3. Ge M., Bangui H. and Buhnova B. (2018) Big Data for Internet of Things: A Survey. Future Generation Computer Systems. 87. P. 601–614.
4. Xu Rui and Wunsch D. (2005) Survey of clustering algorithms. IEEE Transactions on Neural Networks. 16(3). P. 645–678.
5. Xu D. and Tian Y. (2015) A Comprehensive survey of clustering algorithms. Ann. Data. Sci. 2. P. 165–193.
6. Jain A. K. (2010) Data clustering: 50 years beyond K-means. Pattern Recognition Letters. 31(8). P. 651–666.
7. Lemke O. and Keller B. G. (2016) Density-based cluster algorithms for the identification of core sets. J. Chem. Phys. 145(16). P. 164104(14).
8. Lee K. M., Lee S. Y. [et al] (2017) Density and frequency-aware cluster identification for spatio-temporal sequence data. Wireless Pers. Commun. 93. P. 47–65.
9. Wright W. E. (1977) Gravitational clustering. Pattern Recognition. 9. P. 151–166.
10. Gorbonos D., van der Vaart K., Sinhuber M., Puckett J. G., Reynolds A. M., Ouellette N. T. and Gov N. S. (2020) Similarities between insect swarms and isothermal globular clusters. Phys. Rev. Research. 2. P. 013271(5).
11. Fazliana Abdul Kadir A., Mohamed A., Shareef H., Asrul Ibrahim A., Khatib T. and Elmenreich W. (2014) An improved gravitational search algorithm for optimal placement and sizing of renewable distributed generation units in a distribution system for power quality enhancement. Journal of Renewable and Sustainable Energy. 6(3). P. 033112(17).
12. Mahdad B. and Srairi K. (2014) Interactive gravitational search algorithm and pattern search algorithms for practical dynamic economic dispatch. International Transactions on Electrical Energy Systems. 25(10). P. 2289–2309.
13. Kou Z. (2019) Association rule mining using chaotic gravitational search algorithm for discovering relations between manufacturing system capabilities and product features. Concurrent Engineering. 27(3). P. 213– 232.
14. Huang M.-L. and Chou Y.-C. (2019) Combining a gravitational search algorithm, particle swarm optimization, and fuzzy rules to improve the classification performance of a feed-forward neural network. Computer Methods and Programs in Biomedicine. 180. P. – 105016(12).
15. Siddique N. and Adeli H. (2016) Applications of gravitational search algorithm in engineering / Journal of Civil Engineering and Management. 22(8). P. 981–990.
16. Ali A. F. and Tawhid M. A. (2016) Direct gravitational search algorithm for global optimisation problems. East Asian Journal on Applied Mathematics. 6(03). P. 290–313.
17. Koay Y. Y., Tan J. D., Lim C. W., Koh S. P., Tiong S. K. and Ali K. (2019) An adaptive gravitational search algorithm for global optimization. Indonesian Journal of Electrical Engineering and Computer Science. 16(2). P. 724–729.
18. Zhang A., Sun G., Wang Z. and Yao Y. (2015) A hybrid genetic algorithm and gravitational search algorithm for global optimization. Neural Network World. 25(1). P. 53–73
19. Rashedi E., Rashedi E. and Nezamabadi-pour H. (2018) A comprehensive survey on gravitational search algorithm. Swarm and Evolutionary Computation. 41. P. 141–158.
20. Xiaobing Y., Xianrui Y. and Hong C. (2019) An improved gravitational search algorithm for global optimization. J. Intell. Fuzzy Syst. 37. P. 50395047.
21. Vasile M., Martin J. M. R., Masi L., Minisci E., Epenoy R., Martinot V. and Baig J. F. (2015) Incremental planning of multi-gravity assist trajectories. Acta Astronautica. 115. P. 407–421.
22. Binder P., Muma M. and Zoubir A. M. (2018) Gravitational clustering: A simple, robust and adaptive approach for distributed networks. Signal Processing. 149. P. 36–48.
23. Rashedi E., Nezamabadi-pour H. and Saryazdi S. (2009) GSA: A gravitational search algorithm. Information Sciences. 179(13). P. 2232–2248.
24. Sabri N. M., Puth M. and Mahmood M. (2013) R. A review of gravitational search algorithm. Int. J. Advance. Soft. Comp. Appl. 5. (3). P. 1–39.
25. Bala I. and Yadav A. (2019) Gravitational search algorithm: A state-of-the-art review. In: Yadav N., Yadav A., Bansal J., Deep K., Kim J. (eds) Harmony Search and Nature Inspired Optimization Algorithms. Advances in Intelligent Systems and Computing. Springer, Singapore. 741. P. 27–37.
26. Gauci M., Dodd T. J. and Groß R. (2012) Why ‘CSA: a gravitational search algorithm’ is not genuinely based on the law of gravity. Nat. Comput. 11. P. 719–720.
27. Alswaitti M., Ishak M. K. and Isa N. A. M. (2018) Optimized gravitational-based data clustering algorithm. Engineering Applications of Artificial Intelligence. 73. P. 126–148.
28. Gomez J., Leon E., Nasraoui O. and Giraldo F. (2014) The Parameter-less Randomized Gravitational Clustering algorithm with online clusters’ structure characterization. Prog. Artif. Intell. 2. P. 217–236.
29. Han X., Quan L., Xiong X., Almeter M., Xiang J. and Lan Y. (2017) A novel data clustering algorithm based on modified gravitational search algorithm. Engineering Applications of Artificial Intelligence. 61. P. 1–7.
30. Rashedi E. and Nezamabadi-pour H. (2018) A comprehensive survey on gravitational search algorithm. Swarm and Evolutionary Computation. 41. P. 141–158.
31. Mustafa H. M. J., Ayob M., Nazri M. Z. A. and Kendall G. (2019) An improved adaptive memetic differential evolution optimization algorithms for data clustering problems. PLOS ONE. 4(5). P. e0216906(28).
32. Slamet M. and Sahni V. (1992) Rigorous and unifying physical interpretation of the exchange potential and energy in the local-density approximation. Phys. Rev. B. 45(8). P. 4013–4019
33. Sander J., Ester M., Kriegel HP. and Xu X. (1998) Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications. Data Mining and Knowledge Discovery. 2. P. 169–194.
34. Rodriguez A. and Laio A. (2014) Clustering by fast search and find of density peaks. Science. 344(6191). P. 1492–1496.
35. Mahmoudi S. M., Aghaie M., Bahonar M. and Poursalehi N. (2016) A novel optimization method, Gravitational Search Algorithm (GSA), for PWR core optimization. Annals of Nuclear Energy. 95. P. 23–34.