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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 63: Строка 63:
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 +
<p><b>[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']]</b></p>
 +
Вычислительная мощность алгоритма <i>k means</i> равна <math>\frac{K*N^2*\Tau}{N^2} = K*\Tau </math>, где <math>K</math> &ndash; число кластеров, <math>\Tau</math> &ndash; число итераций алгоритма.
 +
 +
<p><b>[[глоссарий#Детерминированность |''Детерминированность'']] и [[глоссарий#Устойчивость |''Устойчивость'']] </b></p>
 +
Алгоритм <i>PAM</i> является итерационным, количество итераций может быть ограничено сверху, однако в общем случае не фиксируется. Из-за недетермирированности выбора элементов, на которых достигается минимум целевой функции, алгоритм не является <b>детермирированным</b>. Однако, данный алгоритм является <b>устойчивым</b>, поскольку не накапливает ошибки в процессе своей работы.
 +
 +
<b>Сильные стороны алгоритма</b>:
 +
<ul> 
 +
  <li><i>Меньшая чувствительность к выбросам, чем k-means</i></li>
 +
  <li><i>Сравнительно высокая эффективность при простоте реализации</i></li>
 +
  <li>
 +
    <p><i>Возможность распараллеливания</i></p>
 +
    <p>Однако равномерная загрузка процессоров не всегда возможна.</p>
 +
  </li>
 +
</ul>
 +
<b>Недостатки алгоритма</b>:
 +
<ul>
 +
  <li><i>Квадратичная сложность алгоритма</i></li>
 +
  <li>
 +
    <p><i>Количество кластеров является параметром алгоритма</i></p>
 +
    <p>Во многих задачах число кластеров может быть неизвестным.</p>
 +
  </li>
 +
  <li>
 +
    <p><i>Возможность сходимости к локальному оптимуму</i></p>
 +
    <p>Оптимальное решение не гарантировано.</p>
 +
  </li>
 +
</ul>
 +
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===

Версия 13:29, 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] целых числа.

Выходные данные:

* 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 Существующие реализации алгоритма

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

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

3 Литература