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

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:

Аннотация: 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: 1

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

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

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

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