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

A parallel heuristic for a k-medoids clustering problem with unfixed number of clusters

Авторы: Ushakov A.V., Vasilyev I.L.

Журнал: IEEE: Proc. 42nd Intern. Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)



Год: 2019

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


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


Аннотация: The k-medoids clustering model is a well-known NP-hard optimization problem which a number of widely-used clustering algorithms are based on. In the original k-medoids problem, the number of clusters k is an input parameter that must be defined before actual clustering. We address a modification of the k-medoids problem where the number of clusters is not pre-specified. Instead, it is a decision variable bounded by a monotonically increasing nonlinear function of k added to the k-medoids objective function. We propose an effective hybrid heuristic algorithm for the modified k-medoids problem and its shared memory parallel implementation. Our approach is rested upon the approximation of dissimilarity matrix via nearest neighbors, dual search, and a sophisticated variable fixing technique. The main advantage of our algorithm is that it provides a dual bound for the objective value, thus allowing one to ascertain the optimality of a solution found. We present computational results on large-scale problem instances with millions of decision variables.

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

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

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

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

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