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

A Computational Study of the DC Minimization Global Optimality Conditions Applied to K-Means Clustering

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

Журнал: Lecture Notes in Computer Science: 12th International Conference Optimization and Applications (OPTIMA 2021, Petrovac, Montenegro, September 27 – October 1, 2021)

Том: 13078

Номер:

Год: 2021

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

Издательство:

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

URL:

Проекты:

DOI: 10.1007/978-3-030-91059-4_6

Аннотация: Clustering is traditionally one of the basic tools of data analysis widely applied in diverse fields. By now, one of the most common clustering models is the Euclidean minimum-sum-of-squares clustering problem (MSSC). Consequently, Lloyd’s algorithm, often referred to as k-means, is probably the most popular clustering algorithm. Despite its popularity, Lloyd’s algorithm is a local search heuristic for MSSC that in general converges to local optima only. In this paper, we aim at enhancing k-means by employing the global optimality conditions for MSSC represented as a problem with DC (difference of convex) functions. We then embed the k-means algorithm into the so-called global search framework for DC minimization problems where it is employed to find local optimal solutions. We tested such an improved implementation of k-means in a series of computation experiments on well-known test library of medium-size datasets and compared it with the conventional k-means and k-means++ algorithms.

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

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

Индексируется УБС: Нет

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

Индексируется ВАК: Нет

Индексируется CORE: Нет

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