УПГМА

UPGMA ( метод невзвешенных парных групп со средним арифметическим ) — это простой агломеративный (восходящий) метод иерархической кластеризации . У него также есть взвешенный вариант, WPGMA , и их обычно приписывают Сокалю и Миченеру .

Обратите внимание, что невзвешенный термин указывает, что все расстояния в равной степени вносят вклад в каждое вычисляемое среднее значение, и не относится к математическим расчетам, с помощью которых оно достигается. Таким образом, простое усреднение в WPGMA дает взвешенный результат, а пропорциональное усреднение в UPGMA дает невзвешенный результат ( см. рабочий пример ).

Алгоритм

Алгоритм UPGMA строит корневое дерево ( дендрограмму ), которое отражает структуру, присутствующую в матрице попарного сходства (или матрице несходства ).На каждом шаге два ближайших кластера объединяются в кластер более высокого уровня. Расстояние между любыми двумя кластерами ${\mathcal {A}}$ и ${\mathcal {B}}$, каждый из размеров ( т. е . мощности ) ${|{\mathcal {A}}|}$ и ${|{\mathcal {B}}|}$, принимается как среднее всех расстояний $d(x,y)$ между парами объектов $x$ в ${\mathcal {A}}$ и $y$ в ${\mathcal {B}}$, то есть среднее расстояние между элементами каждого кластера:

${1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)$

Другими словами, на каждом этапе кластеризации обновляемое расстояние между объединенными кластерами ${\mathcal {A}}\cup {\mathcal {B}}$ и новый кластер $X$ определяется пропорциональным усреднением $d_{{\mathcal {A}},X}$ и $d_{{\mathcal {B}},X}$ расстояния:

$d_{({\mathcal {A}}\cup {\mathcal {B}}),X}={\frac {|{\mathcal {A}}|\cdot d_{{\mathcal {A}},X}+|{\mathcal {B}}|\cdot d_{{\mathcal {B}},X}}{|{\mathcal {A}}|+|{\mathcal {B}}|}}$

Алгоритм UPGMA создает корневые дендрограммы и требует допущения о постоянной скорости, то есть предполагает ультраметрическое дерево, в котором расстояния от корня до каждой вершины ветвей равны. Когда кончики представляют собой молекулярные данные ( ДНК т.е. , РНК и белок ) , отобранные одновременно, предположение об ультраметричности становится эквивалентным предположению о молекулярных часах .

Рабочий пример

Этот рабочий пример основан на JC69 матрице генетических расстояний , рассчитанной на основе выравнивания последовательностей 5S рибосомальной РНК пяти бактерий: Bacillus subtilis ( $a$), Bacillus stearothermophilus ( $b$), Lactobacillus viridescens ( $c$), Ахолеплазма хоть ( $d$) и Micrococcus luteus ( $e$).

Первый шаг

• Первая кластеризация

Предположим, что у нас есть пять элементов $(a,b,c,d,e)$ и следующая матрица $D_{1}$ попарных расстояний между ними:

	а	б	с	д	и
а	0	17	21	31	23
б	17	0	30	34	21
с	21	30	0	28	39
д	31	34	28	0	43
и	23	21	39	43	0

В этом примере $D_{1}(a,b)=17$ это наименьшее значение $D_{1}$, поэтому мы соединяем элементы $a$ и $b$.

• Оценка длины первой ветки

Позволять $u$ обозначаем узел, к которому $a$ и $b$ теперь подключены. Параметр $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ гарантирует, что элементы $a$ и $b$ равноудалены от $u$. Это соответствует ожиданию гипотезы ультраметричности .Ветви, соединяющиеся $a$ и $b$ к $u$ тогда есть длины $\delta (a,u)=\delta (b,u)=17/2=8.5$ ( см. окончательную дендрограмму )

• Первое обновление матрицы расстояний

Затем мы приступаем к обновлению исходной матрицы расстояний. $D_{1}$ в новую матрицу расстояний $D_{2}$ (см. ниже), уменьшенный в размере на одну строку и один столбец из-за кластеризации $a$ с $b$.Жирные значения в $D_{2}$ соответствуют новым расстояниям, рассчитанным путем усреднения расстояний между каждым элементом первого кластера $(a,b)$ и каждый из оставшихся элементов:

$D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5$

$D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5$

$D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22$

Значения, выделенные курсивом $D_{2}$ на них не влияет обновление матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом кластере.

Второй шаг

• Вторая кластеризация

Теперь мы повторяем три предыдущих шага, начиная с новой матрицы расстояний. $D_{2}$

	(а, б)	с	д	и
(а, б)	0	25.5	32.5	22
с	25.5	0	28	39
д	32.5	28	0	43
и	22	39	43	0

Здесь, $D_{2}((a,b),e)=22$ это наименьшее значение $D_{2}$, поэтому мы присоединяемся к кластеру $(a,b)$ и элемент $e$.

• Оценка длины второй ветви

Позволять $v$ обозначаем узел, к которому $(a,b)$ и $e$ теперь подключены. Из-за ограничения ультраметричности ветви, соединяющиеся $a$ или $b$ к $v$, и $e$ к $v$ равны и имеют следующую длину: $\delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11$

Выводим недостающую длину ветки: $\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5$ ( см. окончательную дендрограмму )

• Обновление матрицы второго расстояния

Затем приступаем к обновлению $D_{2}$ в новую матрицу расстояний $D_{3}$ (см. ниже), уменьшенный в размере на одну строку и один столбец из-за кластеризации $(a,b)$ с $e$. Жирные значения в $D_{3}$ соответствуют новым расстояниям, рассчитанным пропорциональным усреднением :

$D_{3}(((a,b),e),c)=(D_{2}((a,b),c)\times 2+D_{2}(e,c)\times 1)/(2+1)=(25.5\times 2+39\times 1)/3=30$

Благодаря этому пропорциональному среднему при расчете этого нового расстояния учитывается больший размер $(a,b)$ кластер (два элемента) по отношению к $e$ (один элемент). Сходным образом:

$D_{3}(((a,b),e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/3=36$

Таким образом, пропорциональное усреднение придает равный вес начальным расстояниям матрицы. $D_{1}$. По этой причине метод является невзвешенным не по отношению к математической процедуре, а по отношению к начальным расстояниям.

Третий шаг

• Третья кластеризация

Мы снова повторяем три предыдущих шага, начиная с обновленной матрицы расстояний. $D_{3}$.

	((а,б),д)	с	д
((а,б),д)	0	30	36
с	30	0	28
д	36	28	0

Здесь, $D_{3}(c,d)=28$ это наименьшее значение $D_{3}$, поэтому мы соединяем элементы $c$ и $d$.

• Оценка длины третьей ветви

Позволять $w$ обозначаем узел, к которому $c$ и $d$ теперь подключены.Ветви, соединяющиеся $c$ и $d$ к $w$ тогда есть длины $\delta (c,w)=\delta (d,w)=28/2=14$ ( см. окончательную дендрограмму )

• Обновление матрицы третьего расстояния

Для обновления требуется одна запись, учитывая, что два элемента $c$ и $d$ каждый имеет вклад $1$ в среднем расчете :

$D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))\times 1+D_{3}(d,((a,b),e))\times 1)/(1+1)=(30\times 1+36\times 1)/2=33$

Последний шаг

Финал $D_{4}$ матрица:

	((а,б),д)	(в, г)
((а,б),д)	0	33
(в, г)	33	0

Итак, мы объединяем кластеры $((a,b),e)$ и $(c,d)$.

Позволять $r$ обозначают (корневой) узел, к которому $((a,b),e)$ и $(c,d)$ теперь подключены.Ветви, соединяющиеся $((a,b),e)$ и $(c,d)$ к $r$ тогда имейте длину:

$\delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5$

Выводим две оставшиеся длины ветвей:

$\delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5$

$\delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5$

Дендрограмма UPGMA

Дендрограмма готова. Он ультраметрический, потому что все кончики ( $a$ к $e$) равноудалены от $r$ :

$\delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5$

Таким образом, дендрограмма имеет корни $r$, его самый глубокий узел.

Сравнение с другими связями

Альтернативные схемы связи включают кластеризацию с одной связью , полную кластеризацию связи и кластеризацию средней связи WPGMA . Реализация другой связи — это просто вопрос использования другой формулы для расчета расстояний между кластерами на этапах обновления матрицы расстояний вышеуказанного алгоритма. Кластеризация с полной связью позволяет избежать недостатка альтернативного метода кластеризации с одной связью - так называемого явления цепочки , при котором кластеры, сформированные с помощью кластеризации с одной связью, могут быть объединены вместе из-за того, что отдельные элементы находятся близко друг к другу, даже если многие элементы в каждом из них кластеры могут находиться очень далеко друг от друга. Полная связь имеет тенденцию находить компактные кластеры примерно одинакового диаметра.

Сравнение дендрограмм, полученных разными методами кластеризации из одной и той же матрицы расстояний .

Кластеризация с одной связью	Кластеризация с полной связью	Кластеризация средних связей: WPGMA	Кластеризация средних связей: UPGMA.

Использование

• В экологии это один из самых популярных методов классификации единиц выборки (например, участков растительности) на основе их попарного сходства по соответствующим переменным дескриптора (например, видовому составу). Например, его использовали для понимания трофического взаимодействия между морскими бактериями и протистами.
• В биоинформатике UPGMA используется для создания фенетических деревьев (фенограмм). UPGMA изначально был разработан для использования в исследованиях электрофореза белков , но в настоящее время чаще всего используется для создания направляющих деревьев для более сложных алгоритмов. Этот алгоритм, например, используется в процедурах выравнивания последовательностей , поскольку он предлагает один порядок, в котором последовательности будут выравниваться. Действительно, направляющее дерево направлено на группировку наиболее похожих последовательностей, независимо от скорости их эволюции или филогенетического сходства, и это именно цель UPGMA.
• В филогенетике UPGMA предполагает постоянную скорость эволюции ( гипотеза молекулярных часов ) и то, что все последовательности были отобраны в одно и то же время, и не является общепризнанным методом вывода взаимосвязей, если это предположение не было проверено и обосновано для используемого набора данных. использовал. Обратите внимание, что даже при «строгих часах» последовательности, выбранные в разное время, не должны приводить к ультраметрическому дереву.

Временная сложность

Тривиальная реализация алгоритма построения дерева UPGMA имеет $O(n^{3})$ временная сложность, а использование кучи для каждого кластера для сохранения его расстояний от другого кластера сокращает время $O(n^{2}\log n)$. Фионн Мурта представил $O(n^{2})$ алгоритм времени и пространства.

См. также

• Присоединение к соседям
• Кластерный анализ
• Кластеризация с одной связью
• Кластеризация с полной связью
• Иерархическая кластеризация
• Модели эволюции ДНК
• Молекулярные часы

Внешние ссылки

• Реализация алгоритма кластеризации UPGMA в Ruby (AI4R)
• Пример расчета UPGMA с использованием матрицы подобия
• Пример расчета UPGMA с использованием матрицы расстояний