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, ceПоказать полностьюntroids, 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.

Ссылки на полный текст



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

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

ISSN журнала: 03505596

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



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