WikiDer > UPGMA - Википедия

UPGMA (невзвешенный парно-групповой метод со средним арифметическим) представляет собой простую агломерацию (снизу вверх) иерархическая кластеризация метод. Метод обычно относят к Сокаль и Michener.^[1]

Метод UPGMA аналогичен его взвешенный вариант, WPGMA метод.

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

Алгоритм

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

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

Другими словами, на каждом шаге кластеризации обновленное расстояние между объединенными кластерами ${ Displaystyle { mathcal {A}} чашка { mathcal {B}}}$ и новый кластер ${ displaystyle X}$ дается пропорциональным усреднением ${ displaystyle d _ {{ mathcal {A}}, X}}$ и ${ displaystyle d _ {{ mathcal {B}}, X}}$ расстояния:

${ displaystyle 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 (${ displaystyle a}$), Bacillus stearothermophilus (${ displaystyle b}$), Лактобациллы viridescens (${ displaystyle c}$), Ахолеплазма хоть (${ displaystyle d}$), и Micrococcus luteus (${ displaystyle e}$).^[3][4]

Первый шаг

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

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

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

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

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

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

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

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

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

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

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

Второй шаг

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

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

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

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

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

Вычисляем недостающую длину ветки:${ displaystyle delta (u, v) = delta (e, v) - delta (a, u) = delta (e, v) - delta (b, u) = 11-8,5 = 2,5}$ (увидеть окончательную дендрограмму)

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

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

${ Displaystyle D_ {3} (((a, b), e), c) = (D_ {2} ((a, b), c) times 2 + D_ {2} (e, c) times 1) / (2 + 1) = (25,5 раз 2 + 39 раз 1) / 3 = 30}$

Благодаря этому пропорциональному среднему вычисление этого нового расстояния учитывает больший размер ${ Displaystyle (а, б)}$ кластер (два элемента) относительно ${ displaystyle e}$ (один элемент). По аналогии:

${ Displaystyle D_ {3} (((a, b), e), d) = (D_ {2} ((a, b), d) times 2 + D_ {2} (e, d) times 1) / (2 + 1) = (32,5 раз 2 + 43 раз 1) / 3 = 36}$

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

Третий шаг

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

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

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

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

Позволять ${ displaystyle w}$ обозначим узел, к которому ${ displaystyle c}$ и ${ displaystyle d}$ подключены. ${ displaystyle c}$ и ${ displaystyle d}$ к ${ displaystyle w}$ тогда имейте длину ${ Displaystyle дельта (с, ш) = дельта (д, ш) = 28/2 = 14}$ (увидеть окончательную дендрограмму)

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

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

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

Заключительный этап

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

Итак, мы присоединяемся к кластерам ${ Displaystyle ((а, б), д)}$ и ${ displaystyle (c, d)}$.

Позволять ${ displaystyle r}$ обозначают (корневой) узел, к которому ${ Displaystyle ((а, б), д)}$ и ${ displaystyle (c, d)}$ подключены. ${ Displaystyle ((а, б), д)}$ и ${ displaystyle (c, d)}$ к ${ displaystyle r}$ тогда имейте длины:

${ displaystyle delta (((a, b), e), r) = delta ((c, d), r) = 33/2 = 16,5}$

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

${ displaystyle delta (v, r) = delta (((a, b), e), r) - delta (e, v) = 16,5–11 = 5,5}$

${ displaystyle delta (w, r) = delta ((c, d), r) - delta (c, w) = 16,5–14 = 2,5}$

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

Дендрограмма завершена.^[5] Он ультраметрический, потому что все наконечники (${ displaystyle a}$ к ${ displaystyle e}$) равноудалены от ${ displaystyle r}$ :

${ displaystyle delta (a, r) ​​= delta (b, r) = delta (e, r) = delta (c, r) = delta (d, r) = 16,5}$

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

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

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

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

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

Использует

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

Сложность времени

Тривиальная реализация алгоритма построения дерева UPGMA имеет ${ Displaystyle О (п ^ {3})}$ временная сложность, а использование кучи для каждого кластера для сохранения расстояния от другого кластера сокращает время до ${ Displaystyle О (п ^ {2} журнал п)}$. Фионн Муртаг представил некоторые другие подходы для особых случаев, ${ Displaystyle О (к3 ^ {к} п ^ {2})}$ алгоритм времени Дей и Эдельсбруннер^[10] для k-мерных данных, что оптимально ${ Displaystyle О (п ^ {2})}$ для постоянного k, а другой ${ Displaystyle О (п ^ {2})}$ алгоритм для ограниченных входов, когда «агломерационная стратегия удовлетворяет свойству сводимости».^[11]

Смотрите также

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

Рекомендации

внешняя ссылка

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