Application of Algorithms with Variable Greedy Heuristics for k-Medoids Problems | Научно-инновационный портал СФУ

## Application of Algorithms with Variable Greedy Heuristics for k-Medoids Problems

Тип публикации: статья из журнала

Год издания: 2020

Идентификатор DOI: 10.31449/inf.v44i1.2737

Ключевые слова: clustering algorithms, VNS, k-medoids, greedy heuristic method

Аннотация: Progress in location theory methods and clustering algorithms is mainly targeted at improving the performance of the algorithms. The most popular clustering models are based on solving the p-median and similar location problems (k-means, k-medoids). In such problems, the algorithm must find several points called cluster centers, centroids, medoids, depending on the specific problem which minimize some function of distances from known objects to the centers. In the the k-medoids problem, the centers (medoids) of the cluster must coincide with one of the clustered objects. The problem is NP-hard, and the efforts of researchers are focused on the development of compromise heuristic algorithms that provide a fairly quick solution with minimal error. In this paper, we propose new algorithms of the Greedy Heuristic Method which use the idea of the Variable Neighborhood Search (VNS) algorithms for solving the k-medoids problem (which is also called the discrete p-median problem). In addition to the known PAM (Partition Around Medoids) algorithm, neighborhoods of a known solution are formed by applying greedy agglomerative heuristic procedures. According to the results of computational experiments, the new search algorithms (Greedy PAM-VNS) give more accurate and stable results (lower average value of the objective function and its standard deviation, smaller spread) in comparison with known algorithms on various data sets. Progress in location theory methods and clustering algorithms is mainly targeted at improving the performance of the algorithms. The most popular clustering models are based on solving the p-median and similar location problems (k-means, k-medoids). In such problems, the algorithm must find several points called cluster centers, centroids, medoids, depending on the specific problem which minimize some function of distances from known objects to the centers. In the the k-medoids problem, the centers (medoids) of the cluster must coincide with one of the clustered objects. The problem is NP-hard, and the efforts of researchers are focused on the development of compromise heuristic algorithms that provide a fairly quick solution with minimal error. In this paper, we propose new algorithms of the Greedy Heuristic Method which use the idea of the Variable Neighborhood Search (VNS) algorithms for solving the k-medoids problem (which is also called the discrete p-median problem). In addition to the known PAM (Partition Around Medoids) algorithm, neighborhoods of a known solution are formed by applying greedy agglomerative heuristic procedures. According to the results of computational experiments, the new search algorithms (Greedy PAM-VNS) give more accurate and stable results (lower average value of the objective function and its standard deviation, smaller spread) in comparison with known algorithms on various data sets. © 2020 Slovene Society Informatika. All rights reserved.

#### Издание

Журнал: INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS

Выпуск журнала: Vol. 44, Is. 1

Номера страниц: 55-61

ISSN журнала: 03505596

Место издания: LJUBLJANA

Издатель: SLOVENSKO DRUSTVO INFORMATIKA

#### Авторы

• Kazakovtsev Lev (Reshetnev Siberian State Univ Sci & Technol, Prosp Krasnoyarskiy Rabochiy 31, Krasnoyarsk 660031, Russia)
• Rozhnov Ivan (Siberian Fed Univ, Krasnoyarsk 660041, Russia)

#### Вхождение в базы данных

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.

Вы можете отметить интересные фрагменты текста, которые будут доступны по уникальной ссылке в адресной строке браузера.