Страница публикации

K-Means Clustering via a Nonconvex Optimization Approach

Авторы: Gruzdeva T.V., Ushakov A.V.

Журнал: Lecture Notes in Computer Science: 20th Intern. Conf. on Mathematical Optimization Theory and Operations Research, MOTOR 2021 (Irkutsk, 5-10 July 2021)

Том: 12755


Год: 2021

Отчётный год: 2021


Местоположение издательства:


Аннотация: Clustering is one of the basic tasks in machine learning and data mining. Euclidean minimum-sum-of-squares clustering problem is probably the most common clustering model. It consists in finding k cluster centers or representatives so as the sum of squared Euclidean distances from a set of points and their closest centers is minimized. The problem is known to be nonconvex and NP-hard even in the planner case. In this paper, we propose a new DC programming approach to the problem. First, we cast the original nonconvex problem as a continuous optimization problem with the objective function represented as a DC function. We then devise a solution algorithm, resting upon the global optimality conditions and global search scheme for DC minimization problems proposed by A.S. Strekalovsky. We implement the developed algorithm and compare it with k-means clustering algorithms on generated datasets.

Индексируется WOS: 1

Индексируется Scopus: 1

Индексируется РИНЦ: 1

Публикация в печати: 0

Добавил в систему: