дз 1. PAM (Partitioning Around Medoids) (Практикум)
Описание файла
Файл "дз 1. PAM (Partitioning Around Medoids)" внутри архива находится в следующих папках: Практикум, 2016 Практикум (Дирихле, Пуассон). Текстовый-файл из архива "Практикум", который расположен в категории "". Всё это находится в предмете "суперкомпьютерное моделирование и технологии" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр текстового-файла онлайн
{{Assignment|Zhum|Dexter}}
{{algorithm
| name = Partitioning Around Medoids
| serial_complexity = <math>O(T*kn^2)</math>
| input_data = <math>n*(n-1)+2</math>
| output_data = <math>k+1</math>
| pf_height = <math>O(T*kn)</math>
| pf_width = <math>O(k(n-k))</math>
}}
'''Авторы''':
* [[Участник:Avasilenko|А.Э.Василенко]] (отвечает за программистскую составляющую);
* [[Участник:Anastasia|А.В.Тузикова]] (отвечает за математическую составляющую).
Вклад авторов считать равноценным, чётких границ ответственности провести невозможно.
==Свойства и структура алгоритма==
=== Общее описание алгоритма ===
Объединение схожих объектов в группы - один из важнейших видов человеческой деятельности<ref>Rousseeuw P. J., Kaufman L. Finding Groups in Data. – Wiley Online Library, 1990.</ref>. Более того - это важная часть процесса познания мира, в котором мы живем. Мы учим детей различать кошек и собак, воду и песок, мужчин и женщин путем постоянного развития и улучшения подсознательных схем классификации. Примеры есть и во взрослой жизни – в химии необходимо классифицировать соединения, в археологии – объединять находки по периодам и т.д.
'''Задача кластеризации''' - разделение множества объектов на заданное число множеств с минимизацией некоторого функционала - является популярной задачей, относится к разделу машинного обучения и находит применение в таких областях, как анализ текста, биоинформатика, интеллектуальные транспортные системы и др. <ref> Речкалов Т.В. Параллельный алгоритм кластеризации для многоядерного сопроцессора Intel Xeon Phi // Суперкомпьютерные дни в России: Труды vеждународной конференции. – М.: Изд-во МГУ, 2015, c. 532.</ref>
Существует несколько видов кластеризации<ref>Маннинг К.Д., Введение в информационный поиск: пер. с англ. / К.Д. Маннинг, П. Рагхаван, Х.Шютце - М. : Вильямс, 2011. - 528.</ref>:
* ''плоская кластеризация'' (''flat clustering'') - порождает совокупность кластеров, не имеющих явных взаимосвязей;
* ''иерархическая кластеризация'' (''hierarchical clustering'') - создаёт иерархию кластеров.
'''PAM''' ('''Partitioning Around Medoids''') - плоский алгоритм кластеризации, позволяющий выделить <math>k</math> кластеров (множеств), удовлетворяющих следующим свойствам:
* каждая группа содержит хотя бы один объект;
* каждый объект принадлежит ровно одной группе.
Модель <ref>Kaufman, L. and Rousseeuw, P.J., Clustering by means of Medoids. In: Y. Dodge and North-Holland, editor. Statistical Data Analysis Based on the L1-Norm and Related Methods. Springer US; 1987, p. 405–416.</ref>, лежащая в основе алгоритма PAM, основана на выборе <math>k</math> объектов, являющихся характерными точками соответствующего кластера. Таким образом, кластерам сопоставляются принадлежащие им объекты, называемые '''медоидами''', на основании которых распределяются остальные объекты по принципу наибольшего сходства. Cама модель называется моделью '''k-medoids''' (не путать с моделью ''k-median'').
PAM состоит из двух фаз: '''BUILD''' и '''SWAP''':
* на фазе BUILD выполняется первичная кластеризация, в ходе которой последовательно выбираются <math>k</math> объектов в качестве медоидов;
* фаза SWAP представляет собой итерационный процесс, в ходе которого производятся попытки улучшить множество медоидов. Алгоритм выполняет поиск пары объектов (медоид, не-медоид), минимизирующих целевую функцию при замене, после чего обновляет множество медоидов.
На каждой итерации алгоритма выбирается пара (медоид, не-медоид) такая, что замена медоида <math>x_{m_l}</math> на не-медоид <math>x_{o_h}</math> дает лучшую кластеризацию из возможных. Оценка кластеризации выполняется с помощью целевой функции, вычисляемой как сумма расстояний от каждого объекта до ближайшего медоида:
:<math>E = \sum_{j = 1}^n \min_{1 \leq l \leq k} \rho ( x_{m_l},x_{o_j} )</math>
Процедура изменения множества медоидов повторяется, пока есть возможность улучшения значения целевой функции.
=== Математическое описание алгоритма ===
''Исходные данные'':
* множество кластеризуемых объектов <math>X = \{ x_1, x_2, ... , x_n \} </math>, где <math>x_i</math> - кортеж, состоящий из <math> w </math> вещественных чисел;
* симметрическая матрица <math>D</math>, элементы матрицы <math>d_{ij}=d(i,j)</math> - вычисленные расстояния между объектами <math>x_i, x_j</math>;
* количество кластеров <math>k \leq n.</math>
''Обозначения'':
* <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_k} \} </math> - множество медоидов, <math> M \subseteq X ;</math>
* <math>O = \{ x_{o_1}, x_{o_2}, ... , x_{o_r} \} </math> - множество не-медоидов, <math> O \subseteq X, </math> где <math>r=n-k;</math>
* <math>d_{ij}=\rho (x_i, x_j )</math>, где <math> \rho : X \times X \rightarrow R </math> — метрика расстояния;
* <math>F_{M,O} = \sum_{j = 1}^{n} \min_{ x_{m_l} \in M} \rho ( x_{m_l},x_{o_j} )</math> - значение целевой функции для заданных множеств <math>M</math> и <math>O;</math>
* <math>T^i</math> - изменение целевой функции на <math>i</math>-м шаге фазы SWAP.
''Выходные данные'':
* <math>M = \{ x_{m_1}, x_{m_2}, ... , x_{m_k} \}</math> - множество медоидов;
* <math>K_{m_i} = \{ x_{o_h} \in O \| x_{m_i} = \arg \min_{x_{m_s} \in M} \rho (x_{o_h}, x_{m_s}) \}, 1 \leq i \leq k</math> - искомые кластеры.
''Вычислительные формулы метода'':
* ''фаза BUILD'' (состоит из <math>k</math> шагов последовательного выбора <math>k</math> медоидов):
** <math>O_0 = X, M_0 = \varnothing ;</math>
** <math>x_{m_1} = \arg \min_{x_{o_h} \in O_0} \sum_{j = 1}^n \rho \left ( x_{o_h},x_j \right ), O_1 = O_0 \backslash \{x_{m_1}\}, M_1 = M_1 \cup \{x_{m_1}\} ; </math>
** <math>x_{m_2} = \arg \min_{x_{o_h} \in O_1} \sum_{j = 1}^{n} \min ( \rho ( x_{m_1},x_j ), \rho ( x_{o_h},x_j ) ), O_2 = O_1 \backslash \{x_{m_2}\}, M_2 = M_1 \cup \{x_{m_2}\} ; </math>
** <math>x_{m_3} = \arg \min_{x_{o_h} \in O_2} \sum_{j = 1}^{n} \min_{1 \leq l \leq 2} ( \rho ( x_{m_l},x_j ) , \rho ( x_{o_h},x_j ) ) , O_3 = O_2 \backslash \{x_{m_3}\}, M_3 = M_3 \cup \{x_{m_3}\} ; </math>
** ...
** <math>x_{m_k} = \arg \min_{x_{o_h} \in O_{k-1}} \sum_{j = 1}^{n} \min_{ x_{m_l} \in M_{k-1}} ( \rho ( x_{m_l},x_j ), \rho ( x_{o_h},x_j ) ) , O_k = O_{k-1} \backslash \{x_{m_k}\}, M_k = M_{k-1} \cup \{x_{m_k}\} ; </math>
* ''фаза SWAP'' (итерационный процесс):
** начальное приближение: <math>O_0 = O_k^{BUILD}, M_0 = M_k^{BUILD};</math>
** <math>i</math>-й шаг итерации:
*** вычисление целевой функции при оптимальной замене (замене, при которой достигается лучшая кластеризация из возможных на текущей итерации): <br><math>F^i = \min_{x_{m_s} \in M_{i-1} , x_{o_h} \in O_{i-1}} \sum_{j = 1}^{n} \min_{ x_{m_l} \in M_{i-1} \backslash \{x_{m_s}\} } ( \rho ( x_{m_l},x_j ), \rho ( x_{o_h},x_j) ); </math>
*** определение пары (медоид, не-медоид), на которой достигается оптимальная замена: <br><math> (x_{m_s}, x_{o_h}) = \arg F^i; </math>
*** проверка критерия останова;
*** изменение множеств в соответствии с выбранной парой <math> (x_{m_s}, x_{o_h}):</math> <br><math>M_i = M_{i-1} \backslash \{x_{m_s}\} \cup \{x_{o_h}\} , O_i = O_{i-1} \cup \{x_{m_s}\} \backslash \{x_{o_h}\} ;</math>
** критерий останова: