UPGMA

UPGMA (англ. unweighted pair group method with arithmetic mean — незважений метод групування пар з арифметичним середнім) — це простий агломеративний (висхідний) метод ієрархічної кластеризації. Він також має зважений варіант 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$ ), Acholeplasma modicum ( $d$ ) та Micrococcus luteus ( $e$ ).

Перший крок

Нехай є п'ять елементів $(a,b,c,d,e)$ та матриця $D_{1}$ попарних відстаней між ними. Найменше значення — $D_{1}(a,b)=17$ , тож з'єднуємо елементи $a$ та $b$ . Нехай $u$ позначає вузол, до якого тепер приєднані $a$ та $b$ . Встановлення $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ забезпечує рівновіддаленість $a$ та $b$ від $u$ :

$\delta (a,u)=\delta (b,u)=17/2=8.5$

Оновлюємо матрицю $D_{1}$ на нову $D_{2}$ , усереднюючи відстані:

$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}((a,b),e)=22$ — найменше значення, тож з'єднуємо кластер $(a,b)$ та елемент $e$ . Нехай $v$ — вузол, до якого приєднані $(a,b)$ та $e$ :

$\delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11$

Виводимо недостатню довжину гілки:

$\delta (u,v)=\delta (e,v)-\delta (a,u)=11-8.5=2.5$

Оновлюємо матрицю пропорційним усередненням:

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

$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_{3}(c,d)=28$ — найменше значення, тож з'єднуємо $c$ та $d$ . Нехай $w$ — вузол, до якого приєднані $c$ та $d$ :

$\delta (c,w)=\delta (d,w)=28/2=14$

$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+36)/2=33$

Останній крок

З'єднуємо кластери $((a,b),e)$ та $(c,d)$ . Нехай $r$ — кореневий вузол:

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

Виводимо дві решти довжин гілок:

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

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

Дендрограма ультраметрична, бо всі кінці ( $a$ – $e$ ) рівновіддалені від $r$ .

Порівняння з іншими зв'язками

Альтернативні схеми зв'язку включають кластеризацію з одинарним зв'язком, кластеризацію з повним зв'язком та середній зв'язок WPGMA. Реалізація іншого зв'язку — лише питання використання іншої формули для обчислення міжкластерних відстаней. Кластеризація з повним зв'язком уникає недоліку одинарного зв'язку — так званого ефекту ланцюжка.

Застосування

В екології це один з найпопулярніших методів класифікації одиниць вибірки на основі їхніх попарних схожостей. В біоінформатиці UPGMA використовують для створення фенетичних дерев (фенограм). Нині його найчастіше використовують для побудови напрямних дерев для складніших алгоритмів, наприклад у процедурах вирівнювання послідовностей. У філогенетиці UPGMA передбачає сталу швидкість еволюції (гіпотеза молекулярного годинника) і не є добре визнаним методом виведення зв'язків, якщо це припущення не перевірено.

Див. також

Примітки

Посилання

Sokal, Robert R.; Michener, Charles D. (1958). A statistical method for evaluating systematic relationships. University of Kansas Science Bulletin. 38: 1409—1438.
Оригінальна стаття в англійській Вікіпедії