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