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)
Отчётный год: 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
Добавил в систему: