Участник:Denemmy/Partitioning Around Medoids (Алгоритм): различия между версиями
Denemmy (обсуждение | вклад) |
Denemmy (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
''Входные данные'': | '''Входные данные''': | ||
* число <math>K</math> - количество кластеров; | * число <math>K</math> - количество кластеров; | ||
* число <math>N</math> - количество объектов; | * число <math>N</math> - количество объектов; | ||
* вектор попарных расстояний, имеющий длину <math>N*(N-1)/2</math>, из данных чисел однозначно восстанавливается симметрическая матрица расстояний <math>D</math> | * вектор попарных расстояний, имеющий длину <math>N*(N-1)/2</math>, из данных чисел однозначно восстанавливается симметрическая матрица расстояний <math>D</math> | ||
''Объём входных данных'': <math>N*(N-1)/2</math> вещественное число и <math>2</math> целых числа. | '''Объём входных данных''': <math>N*(N-1)/2</math> вещественное число и <math>2</math> целых числа. | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия от 09:57, 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]
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Входные данные:
* число [math]\displaystyle{ K }[/math] - количество кластеров; * число [math]\displaystyle{ N }[/math] - количество объектов; * вектор попарных расстояний, имеющий длину [math]\displaystyle{ N*(N-1)/2 }[/math], из данных чисел однозначно восстанавливается симметрическая матрица расстояний [math]\displaystyle{ D }[/math]
Объём входных данных: [math]\displaystyle{ N*(N-1)/2 }[/math] вещественное число и [math]\displaystyle{ 2 }[/math] целых числа.