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

Partitioning Around Medoids
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(T*K*N^2) }[/math]
Объём входных данных	[math]\displaystyle{ N*(N-1)/2 + 2 }[/math]
Объём выходных данных	[math]\displaystyle{ N }[/math]

Авторы: Галеев Д.Ф, Запутляев И.

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

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

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. 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]\displaystyle{ K }[/math], количество объектов как [math]\displaystyle{ N }[/math], число итераций алгоритма как [math]\displaystyle{ T }[/math].

На стадии BUILD каждый шаг нахождения очередного метоида имеет сложность [math]\displaystyle{ O(N^2) }[/math] по количеству операций сложения вещественных чисел и по количеству операций сравнения двух вещественных чисел.
Тогда стадия BUILD имеет сложность [math]\displaystyle{ O(K*N^2) }[/math]

На стадии SWAP вычисление целевой функции имеет сложность [math]\displaystyle{ O(K*N^2) }[/math] по количеству операций сложения вещественных чисел и по количеству операций сравнения двух вещественных чисел.

Таким образом алгоритм PAN имеет сложность [math]\displaystyle{ O(T*K*N^2) }[/math]

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

Фаза BUILD

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

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

Операции

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

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

Фаза SWAP

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

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

Операции

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

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

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

* число [math]\displaystyle{ K }[/math] - количество кластеров;
* число [math]\displaystyle{ N }[/math] - количество объектов;
* вектор попарных расстояний, имеющий длину [math]\displaystyle{ N*(N-1)/2 }[/math], из данных чисел однозначно восстанавливается симметрическая матрица расстояний [math]\displaystyle{ D }[/math]

Объём входных данных: [math]\displaystyle{ N*(N-1)/2 }[/math] вещественное число и [math]\displaystyle{ 2 }[/math] целых числа.

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

* K чисел [math]\displaystyle{ m_1, m_2, ..., m_K }[/math] - индексы объектов соответствующие метоидам;
* N-K чисел [math]\displaystyle{ k_1, k_2, ..., k_{N-K} }[/math] - номера кластеров для каждого объекта (кроме тех, что являются метоидами);

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

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

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

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

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

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

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

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

• Возможность распараллеливания

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

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

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

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

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

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

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

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

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

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