Участник:Denemmy/Partitioning Around Medoids (Алгоритм): различия между версиями
Перейти к навигации
Перейти к поиску
Denemmy (обсуждение | вклад) |
Denemmy (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
=== Последовательная сложность алгоритма=== | === Последовательная сложность алгоритма=== | ||
Обозначим количество кластеров как <math>K</math>, а количество объектов как <math>N</math>.<br> | |||
Тогда стадия '''BUILD''' будет требовать <math>K*N^2</math> | |||
=== Информационный граф === | === Информационный граф === | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
Версия от 08:57, 15 октября 2016
Авторы: Галеев Д.Ф, Запутляев И.
Свойства и структура алгоритма
Общее описание алгоритма
Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
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 вернуть М
Последовательная сложность алгоритма
Обозначим количество кластеров как [math]\displaystyle{ K }[/math], а количество объектов как [math]\displaystyle{ N }[/math].
Тогда стадия BUILD будет требовать [math]\displaystyle{ K*N^2 }[/math]