Лекции: Практикум

{{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>

** критерий останова:

1-й поток: Номер варианта определяется формулой: (<номер_по_списку_группы> mod 8)+1

2-й и 3-й поток: Номер варианта определяется формулой: <номер в списке группы> mod 18 + 18* (<номер в списке группы> mod 2)

Нумерация груп - с 1-цы