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

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

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

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

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

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

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

Для заданных входных данных, алгоритм выделяет $K$ объектов - медоидов (medoids) из $N$ объектов кластеризации. Задачей алгоритма является минимизация средней непохожести (average dissimilarity) объектов и ближайшего к ним медоида. Без ограничения общности можно минимизировать сумму непохожестей объектов на ближайший к ним медоид.

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

• $U$ – множество объектов кластеризации, не выбранных в качестве медоидов
• $S$ – множество объектов кластеризации, выбранных в качестве медоидов
• $D_{i}$ – непохожесть $i$-го объекта на ближайший к нему медоид
• $E_{i}$ – непохожесть $i$-го объекта на второй ближайший к нему медоид

Перед выполненением алгоритма множество $U$ содержит все объекты кластеризации, а множество $S$ – пусто. Числа $D_{i}$ и $E_{i}$ могут измениться при изменениях в множествах $U$ и $S$.

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

Стадия BUILD (стоит начальное множество медоидов):

1. Добавить в множество $S$ объект, для которого сумма непохожести на все остальные объекты минимальна (самый центральный объект): $S = \{ arg\min_{i \in U} \sum_{j \in U} d_{ij} \}$

2. Для каждого объекта $i \in U$ выполнить шаги 3-5

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

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

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

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

$k = arg\min_{i \in U} \sum_{j \in U} d_{ij} U = U - \{k\} S = S + \{k\}$

7. Если множество $S$ содержит менее $K$ объектов (медоидов) перейти к шагу 2

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

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

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

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

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

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

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

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

При описании последовательной сложности будем считать, что выполняется кластеризация $N$ объектов для $K$ кластеров. В соответствии с приведённым математическим описанием алгоритм включает в себя подготовительную стадию BUILD и итерационную стадию SWAP.

Для выполнения фазы BUILD требуется:

• Около $K * N^2$ операций сложения (вычитания),
• Около $K * N^2$ операций сравнения (определения максимума/минимума).

Для выполнения одной итерации фазы SWAP требуется:

• Около $K * N^2$ операций сложения (вычитания),
• Около $K * N^2$ операций сравнения (определения максимума/минимума).

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

При классификации по последовательной сложности, таким образом, данный алгоритм можно отнести к алгоритмам с кубической сложностью.

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

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

1. Матрица непохожести объектов кластеризации (dissimilarity matrix) $D$ (элементы $d_{ij}$). Дополнительные ограничения:

• $D$ – симметрическая матрица порядка $N$, т.е. $d_{ij}= d_{ji}, i, j = 1, \ldots, N$
• $D$ – содержит нули на главной диагонали, т.е. $d_{ii}= 0, i = 1, \ldots, N$

2. $K$ - число кластеров, на которое следует разбить объекты кластеризации

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

Выходные данные: $N$ чисел $k_{1}, k_{2}, \ldots, k_{N}$, где $k_{i}$ - целое число, соответствующее кластеру $i$-го объекта.

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

Объём выходных данных: $N$ (кластеры объектов кластеризации)