Участник:Denemmy/Partitioning Around Medoids (Алгоритм): различия между версиями
Denemmy (обсуждение | вклад) |
Denemmy (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
* вектор попарных расстояний, имеющий длину <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> целых числа. | ||
| + | |||
''Выходные данные'': | ''Выходные данные'': | ||
* K чисел <math>m_1, m_2, ..., m_K</math> - индексы объектов соответствующие метоидам; | * K чисел <math>m_1, m_2, ..., m_K</math> - индексы объектов соответствующие метоидам; | ||
| − | * N чисел <math>k_1, k_2, ..., | + | * N чисел <math>k_1, k_2, ..., k_(N-K)</math> - номера кластеров для каждого объекта (кроме тех, что являются метоидами); |
| + | ''Объём выходных данных'': <math>N</math> целых чисел. | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 13:02, 15 октября 2016
| Partitioning Around Medoids | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(T*K*N^2)[/math] |
| Объём входных данных | [math] N*(N-1)/2 + 2 [/math] |
| Объём выходных данных | [math] N [/math] |
Авторы: Галеев Д.Ф, Запутляев И.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
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.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
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] целых числа.
Выходные данные:
* K чисел [math]m_1, m_2, ..., m_K[/math] - индексы объектов соответствующие метоидам; * N чисел [math]k_1, k_2, ..., k_(N-K)[/math] - номера кластеров для каждого объекта (кроме тех, что являются метоидами);
Объём выходных данных: [math]N[/math] целых чисел.
