Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

Авторы: Галеев Д.Ф, Запутляев И.

Свойства и структура алгоритма

Общее описание алгоритма

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

Схема реализации последовательного алгоритма

Псевдокод алгоритма:

1  функция PAM(D, k, tmax=100):
2      # D - матрица расстояний, k - число кластеров, tmax - маскимальное число итераций
3      выполнить фазу BUILD, получить множество метоидов M и множество не-метоидов L
4      вычислить значение целевой функции F
5      для t = 0..tmax-1:
6          выполнить фазу SWAP, вычислить значение целевой функции F'
7          delta = F' - F
8          если delta > 0:
9              обновить множества M и L
10             F = F'
11         иначе:
12             выйти из цикла
13     вернуть М