Название статьи:
Вязкий гравитационный алгоритм кластеризации многомерных данных
Авторы: Головинский П.А., доктор физизико-математических наук, профессор кафедры инноватики и строительной физики им. И.С. Суровцева, Воронежский государственный технический университет, г. Воронеж, Российская Федерация,
golovinski@bk.ru,
Тарасова А.С., аспирант кафедры инноватики и строительной физики им. И.С. Суровцева, Воронежский государственный технический университет, г. Воронеж, Российская Федерация,
anna222tarasova@yandex.ru В рубрике:
ТЕХНИЧЕСКИЕ НАУКИ
Год: 2023 Том: 5 Номер журнала: 4
Страницы: 379-391
Тип статьи: Научная статья
УДК: 004.8
DOI: 10.17150/2713-1734.2023.5(4).379-391
Аннотация:
Кластеризация является одним из первых стандартных шагов при анализе больших данных. Она необходима для дальнейшего решения задач классификации и группового прогноза. Нами исследуется вязкая модификация гравитационного алгоритма кластеризации данных (VGSA), которая является развитием уже зарекомендовавшего себя ранее подхода. Отдельные записи данных рассматриваются в VGSA как точки в многомерном пространстве, между которыми действует парное центральное притяжение. Массы взаимодействующих точек приняты одинаковыми, что соответствует специфике кластеризации в отличие от задачи поиска оптимального значения целевой функции, при решении которой массы частиц увеличиваются по мере приближения к экстремуму. Обсуждается выбор вида парного взаимодействия в зависимости от предполагаемой структуры данных. Наличие большой вязкости понижает порядок динамических уравнений движения путем исключения из них ускорения. Полученные укороченные уравнения задают устойчивое движение системы, что гарантирует воспроизведение результатов при повторном запуске алгоритма. Устойчивость системы уравнений доказывается с помощью функции Ляпунова, являющейся аналогом физической потенциальной энергии. Выключение взаимодействия частиц на малых расстояний между ними обеспечивает автоматический механизм иерархической кластеризации на разных временах работы алгоритма с конечным образованием единого кластера. Прослежена связь VGSA с принципом действия самоорганизующихся карт Кохонена, который соответствует гравитационному перераспределению пробных частиц. Работа алгоритма протестирована на базе данных в сравнении с методами кластеризации K-средних, карт Кохонена и стандартного гравитационного алгоритма. Оценивалась скорость и точность кластеризации. Сделан вывод о преимуществе применения VGSA к большим данным с учетом автоматического определения числа кластеров, возможности коррекции при обновлении записей и неточного задания данных.
Ключевые слова: кластеризация, большие данные, гравитационный алгоритм, вязкость, устойчивость по Ляпунову
Список цитируемой литературы: - Suárez J.L. A Tutorial on Distance Metric Learning: Mathematical Foundations, Algorithms, Experimental Analysis, Prospects and Challenges / J.L. Suárez, S. García, F. Herrera. - DOI 10.1016/j.neucom.2020.08.017 // Neurocomputing. - 2021. - Vol. 425. - P. 300-322.
- Жерон О. Прикладное машинное обучение с помощью Scikit-Learn и TensorFlow / О. Жерон. - Санкт-Петербург : Диалектика, 2020. - 690 с.
- Dawani J. Hands-On Mathematics for Deep Learning: Build a Solid Mathematical Foundation for Training Efficient Deep Neural Networks / J. Dawani. - Birmingham : Packt Publishing, 2020. - 364 p.
- A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects / A.E. Ezugwu, A.M. Ikotun, O.O. Oyelade [at al.]. - DOI 10.1016/j.engappai.2022.104743 // Engineering Applications of Artificial Intelligence. - 2022. - Vol. 110. - P. 104743.
- Data Clustering. Algorithms and Applications / ed. C.C. Aggarwal, Ch.K. Reddy. - New York : CRC Press, 2014. - 652 p.
- Воронов К.В. Лекции по алгоритмам кластеризации и многомерного шкалирования / К.В. Воронов. - Москва, 2007. - URL: https://knigogid.ru/books/1780564-lekcii-po-algoritmam-klasterizacii-i-mnogomernogo-shkalirovaniya/toread.
- Corne D. Evolutionary Clustering / D. Corne, J. Handl, J. Knowles // Encyclopedia of Machine Learning / ed. C. Sammut, G.I. Webb. - Boston : Springer, 2011. - P. 332-337.
- Binder P. Gravitational Clustering: A simple, robust and adaptive approach for distributed networks / P. Binder, M. Muma, A.M. Zoubir. - DOI 10.1016/j.sigpro.2018.02.034 // Signal Processing. - 2018. - Vol. 149. - P. 36-48.
- Головинский П.А. Вязкий гравитационный алгоритм кластеризации неточных данных / П.А. Головинский. - DOI 10.17308/sait.2022.1/9203 // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. - 2022. - № 1. - C. 79-89.
- Саймон Д. Алгоритмы эволюционной оптимизации / Д. Саймон. - Москва : ДМК Пресс, 2020. - 1002 с.
- Hybridized Particle Swarm-Gravitational Search Algorithm for Process Optimization / R. Shankar, N. Ganesh, R. Čep [et. al.]. - DOI 10.3390/pr10030616 // Processes. - 2022. - Vol. 10, iss. 3. - P. 616.
- Кохонен Т. Самоорганизующиеся карты / Т. Кохонен. - Москва : Бином Лаборатория знаний, 2017. - 655 с.
- Халил Х.К. Нелинейные системы / Х.К. Халил. - Москва, 2009. - 829 с.
- Sushkov A. Машинное обучение: от Ирисов до Телекома / A. Sushkov // Хабр. - 2017. - 23 авг. - URL: https://habr.com/ru/companies/billing/articles/334738/.
- Khotijah S. K-Means Clustering of Iris Dataset / S. Khotijah // Kaggle. - URL: https://www.kaggle.com/code/khotijahs1/k-means-clustering-of-iris-dataset.
- Ahangama I. U Matrix of SOM for Iris Dataset / I. Ahangama // Kaggle. - URL: https://www.kaggle.com/code/imanthaahangama/u-matrix-of-som-for-iris-dataset#5-Vector-Field-for-SOM-Generated-in-Section-4.
- Dhawale C.A. Current Trends in Deep Learning Frameworks with Opportunities and Future Prospectus / C.A. Dhawale, K. Dhawale. - DOI 10.4018/978-1-7998-1159-6.ch003 // Neural Networks for Natural Language Processing / ed. S. Sumathi, M. Janani. - IGI Global, 2020. - P. 63-77.
- A novel data clustering algorithm based on modified gravitational search algorithm / XiaoHong Han, Long Quan, XiaoYan Xiong [et al.]. - DOI 10.1016/j.engappai.2016.11.003 // Engineering Applications of Artificial Intelligence. - 2017. - Vol. 61. - P. 1-7.