Алговики - Вклад [ru]

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:58:04Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

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

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом (Leonard Kaufman) и Питером Руссивом (Peter J. Rousseeuw) и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей расстояний, его цель - минимизировать расстояние между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера расстояния между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что расстояние только между объектами из одного кластера будет вычислено в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. С матрицей расстояний.

Алгоритм имеет две фазы:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу расстояний, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие среднее расстояние, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

1. Начальное приближение: <math>M_0 = M_{BUILD}, L_0 = L_{BUILD}</math>;

2. Множественные вычисления значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>;

3. Изменение множеств в соответствии с выбранной парой <math>(x_{m_t}, x_{l_q})</math>:

<math>M_i = M_{i-1} \backslash \{x_{m_t}\} \cup \{x_{l_q}\} , L_i = L_{i-1} \cup \{x_{m_t}\} \backslash \{x_{l_q}\} </math>;

4. Проверка критерия останова.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} d(x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:55:55Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

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

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом (Leonard Kaufman) и Питером Руссивом (Peter J. Rousseeuw) и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей расстояний, его цель - минимизировать расстояние между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера расстояния между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что расстояние только между объектами из одного кластера будет вычислено в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. С матрицей расстояний.

Алгоритм имеет две фазы:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу расстояний, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие среднее расстояние, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

1. Начальное приближение: <math>M_0 = M_{BUILD}, L_0 = L_{BUILD}</math>;

2. Множественные вычисления значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>;

3. Изменение множеств в соответствии с выбранной парой <math>(x_{m_t}, x_{l_q})<math>:

<math>M_i = M_{i-1} \backslash \{x_{m_t}\} \cup \{x_{l_q}\} , L_i = L_{i-1} \cup \{x_{m_t}\} \backslash \{x_{l_q}\} <math>;

4. Проверка критерия останова.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:50:06Z

Ivan.Z: /* Общее описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

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

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом (Leonard Kaufman) и Питером Руссивом (Peter J. Rousseeuw) и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей расстояний, его цель - минимизировать расстояние между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера расстояния между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что расстояние только между объектами из одного кластера будет вычислено в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. С матрицей расстояний.

Алгоритм имеет две фазы:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу расстояний, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие среднее расстояние, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:47:01Z

Ivan.Z: /* Общее описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

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

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей расстояний, его цель - минимизировать расстояние между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера расстояния между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что расстояние только между объектами из одного кластера будет вычислено в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. С матрицей расстояний.

Алгоритм имеет две фазы:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу расстояний, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие среднее расстояние, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:40:37Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

'''Кластеризация''' - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
'''Partitioning Around Medoids''' ('''PAM''') - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера непохожести между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. Напрямую с матрицей непохожести.

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

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу непохожести, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:39:27Z

Ivan.Z: /* Вычислительное ядро алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

'''Кластеризация''' - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
'''Partitioning Around Medoids''' ('''PAM''') - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера непохожести между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. Напрямую с матрицей непохожести.

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

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу непохожести, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма PAM сосредоточено в стадии '''SWAP''' и состоит из вычислений значений целевой функции для различных вариантов замены текущей медоиды на новую:

<math>F = arg \min_{i \in M , j \in L} \sum_{y \in L \backslash \{j\}} {min (d(i,y),d(j,y))} </math>

=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T20:19:15Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

'''Кластеризация''' - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
'''Partitioning Around Medoids''' ('''PAM''') - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера непохожести между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. Напрямую с матрицей непохожести.

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

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу непохожести, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Обозначения'':

1. <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_s} \} - </math> множество медоид;

2. <math>L = \{ x_{l_1}, x_{l_2}, ... , x_{m_t} \} - </math> множество объектов <math>x_i</math>, не являющихся медоидами;

3. <math>F_{M,L} = \sum_{j = 1}^{N} \min_{ x_{m_q} \in M} d(x_{m_q},x_{l_j}) - </math> целевая функция.

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

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(x_i,x_j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(x_i,x_j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Представляет из себя выбор K медоид за K последовательных шагов:

1. <math>M_0 = \varnothing, L_0 = X</math>;

2. <math>x_{m_i} = \arg \min_{x_{l_q} \in L_0} \sum_{j = 1}^N d(x_{l_q},x_j), L_1 = L_0 \backslash \{x_{m_i}\}, M_1 = M_1 \cup \{x_{m_i}\}, i=1 \dots N </math>;

Фаза '''Swap''':

Представляет из себя итерационный процесс.

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{l_q} \in L \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{l_q}, x_{m_s}) \}, i=1 \dots K, K -</math> множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T19:27:23Z

Ivan.Z: /* Общее описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

'''Кластеризация''' - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
'''Partitioning Around Medoids''' ('''PAM''') - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

Алгоритм '''Partitioning Around Medoids''' ('''PAM''') был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:

<math>F(x)=minimize \sum_{i=1}^{N}\sum_{j=1}^{N} d(i,j)z_{ij}</math>

При этом:

1. <math> \sum_{i=1}^N {z_{ij} = 1} , j = 1,2,...,N</math>;

2. <math>z_{ij} \le y_i , i, j = 1,2,...,N</math>;

3. <math>\sum_{i=1}^N {y_i = K} , K - </math> число кластеров;

4. <math>y_i , z_{ij} \in \{ 0,1 \} , i, j = 1,2,...,N</math>.

где функция <math>F(x)</math> - целевая минимизируемая функция, <math>d(i,j)</math> - мера непохожести между объектами <math>i</math> и <math>j</math>, <math>z_{ij}</math> - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:

1. Каждый объект принадлежит одному и только одному кластеру;

2. Каждый объект относится к медоиде, представляющей его кластер;

3. Есть в точности K кластеров;

4. Решающая переменная принимает значения 0 или 1.

PAM может работать с двумя типами входных данных:

1. С матрицей объектов и значениями ее переменных;

2. Напрямую с матрицей непохожести.

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

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:

Фаза '''Build''':

1. Выбрать K объектов в качестве медоид;

2. Построить матрицу непохожести, если она не была задана;

3. Отнести каждый объект к ближайшей медоиде;

Фаза '''Swap''':

4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид;

5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T19:10:58Z

Ivan.Z: /* Литература */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.</li>
<li>Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.</li>
<li>Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.</li>
<li>Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:58:00Z

Ivan.Z: /* Литература */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />
<ol>
<li>
[Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.]</li>
<li>[Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.]</li>
<li>[Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.]</li>
<li>[Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.]</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:56:55Z

Ivan.Z: /* Литература */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />

<ol>
<li>
[Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.]</li>
<li>[Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.]</li>
<li>[Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.]</li>
<li>[Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.]</li>
</ol>

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:55:08Z

Ivan.Z: /* Литература */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />

[Fasulo D. An analysis of recent work on clustering algorithms. – Technical report, 1999. – №. 01-03. – С. 02.]
[Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering //Expert Systems with Applications. – 2009. – Т. 36. – №. 2. – С. 3336-3341.]
[Van der Laan M., Pollard K., Bryan J. A new partitioning around medoids algorithm //Journal of Statistical Computation and Simulation. – 2003. – Т. 73. – №. 8. – С. 575-584.]
[Нейский И. М. Классификация и сравнение методов кластеризации //ББК 32.813 И 76 Составитель: ЮН Филиппович. – 2006. – С. 130.]

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:27:27Z

Ivan.Z: /* Существующие реализации алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>[http://research.omicsgroup.org/index.php/Python_(programming_language) Python]. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащем также различные варианты k-means</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:22:12Z

Ivan.Z: /* Существующие реализации алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
<li>Python. Алгоритм PAM реализован как k-medoids в пакете pyclust, содержащим и другие алгоритмы кластеризации, например, k-means</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:17:49Z

Ivan.Z: /* Макроструктура алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(a,b) = \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2} = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T18:08:52Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
''Входные данные'':

1. Множество <math>X = \{ x_{1}, x_{2}, \dots, x_{N} \}</math> объектов <math>x_i</math>, каждый из который задается <math>P</math> вещественными значениями;

2. Симметрическая матрица <math>D</math>, элементы <math>d_{ij} = d(i,j)</math> которой являются расстояниями между объектами <math>x_i</math> и <math>x_j</math>;

3. Число кластеров <math>K \le N</math>;

4. Метрика <math>d_{ij} = d(i,j)</math>, задающая расстояние между объектами <math>x_i</math> и <math>x_j</math>.

''Вычислительные формулы метода'':

Фаза '''Build''':

Фаза '''Swap''':

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

1. <math>M = \{ x_{m_{1}}, x_{m_{2}}, ..., x_{m_{K}} \}</math> - множество медоид;

2. <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math>- множество искомых кластеров.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов и их значений, то операция вычисления расстояния между объектами i и j будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(i,j) = \sqrt{(i_1-j_1)^2+(i_2-j_2)^2+\dots+(i_w-j_w)^2} = \sqrt{\sum_{j=1}^w (p_j-q_j)^2}</math> , где автвадр

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T17:27:22Z

Ivan.Z: /* Макроструктура алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
Обозначения:

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

Вычислительные формулы метода:
Фаза Build

Фаза Swap

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

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
Если на вход алгоритма была подана не матрица расстояний, а матрица объектов и их значений, то операция вычисления расстояния между объектами i и j будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
<math> d(i,j) = \sqrt{(i_1-j_1)^2+(i_2-j_2)^2+\dots+(i_w-j_w)^2} = \sqrt{\sum_{j=1}^w (p_j-q_j)^2}</math> , где автвадр

=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T16:02:02Z

Ivan.Z: /* Математическое описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
Обозначения:

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

Вычислительные формулы метода:
Фаза Build

Фаза Swap

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

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
</ol>

== Литература ==
<references />

Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

2016-10-15T16:00:06Z

Ivan.Z: /* Общее описание алгоритма */

{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*K*N^2)</math>
| input_data = <math> N*(N-1)/2 + 2 </math>
| output_data = <math> N </math>
}}

Авторы: [[Участник:Denemmy|Галеев Д.Ф]], [[Участник:zaputlyaev|Запутляев И.]]

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

=== Общее описание алгоритма ===

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы. 
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

====================

Алгоритм Partitioning Around Medoids (PAM) был создан Леонардом Кауфманом и Питером Россеву и он очень похож на алгоритм K-means, в основном потому, что оба являются алгоритмами кластеризации, другими словами, оба разделяют множество объектов на группы (кластеры) и работа обоих основана на попытках минимизировать ошибку, но PAM работает с медоидами - объектами, являющимися частью исходного множества и представляющими группу, в которую они включены, а K-means работает с центроидами - искусственно созданными объектами, представляющими кластер.

Алгоритм PAM разделяет множество из N объектов на K кластеров, где и множество объектов, и число K являются входными данными алгоритма. Алгоритм работает с матрицей непохожести, чья цель - минимизировать общую непохожесть между представителями каждого кластера и его членами. Алгоритм использует следующую модель для решения задачи:
{\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}} {\displaystyle F(x)={\text{minimize}}\sum _{i=1}^{n}\sum _{j=1}^{n}d(i,j)z_{ij}}

Пусть:

Σ i=1 n zij = 1 , j = 1,2,...,n
zij ≤ yi , i, j = 1,2,...,n
Σ i=1 n yi = k , k = число кластеров
yi , zij € {0,1} , i, j = 1,2,...,n

где функция F(x) - целевая минимизируемая функция, d(i,j) - мера непохожести между объектами i и j, z_ij - переменная, которая гарантирует, что непохожесть только между объектами из одного кластера будет вычислена в целевой функции. Остальные выражения являются следующими ограничениями:
1. Каждый объект принадлежит одному и только одному кластеру
2. Каждый объект относится к медоиде, представляющей его кластер
3. Есть в точности K кластеров
4. Решающая переменная принимает значения 0 или 1

PAM может работать с двумя типами входных данных:
1. С матрицей объектов и значениями ее переменных
2. Напрямую с матрицей непохожести
В последнем случае пользователь может подать матрицу непохожести на вход алгоритму, вместо матрицы, представляющей объекты.

В любом случае, алгоритм находит решение задачи. Алгоритм работает следующим образом:
Фаза Build:
1. Выбрать K объектов в качестве медоид
2. Построить матрицу непохожести, если она не была задана
3. Отнести каждый объект к ближайшей медоиде

Фаза Swap:
4. Для каждого кластера найти объекты, снижающие коэффициент средней непохожести, и если такие объекты есть, выбрать те, которые снижают его сильней всего, в качестве медоид
5. Если хотя бы одна медоида поменялась, вернуться к шагу 3, иначе завершить алгоритм.

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

=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===

''Псевдокод алгоритма'':

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 вернуть М

=== Последовательная сложность алгоритма===
Обозначим количество кластеров как <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>

=== Информационный граф ===

'''Фаза BUILD'''

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

[[Файл:BUILD.png|thumb|center|800px|Рисунок 1. Информационный граф шага t фазы BUILD алгоритма.]]

''Операции''
<ul>
<li>Update<math>_M</math> и Update<math>_L</math> - операции обновления множества метоидов и не-метоидов соответственно</li>
<li>SUM - вычисление функции ошибки, на вход подается расстояния от очередного объекта до всех остальных, а также минимальные расстояния от выбранных на данном шаге метоидов до всех остальных вершин</li>
<li>MIN<math>_s</math> - нахождение аргумента, соответствующего минимальному значению, а также само минимальное значение</li>
<li>MIN<math>_d</math> - нахождение минимальных расстояний от медоидов до остальных вершин, используется в операции SUM</li>
</ul>
Количество шагов t равно K, где K - число кластеров

'''Фаза SWAP'''

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

[[Файл:SWAP.png|thumb|center|800px|Рисунок 1. Информационный граф итерации t фазы SWAP алгоритма.]]

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

=== Ресурс параллелизма алгоритма ===

Пусть число кластеров равно <math>K</math>, а число объектов равно <math>N</math>. Тогда параллельная сложность фазы BUILD имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Таким образом параллельная сложность фазы BUILD равна <math>O(K*N*T)</math>.

Параллельная сложность фазы SWAP имеет <math>O(K*N)</math> операций сложения и <math>O(K*N)</math> операций сравнения двух вещественных чисел. Параллельная сложность фазы SWAP равна <math>O(K*N*T)</math>.

Таким образом параллельная сложность алгоритма равна <math>O(K*N*T)</math>.

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

''Входные данные'':
* число <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> целых чисел.

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

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

Сильные стороны алгоритма:
<ul>
<li>Меньшая чувствительность к выбросам, чем k-means</li>
<li>Несложность реализации</li>
<li>
Возможность распараллеливания
Однако равномерная загрузка процессоров не всегда возможна.
</li>
</ul>
Недостатки алгоритма:
<ul>
<li>Квадратичная сложность алгоритма</li>
<li>
Количество кластеров является параметром алгоритма
Во многих задачах число кластеров может быть неизвестным.
</li>
<li>
Возможность сходимости к локальному оптимуму
Оптимальное решение не гарантировано.
</li>
</ul>

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

<ol>
<li>[http://research.omicsgroup.org/index.php/ELKI ELKI] реализует несколько вариантов алгоритма кластеризации, включая алгоритм PAM. Написан на Java</li>
<li>[http://java-ml.sourceforge.net/ Java-ML]. Включает реализацию k-metoid. Написан на Java</li>
<li>[http://research.omicsgroup.org/index.php?title=Julia_language&action=edit&redlink=1 Julia] содержит реализацию k-metoid в пакете для кластеризации JuliaStats</li>
<li>[http://research.omicsgroup.org/index.php/R_(programming_language) R] включает различные варианты k-means в пакете flexclust. Алгоритм PAM реализован в пакете cluster</li>
<li>[http://research.omicsgroup.org/index.php/MATLAB MATLAB]. Реализованы PAM, CLARA и другие алгоритмы кластеризации</li>
</ol>

== Литература ==
<references />