Методы локального и глобального поисков для задачи k-means (k-средних) (2021 год)

Исследована так называемая задача о k-средних, являющаяся одной из базовых моделей кластеризации, которая основанна на поиске центров кластеров (center-based clustering) и представляет собой невыпуклую оптимизационную задачу. Один из наиболее известных современных алгоритмов кластеризации, алгоритм поиска k-средних, в общем случае является только лишь алгоритмом локального поиска в указанной задаче кластеризации. Для задачи о k-средних предложена новая формулировка в виде задачи минимизации d.c. функции (т.е. представимой в виде разности двух выпуклых функций) над пересечением m канонических симплексов, где m – заданное число элементов данных, которые необходимо разбить на кластеры. Для этой задачи разработан алгоритм поиска решений, основанный на Теории глобального поиска А.С. Стрекаловского. Проведено тестирование разработанного алгоритма кластеризации, а также его сравнение с наиболее популярными вариантами реализации алгоритма k-средних: алгоритмом Ллойда и k-means++. Разработанный алгоритм во многих случаях позволил найти лучшие разбиения на кластеры в сравнении с указанными популярными алгоритмами, что подтверждено с помощью, так называемых внешних оценок качества кластеризации.

Рис. Пример кластеризации изображений лиц (изображения из разных кластеров помечены рамками разных цветов)

Авторы: к.ф.-м.н. Т.В. Груздева, к.ф.-м.н. А.В. Ушаков

Наиболее значимые публикации:

1. Gruzdeva T.V., Ushakov A.V. K-Means Clustering via a Nonconvex Optimization Approach // Lecture Notes in Computer Science: 20th Intern. Conf. on Mathematical Optimization Theory and Operations Research, MOTOR 2021 (Irkutsk, 5-10 July 2021). 2021. Vol. 12755. pp. 462-476. DOI: 10.1007/978-3-030-77876-7_31. (Web of Science Q4)
2. Gruzdeva T.V., Ushakov A. V. A Computational Study of the DC Minimization Global Optimality Conditions Applied to K-Means Clustering / N.N. Olenev et al. (Eds.) // Lecture Notes in Computer Science: OPTIMA 2021. 2021. Vol. 13078. pp. 79-93. DOI: 10.1007/978-3-030-91059-4_6. (Web of Science Q4)