дз 1. PAM (Partitioning Around Medoids) (Практикум), страница 6

:<math>O(kn)</math> против <math>O(kn^2).</math>

Соотношение количества сложений и взятий минимума для фазы BUILD является постоянным и стремится к <math>3,</math> при <math>k, n \to \infty.</math>

Максимальная ширина яруса достигается при вычислении <math>\overline {c}</math> и <math>S</math> и равна <math>n-It+1</math> для шага <math>It</math> фазы BUILD. Максимальная ширина яруса при рассмотрении всей фазы есть <math>n</math> и достигается на первом шаге.

==== Ресурс параллелизма фазы SWAP ====

Для решения задачи кластеризации методом PAM в параллельном варианте фазы SWAP в предположении доступности неограниченного числа процессов для одной итерации необходимо выполнить:

* 1 ярус с нахождением <math>\overline {a}:</math>

** <math>n(k-1)</math> операций нахождения минимального из двух элементов;

* 1 ярус с нахождением <math>\overline {b}:</math>

** <math>n</math> операций нахождения минимального из двух элементов;

* 1 ярус с нахождением суммы <math>S</math>:

** <math>n-1</math> операцию сложения;

* 1 ярус с нахождением минимального элемента 'первого' вида <math>(M1 = \min_{x_{o_p} \in O} S):</math>

** <math>n-k-1</math> операцию нахождения минимального из двух элементов;

* 1 ярус с нахождением минимального элемента 'второго' вида <math>(M2 = \min_{x_{m_i} \in M} M1):</math>

** <math>k-1</math> операцию нахождения минимального из двух элементов;

* 1 ярус с изменением множеств медоидов и не-медоидов (не выполняются операции рассматриваемых типов).

Таким образом, параллельная сложность одной итерации фазы SWAP равна:

* <math>n-1</math> - по количеству операций сложения;

* <math>kn + n - 2</math> - по количеству операций нахождений минимума для двух чисел.

В параллельном варианте, по сравнению с последовательным, при <math>k, n \to \infty</math> количество операций на один порядок меньше по параметру <math>n:</math>

: <math>O(kn)</math> против <math>O(kn^2).</math>

Соотношение количества сложений и взятий минимума для одной итерации фазы SWAP является постоянным и равным <math>k,</math> при <math>n \to \infty</math>.

Максимальная ширина яруса достигается при вычислении <math>\overline {b}</math> и <math>S</math> и равна <math>k(n-k).</math>

При использовании выбранной модели, в предположении доступности неограниченного числа вычислителей, фаза BUILD при <math>n \to \infty</math> требует большего количества операций суммирования на порядок <math>k</math>, по сравнению с одной итерацией фазы SWAP. В свою очередь, количество операций подсчёта минимума ассимптотически эквивалентны.

=== Входные и выходные данные алгоритма ===

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

* число <math>n</math> - количество точек упорядоченного множества <math>X;</math>

* число <math>k</math> - количество требуемых кластеров;

* <math>n</math> векторов, состоящих из <math>n-1</math> вещественных чисел, - попарных расстояний между элементами из множества <math>X</math> за исключением расстояний вида <math>\rho (x, x)=0, x \in X;</math>

''Объём входных данных'': <math>n(n-1)</math> вещественное число и <math>2</math> целых числа.

''Структура хранения данных'':

* сразу после считывания входных данных составляется квадратная симметрическая матрица <math>D^{n * n}</math>, у которой каждый элемент <math>d_{ij}</math> является вещественным числом - расстоянием <math>\rho (x_i, x_j);</math>

* для множества медоидов <math>M</math> создаётся массив из <math>k</math> целых чисел - индексов принадлежащих ему элементов из множества <math>X</math>, аналогичный массив <math>n-k</math> целых чисел создаётся для множества не-медоидов <math>O;</math>

* для пересылки данных, как правило, используется тройка <math>(F_{x_{m_s}, x_{o_h}}^{i_j}; x_{m_s}; x_{o_h})</math> или пара <math>(F_{x_{o_h}}^{i_j}; x_{o_h}),</math> где:

** <math>x_{m_s}</math> - целое число, обозначающее порядковый номер элемента множества <math>X;</math>

** <math>x_{o_h}</math> - целое число, обозначающее порядковый номер элемента множества <math>X;</math>

** <math>F_{x_{m_s}, x_{o_h}}^{i_j}</math> - вещественное число, равное минимальному значению целевой функции, вычисленному в текущем контексте.

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

* <math>k</math> целых чисел, составляющих множество <math>M;</math>

* <math>1</math> вещественное число, являющееся значением целевой функции.

''Объём выходных данных'':

* <math>k</math> целых чисел и <math>1</math> вещественное.

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

Соотношение последовательной и параллельной сложности алгоритма является ''линейным'' и равным <math>n.</math>

''Вычислительная мощность'' последовательного алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, равна <math>O(T*k).</math>

Вычислительная мощность параллельного алгоритма равна <math>O(T*\frac{k}{n}).</math>

Алгоритм PAM является ''менее чувствительным'' к выбросам данных, чем алгоритм k-средних. Это связано с использованием медоидов, менее подверженных влиянию таких данных.<ref> Егоров А. В., Куприянова Н. И. Особенности методов кластеризации данных // Известия Южного федерального университета. Технические науки. –2011. T. 124, № 11. –С. 174-177.</ref>

Фиксированный способ выбора начальных приближений позволяет говорить о воспроизводимости полученных результатов для последовательной реализации. Для параллельной работы алгоритма подобная воспроизводимость отсутствует, так как из-за ''недетерминированности'' выбора элементов, на которых достигается минимальное значение целевой функции для каждой итерации, итоговое множество медоидов и, следовательно, значение целевой функции может меняться.

Алгоритм PAM ''конечен'', так как:

* количество операций фазы BUILD конечно;

* значение целевой фукнции неотрицательно и на каждой итерации фазы SWAP строго уменьшается.

Одно из преимуществ алгоритма PAM заключается в том, что он может работать с любой матрицей различий. В данном случае принципиальное отличие от матрицы расстояний заключается в том, что для матрицы различий может не выполняться неравенство треугольника, так как в основе её построения не обязательно используется метрика.

Основные операция алгоритма PAM: сложение и нахождение минимума. Операция взятия минимума не подвержена процессу накопления ошибки. На каждой итерации алгоритма сложение производится над значениями, взятыми непосредственно из исходных данных. Таким образом, алгоритм PAM не накапливает ошибок в процессе своей работы и является ''устойчивым''.

При <math>k(n-k) \, \bmod \, p \neq 0</math> отсутствует возможность равномерно распределить задачи рассчёта <math>\overline{b}</math> между процессами. Кроме того, если <math>k \, \bmod \, p \neq 0</math>, то после их распределения для некоторых процессов окажется необходимым вычислить несколько соседних значений <math>\overline{a}.</math> Таким образом, ''равномерная'' загрузка процессов ''не всегда возможна''. Помимо этого, агрегирование данных с целью вычисления глобального минимума приводит к простою незадействованных процессов.

Как и большинство алгоритмов кластеризации, PAM может сходиться к некоторому ''локальному минимуму'', не совпадающему с глобальным.

В силу квадратичной сложности последовательного алгоритма, его эффективность при использовании на больших объемах данных достаточно низкая. Алгоритм эффективен при работе с данными небольшого объема.