Участник:Антон Тодуа/Partitioning Around Medoids (PAM): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 49: Строка 49:
  
 
'''Выходные данные''': <math>N</math> чисел <math>k_{1}, k_{2}, \ldots, k_{N}</math>, где <math>k_{i}</math> - целое число, соответствующее кластеру <math>i</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> (кластеры объектов кластеризации)
 
'''Объём выходных данных''': <math>N</math> (кластеры объектов кластеризации)

Версия 00:45, 11 октября 2016

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

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] объектов кластеризации. Целью алгоритма является минимизация средней непохожести

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

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

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

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.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

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

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

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

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

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

3 Литература