Участник:Антон Тодуа/Partitioning Around Medoids (PAM)

Основные авторы описания: Тодуа А.Р., Гусева Ю.В.

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

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

Кластеризация – это процесс автоматического разбиения некоторого множества элементов на группы(кластеры) на основе степени их схожести. Для лучшего осознания, что такое кластер, рассмотрим пример.

Рисунок 1.

В этом небольшом наборе данных четко выделяются две различные группы объектов,а именно: {1, 2, 3} и (4, 5, 6}. Такие группы и называются кластерами, и обнаружить их является целью кластерного анализа.

Таким образом, у кластера можно выделить два признака

● внутренняя однородность;

● внешняя изолированность.

Для чего используется кластеризация?

● Группировка объектов

● Распознавание образов

● Выявление структуры данных

● Сжатие данных

Для чего используется кластеризация?

● классификация результатов поиска (nigma, yippy,quintura)

● автоматическое построение каталогов

● работа только с несколькими представителями кластеров

● сегментация изображений — компьютерная графика

● кластеризация документов, таблиц и др.данных

● выделение групп клиентов, покупателей,товаров для разработки отдельных стратегий

Очевидно, что спектр применений кластерного анализа очень широк: в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах.

По типу обработки данных можно выделить два класса методов кластерного анализа:

Иерархические методы:

Агломеративные методы AGNES (Agglomerative Nesting):

- CURE;

- ROCK;

- CHAMELEON и т.д.

Дивизимные методы DIANA (Divisive Analysis):

- BIRCH;

- MST и т.д.

Неиерархические методы.

Итеративные

- k-means

- k-medoids

- CLOPE

- LargeItem и т.д.

Самый распространённый вариант реализации [math]\displaystyle{ k }[/math]-medoids называется PAM (Partitioning Around Medoids). Он представляет собой «жадный» алгоритм с очень неэффективной эвристикой. Данный метод был предложен Кауфманом в 1987 году.

Алгоритм начинается с выбора набора данных, состоящих из медоидов и остальных объектов. После выбора [math]\displaystyle{ k }[/math] произвольных объектов в качестве медоидов, необходимо для каждой пары [math]\displaystyle{ {x_i} }[/math] и [math]\displaystyle{ {m_k} }[/math] вычислить значение [math]\displaystyle{ S({x_{i}}{m_{k}}) }[/math]. По ходу выполнения алгоритма происходит итеративная замена одного из медоидов [math]\displaystyle{ x_i }[/math] одним из остальных объектов [math]\displaystyle{ m_k }[/math], если посчитанное ранее значение [math]\displaystyle{ S }[/math] меньше нуля. Процесс будет повторятся, пока медоиды не стабилизируются.

Математическое описание алгоритма

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

• Симметрическую матрицу [math]\displaystyle{ D }[/math] порядка [math]\displaystyle{ N }[/math] с нолями на главной диагонали для [math]\displaystyle{ N }[/math] объектов кластеризации: [math]\displaystyle{ i }[/math]-я строка матрицы [math]\displaystyle{ D }[/math] определяет непохожесть [math]\displaystyle{ i }[/math]-го объекта кластеризации на все остальные объекты
• Число кластеров [math]\displaystyle{ K }[/math], при этом: [math]\displaystyle{ K \lt N }[/math]

Для заданных входных данных, алгоритм выбирает [math]\displaystyle{ K }[/math] объектов - медоидов (medoids) из [math]\displaystyle{ N }[/math] объектов кластеризации. При этом выбор медоидов осуществляется исходя из минимизации средней непохожести (average dissimilarity) объектов и наиболее схожего с ними медоида. От минимизации средней непохожести можно перейти к минимизации суммы непохожестей объектов и наиболее схожего с ними медоида, т.к. это не повлияет на выбор медоидов, но позволит не накапливать ошибки округления, возникающие в результате операции деления.

Для дальнейшего описания алгоритма введём следующие обозначения:

• [math]\displaystyle{ U }[/math] – множество объектов кластеризации, не выбранных в качестве медоидов
• [math]\displaystyle{ S }[/math] – множество объектов кластеризации, выбранных в качестве медоидов
• [math]\displaystyle{ C_{ij} }[/math] – изменение непохожести [math]\displaystyle{ j }[/math]-го объекта в результате выбора [math]\displaystyle{ i }[/math]-го объекта в качестве медоида
• [math]\displaystyle{ T_{ijh} }[/math] – изменение непохожести [math]\displaystyle{ j }[/math]-го объекта в результате операции обмена, т.е. выбора [math]\displaystyle{ h }[/math]-го объекта в качестве медоида, вместо [math]\displaystyle{ i }[/math]-го объекта

Перед выполнением алгоритма множество [math]\displaystyle{ U }[/math]содержит все объекты кластеризации, а множество [math]\displaystyle{ S }[/math] – пусто. Описание значений [math]\displaystyle{ C_{ij} }[/math] и [math]\displaystyle{ T_{ijh} }[/math] и способа их вычисления будет дано при описании макроструктуры алгоритма.

Выполнение алгоритма включает в себя подготовительную стадию BUILD и итерационную стадию SWAP.

Стадия BUILD предназначена для построения начального множества медоидов и состоит в последовательном выполнении следующих шагов:

1. Добавить в множество [math]\displaystyle{ S }[/math] объект, для которого сумма непохожести на все остальные объекты минимальна (самый центральный объект):

[math]\displaystyle{ S = S + \{ arg\min_{i \in U} \sum_{j \in U} d_{ij} \} }[/math]

2. Выбрать ещё [math]\displaystyle{ K-1 }[/math] медоидов следующим образом

[math]\displaystyle{ S = S + \{ arg\max_{i \in U} \sum_{j \in U - \{i\}} C_{ij} \} }[/math]

Стадия SWAP является итерационной, одна итерация состоит в попытке улучшить кластеризацию путём выполнения операции обмена, т.е. замены одного медоида на другой. На каждой итерации выполняется операция [math]\displaystyle{ arg\min_{i \in S, h \in U} \sum_{j \in U - \{h\}} T_{ijh} }[/math]. Если для найденной пары [math]\displaystyle{ i \in S }[/math] и [math]\displaystyle{ h \in U }[/math] значение [math]\displaystyle{ \sum_{j \in U - \{h\}} T_{ijh} }[/math] меньше ноля (это означает, что кластеризацию можно улучшить), то выполняется обмен [math]\displaystyle{ i }[/math] и [math]\displaystyle{ h }[/math] ([math]\displaystyle{ S = S - \{i\} + \{h\}, U = U - \{h\} + \{i\} }[/math]), иначе дальнейшее улучшение кластеризации невозможно и алгоритм завершает свою работу.

В результате работы алгоритма множество [math]\displaystyle{ S }[/math] будет содержать ровно [math]\displaystyle{ K }[/math] объектов – медоидов, принадлежащих разным кластерам. Кластер объекта [math]\displaystyle{ j }[/math] из множества [math]\displaystyle{ U }[/math] совпадает с кластером наиболее схожего с ним медоида: [math]\displaystyle{ arg\min_{i \in S} d_{ij} }[/math]

Вычислительное ядро алгоритма

Из математического описания алгоритма следует, что вычислительное ядро алгоритма сосредоточено в итерационной стадии SWAP. Одна итерация состоит в вычислении:

[math]\displaystyle{ arg\min_{i \in S, h \in U} \sum_{j \in U - \{h\}} T_{ijh} }[/math]

Смысл этого выражения в том, что выполняется выбор такой пары медоида [math]\displaystyle{ i }[/math] и объекта [math]\displaystyle{ h }[/math] операция обмена которых приведёт к улучшению кластеризации или же делается вывод о невозможности такого обмена и работа алгоритма завершается.

Макроструктура алгоритма

Для описания значений [math]\displaystyle{ C_{ij} }[/math] и [math]\displaystyle{ T_{ijh} }[/math] и способа их вычисления введём следующие обозначения (в дополнение к обозначениям, введённым в математическом описании алгоритма):

• [math]\displaystyle{ D_{i} }[/math] – непохожесть [math]\displaystyle{ i }[/math]-го объекта на наиболее схожий с ним медоид
• [math]\displaystyle{ E_{i} }[/math] – непохожесть [math]\displaystyle{ i }[/math]-го объекта на второй наиболее схожий с ним медоид

Отметим, что значения [math]\displaystyle{ D_{i} }[/math] и [math]\displaystyle{ E_{i} }[/math] могут меняться при изменениях в множествах [math]\displaystyle{ U }[/math] и [math]\displaystyle{ S }[/math].

Значение [math]\displaystyle{ C_{ij} }[/math] представляет собой число, на которое уменьшается непохожесть [math]\displaystyle{ j }[/math]-го объекта в результате выбора [math]\displaystyle{ i }[/math]-го объекта в качестве медоида. Очевидно, что данное число всегда неотрицательно. Выбор [math]\displaystyle{ i }[/math]-го объекта в качестве медоида влечёт за собой один из следующих двух случаев. В первом случае, когда [math]\displaystyle{ D_{j} \lt = d_{ij} }[/math], величина [math]\displaystyle{ D_{j} }[/math] не изменится, т.к. самый похожий на [math]\displaystyle{ j }[/math]-ый объект медоид останется таковым и после выбора нового медоида ([math]\displaystyle{ i }[/math]-го объекта), следовательно будет справедливо равенство [math]\displaystyle{ C_{ij} = 0 }[/math]. В втором случае, когда [math]\displaystyle{ D_{j} \gt d_{ij} }[/math], самым похожим на [math]\displaystyle{ j }[/math]-ый объект медоид станет новый выбранный медоид ([math]\displaystyle{ i }[/math]-ый объект), т.к. он похож на [math]\displaystyle{ j }[/math]-ый объект больше, чем предыдущий наиболее схожий с [math]\displaystyle{ j }[/math]-ым объектом медоид, следовательно будет справедливо равенство [math]\displaystyle{ C_{ij} = D_{j} - d_{ij} }[/math].

2. Для каждого объекта [math]\displaystyle{ i \in U }[/math] выполнить шаги 3-5

3. Для каждого объекта [math]\displaystyle{ j \in U - \{i\} }[/math] вычислить [math]\displaystyle{ D_{j} }[/math] и выполнить шаг 4

4. Положить [math]\displaystyle{ C_{ij} = max\{ D_{j} - d_{ij}, 0 \} }[/math], мера улучшения кластеризации

5. Положить [math]\displaystyle{ g_{i} = \sum_{j \in U - \{i\}} C_{ij} }[/math], улучшение от выбора [math]\displaystyle{ i }[/math]-го объекта в качестве медоида

6. Выбрать объект, максимизирующий величину [math]\displaystyle{ g_{i} }[/math] в качестве медоида:

[math]\displaystyle{ \begin{align} k & = arg\min_{i \in U} \sum_{j \in U} d_{ij} \\ U & = U - \{k\} \\ S & = S + \{k\} \\ \end{align} }[/math]

7. Если множество [math]\displaystyle{ S }[/math] содержит менее [math]\displaystyle{ K }[/math] объектов (медоидов) перейти к шагу 2

8. КОНЕЦ стадии BUILD

Стадия SWAP (итерационное улучшение кластеризации):

1. Для всех возможных пар объектов [math]\displaystyle{ i \in S }[/math] и [math]\displaystyle{ h \in U }[/math] выполнить шаги 2-4

2. Вычислить эффект [math]\displaystyle{ T_{ih} }[/math] от выполнения обмена объектов [math]\displaystyle{ i }[/math] и [math]\displaystyle{ h }[/math] (т.е. объект [math]\displaystyle{ i }[/math] больше не выбран в качестве медоида, а объект [math]\displaystyle{ h }[/math], наоборот, выбран в качестве медоида). Способ вычисления [math]\displaystyle{ T_{ih} }[/math] описан ниже.

3. Положим [math]\displaystyle{ (i', h') = arg\min_{i \in S, h \in U} T_{ih} }[/math]

4. Если [math]\displaystyle{ T_{i'h'} }[/math] больше 0 (т.е. кластеризацию можно улучшить), то выполняем обмен объектов [math]\displaystyle{ i }[/math] и [math]\displaystyle{ h }[/math] ([math]\displaystyle{ U = U - \{k\}, S = S + \{k\} }[/math]) и переходим к шагу 1

5. КОНЕЦ стадии SWAP

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

В соответствии с приведённым выше математическим описанием последовательное выполнение алгоритма представляет собой выполнение стадии BUILD, а затем последовательное повторение итераций стадии SWAP до тех пор пока существует пара объектов (один из которых медоид, а другой – нет), которые можно обменять, чтобы улучшить кластер.

Последовательная сложность алгоритма

При описании последовательной сложности будем считать, что выполняется распределение [math]\displaystyle{ N }[/math] объектов по [math]\displaystyle{ K }[/math] кластерам. В соответствии с приведённым математическим описанием алгоритм включает в себя подготовительную стадию BUILD и итерационную стадию SWAP.

Стадия BUILD сводится к вычислению:

Одной операции [math]\displaystyle{ arg\min_{i} \sum_{j} d_{ij} }[/math]
[math]\displaystyle{ K-1 }[/math] операций [math]\displaystyle{ arg\max_{i \in U} \sum_{j \in U - \{i\}} C_{ij} }[/math]

Т.е. стадия BUILD требует:

[math]\displaystyle{ K * N^2 }[/math] операций сложения
[math]\displaystyle{ K * N }[/math] операций сравнения (определения максимума/минимума)
Около [math]\displaystyle{ K * N^2 }[/math] вычислений [math]\displaystyle{ C_{ij} }[/math]

Одна итерация стадии SWAP сводится к вычислению:

[math]\displaystyle{ arg\min_{i \in S, h \in U} \sum_{j \in U - \{h\}} T_{ijh} }[/math]

Т.е. одна итерации стадии SWAP требует порядка:

[math]\displaystyle{ K * N^2 }[/math] операций сложения
[math]\displaystyle{ K * N }[/math] операций сравнения (определения максимума/минимума)
[math]\displaystyle{ K * (N - K) * (N - K - 1) }[/math] вычислений [math]\displaystyle{ T_{ijh} }[/math]

Вычисления [math]\displaystyle{ C_{ij} }[/math] и [math]\displaystyle{ T_{ijh} }[/math] имеют константную сложность для любых [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math] и [math]\displaystyle{ h }[/math], поэтому сложность одной итерации алгоритма определяется как [math]\displaystyle{ O(K * N^2) }[/math]. Таким образом можно отнести алгоритм PAM к алгоритмам с кубической сложностью.

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

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

1. Матрица непохожести объектов кластеризации (dissimilarity matrix) [math]\displaystyle{ D }[/math] (элементы [math]\displaystyle{ d_{ij} }[/math]).
Дополнительные ограничения:
- [math]\displaystyle{ D }[/math] – симметрическая матрица порядка [math]\displaystyle{ N }[/math], т.е. [math]\displaystyle{ d_{ij}= d_{ji}, i, j = 1, \ldots, N }[/math]
- [math]\displaystyle{ D }[/math] – содержит нули на главной диагонали, т.е. [math]\displaystyle{ d_{ii}= 0, i = 1, \ldots, N }[/math]
2. [math]\displaystyle{ K }[/math] - число кластеров, на которое следует разбить объекты кластеризации

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

[math]\displaystyle{ \frac{N (N - 1)}{2} }[/math] (в силу симметричности и нулевой главной диагонали достаточно хранить только  над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. 

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

[math]\displaystyle{ N }[/math] чисел [math]\displaystyle{ k_{1}, k_{2}, \ldots, k_{N} }[/math], где [math]\displaystyle{ k_{i} }[/math] - целое число, соответствующее кластеру [math]\displaystyle{ i }[/math]-го объекта.

Выходными данными алгоритма также можно считать [math]\displaystyle{ K }[/math] чисел, задающих номера объектов кластеризации, выделенных в качестве медоидов (medoids). Однако в большинстве случаев требуется именно определение кластеров объектов, а не поиск соответствующих медоидов.

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

[math]\displaystyle{ N }[/math] (кластеры объектов кластеризации)

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

Ограничения: небольшой объем данных. Достоинства: простота использования; быстрота использования; понятность и прозрачность алгоритма, алгоритм менее чувствителен к выбросам в сравнении с k-means. Недостатки: необходимо задавать количество кластеров; медленная работа на больших базах данных.

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

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

PAM работает эффективно для небольших наборов данных, но не очень хорошо масштабируется для больших наборов данных