Уровень алгоритма

Участник:Denemmy/Partitioning Around Medoids (Алгоритм): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 52: Строка 52:
  
 
''Входные данные'':
 
''Входные данные'':
* число <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> целых числа.
  

Версия 12:57, 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 Общее описание алгоритма

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
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] целых числа.

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

2.7.1 Открытое программное обеспечение

2.7.2 Проприетарное программное обеспечение

3 Литература