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

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)

Язык публикации: english

Серия книг: IEEE

Номера страниц: 1116-1120

Количество страниц: 5

Год публикации: 2019

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

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: Нет