Тип публикации: статья из журнала
Год издания: 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.
Журнал: INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS
Выпуск журнала: Vol. 44, Is. 1
Номера страниц: 55-61
ISSN журнала: 03505596
Место издания: LJUBLJANA
Издатель: SLOVENSKO DRUSTVO INFORMATIKA