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

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

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

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

URL:

Проекты:

DOI: 10.23919/MIPRO.2019.8756919

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

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

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

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

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

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

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