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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 8: Строка 8:
  
 
Алгоритм начинается с выбора набора данных, состоящих из медоидов и остальных объектов. После выбора <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> меньше нуля. Процесс будет повторятся, пока медоиды не стабилизируются.
 
Алгоритм начинается с выбора набора данных, состоящих из медоидов и остальных объектов. После выбора <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> меньше нуля. Процесс будет повторятся, пока медоиды не стабилизируются.
 
 
 
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 17:29, 10 октября 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 Математическое описание алгоритма

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

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

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

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

1.7 Информационный граф

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

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

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

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

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

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

3 Литература