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

Partitioning Around Medoids
Последовательный алгоритм
Последовательная сложность	[math]O(T*K*N^2)[/math]
Объём входных данных	[math] N*(N-1)/2 + 2 [/math]
Объём выходных данных	[math] N [/math]

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

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

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

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

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

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

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     вернуть М

1.6 Последовательная сложность алгоритма

Обозначим количество кластеров как [math]K[/math], количество объектов как [math]N[/math], число итераций алгоритма как [math]T[/math].

На стадии BUILD каждый шаг нахождения очередного метоида имеет сложность [math]O(N^2)[/math] по количеству операций сложения вещественных чисел и по количеству операций сравнения двух вещественных чисел.
Тогда стадия BUILD имеет сложность [math]O(K*N^2)[/math]

На стадии SWAP вычисление целевой функции имеет сложность [math]O(K*N^2)[/math] по количеству операций сложения вещественных чисел и по количеству операций сравнения двух вещественных чисел.

Таким образом алгоритм PAN имеет сложность [math]O(T*K*N^2)[/math]

1.9 Входные и выходные данные алгоритма

Входные данные:

• число [math]K[/math] - количество кластеров;
• число [math]N[/math] - количество объектов;
• вектор попарных расстояний, имеющий длину [math]N*(N-1)/2[/math], из данных чисел однозначно восстанавливается симметрическая матрица расстояний [math]D[/math]

Объём входных данных: [math]N*(N-1)/2[/math] вещественное число и [math]2[/math] целых числа.