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

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

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

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

Самый распространённый вариант реализации [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] меньше нуля. Процесс будет повторятся, пока медоиды не стабилизируются.

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

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

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{ N }[/math] (кластеры объектов кластеризации)