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

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

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

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

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

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

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

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

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

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

Выполнение алгоритма состоит из двух

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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