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