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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 50: Строка 50:
  
 
'''Фаза BUILD'''
 
'''Фаза BUILD'''
<p>Общий вид информационного графа для шага t представлен на рисунке 1:
+
 
 +
Общий вид информационного графа для шага t представлен на рисунке 1:
  
 
[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]
 
[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]
Строка 62: Строка 63:
 
</ul>
 
</ul>
 
Количество шагов t равно <b>K</b>, где <b>K</b> - число кластеров
 
Количество шагов t равно <b>K</b>, где <b>K</b> - число кластеров
 +
 +
'''Фаза SWAP'''
 +
 +
Общий вид информационного графа для итерации t представлен на рисунке 2:
 +
 +
[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]
 +
 +
''Операции''
 +
<ul>
 +
  <li><b>Update<math>_M</math></b> и <b>Update<math>_L</math></b> - операции обновления множества метоидов и не-метоидов соответственно</li>
 +
  <li><b>SUM</b> - вычисление целевой функции</li>
 +
  <li><b>MIN</b> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
 +
</ul>
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===

Версия 16:09, 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 Информационный граф

Фаза BUILD

Общий вид информационного графа для шага t представлен на рисунке 1:

Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.

Операции

  • Update[math]_M[/math] и Update[math]_L[/math] - операции обновления множества метоидов и не-метоидов соответственно
  • SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин
  • MIN[math]_s[/math] - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение
  • MIN[math]_d[/math] - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM

Количество шагов t равно K, где K - число кластеров

Фаза SWAP

Общий вид информационного графа для итерации t представлен на рисунке 2:

Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.

Операции

  • Update[math]_M[/math] и Update[math]_L[/math] - операции обновления множества метоидов и не-метоидов соответственно
  • SUM - вычисление целевой функции
  • MIN - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение

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-K чисел [math]k_1, k_2, ..., k_{N-K}[/math] - номера кластеров для каждого объекта (кроме тех, что являются метоидами);

Объём выходных данных: [math]N[/math] целых чисел.

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

Вычислительная мощность

Вычислительная мощность алгоритма k means равна [math]\frac{K*N^2*\Tau}{N^2} = K*\Tau [/math], где [math]K[/math] – число кластеров, [math]\Tau[/math] – число итераций алгоритма.

Детерминированность и Устойчивость

Алгоритм PAM является итерационным, количество итераций может быть ограничено сверху, однако в общем случае не фиксируется. Из-за недетермирированности выбора элементов, на которых достигается минимум целевой функции, алгоритм не является детермирированным. Однако, данный алгоритм является устойчивым, поскольку не накапливает ошибки в процессе своей работы.

Сильные стороны алгоритма:

  • Меньшая чувствительность к выбросам, чем k-means
  • Несложность реализации
  • Возможность распараллеливания

    Однако равномерная загрузка процессоров не всегда возможна.

Недостатки алгоритма:

  • Квадратичная сложность алгоритма
  • Количество кластеров является параметром алгоритма

    Во многих задачах число кластеров может быть неизвестным.

  • Возможность сходимости к локальному оптимуму

    Оптимальное решение не гарантировано.

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

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

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

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

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

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

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

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

  1. ELKI реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java
  2. Java-ML. Включает реализацию k-metoid. Написан на Java
  3. Julia содержит реализацию k-metoid в пакете для кластеризации JuliaStats
  4. R включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster
  5. MATLAB. Реализованы PAM, CLARA и другие алгоритмы кластеризации

3 Литература