UPGMA

UPGMA (unweighted pair group method with arithmetic mean; česky metoda neváženého párování s aritmetickým průměrem) je jednoduchá aglomerativní hierarchická shluková metoda (jde o tzv. bottom-up metodu, kdy se nejprve shlukují páry sobě nejpodobnější, které se následně shlukují až do konečné sítě). Metodu představili Sokal a Michener.

Termín nevážená metoda nesouvisí s matematickým výpočtem, ale odkazuje na skutečnost, že všechny distance se podílejí stejnou měrou na výpočtu každého průměru. Metoda UPGMA má i alternativu váženého párování, která se nazývá WPGMA. +more WPGMA generuje výsledky na základně jednoduchého průměru vzdáleností (neboli distancí), zatímco u nevážené metody UPGMA se používá k výpočtu proporcionální průměr (viz pracovní příklad).

Algoritmus

Algoritmus UPGMA vytváří zakořeněný strom (tzv. dendrogram), který odráží strukturu matice podobností (nebo matice odlišností). +more V každém kroku jsou dva nejpodobnější klastry sloučeny do klastru vyšší úrovně. Vzdálenost mezi každými dvěma klastry \mathcal{A} a \mathcal{B} o velikosti (neboli mohutnosti)

\mathcal{A}

a [wiki_table=b8d7682a] je vypočítána jako průměr všech vzdáleností d(x,y) mezi páry prvků x v \mathcal{A} a y v \mathcal{B}, tzn. jako střední vzdálenost mezi prvky každého klastru:.

:: {1 \over

\mathcal{A}|\cdot|\mathcal{B}

}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y)

Jinými slovy, v každém kroku se aktualizuje vzdálenost mezi nově spojenými klastry \mathcal{A} \cup \mathcal{B} a novým clustrem X. Aktualizovaná vzdálenost je dána proporcionálním průměrem vzdáleností d_{\mathcal{A},X} a 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}

Algoritmus UPGMA vytváří zakořeněné dendrogramy, při jejichž tvorbě předpokládá konstantní podíly - to znamená, že předpokládá tzv. ultrametrický strom, ve kterém jsou vzdálenosti od kořene ke konci každé větve stejné. +more Pokud jsou základem pro tvorbu stromu molekulární data (tj. DNA, RNA nebo proteiny) odebraná ve stejný čas, ultrametricita se stane ekvivalentem molekulárních hodin.

Pracovní příklad

Tento pracovní příklad je založen na matici genetických distancí JC69, která je odvozená z alignmentu sekvencí 5S ribozomální RNA pěti bakterií: Bacillus subtilis (a), Bacillus stearothermophilus (b), Lactobacillus viridescens (c), Acholeplasma modicum (d) a Micrococcus luteus (e).

První krok

První shlukování (klastrování)

Předpokládejme, že máme pět prvků (a,b,c,d,e) uspořádaných v následující matici párových vzdáleností D_1:

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

Protože je v této matici je nejmenší hodnotou D_1 (a,b)=17, v prvním kroku spojíme prvky a a b.

* Odhad délky první větve

Písmenem u označme uzel, ve kterém se nyní spojují prvky a a b. Díky rovnici \delta(a,u)=\delta(b,u)=D_1(a,b)/2 je zajištěno, že prvky a a b jsou stejně vzdálené od u. +more To odpovídá hypotéze ultrametricity. Větve obou prvků a a b vedoucí k uzlu u tedy mají délku \delta(a,u)=\delta(b,u)=17/2=8. 5 (viz výsledný dendrogram).

* První aktualizace matice vzdáleností

Poté přistoupíme k aktualizaci počáteční matice D_1 na novou matici D_2 (viz níže), která bude zmenšená o jeden řádek a jeden sloupec kvůli seskupování a s b v předchozím kroku. Nové hodnoty vzdáleností odpovídají průměru vzdáleností mezi každým prvkem prvního klastru (a,b) a každým ze zbývajících prvků:

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

Nově vypočtené hodnoty vzdáleností v matici D_2 jsou vyznačeny tučně. Hodnoty psané kurzívou v matici D_2 nebyly změněny oproti původní matici D_1, protože jde o vzdálenosti mezi prvky, které nebyly zahrnuty do prvního klastru.

Druhý krok

Druhé shlukování

Nyní zopakujeme tři předchozí kroky, počínaje tvorbou nové matice vzdálenosti D_2

	(a, b)	c	d	e
(a, b)	0	25. 5	32. +more5	22
c	25. 5	0	28	39
d	32. 5	28	0	43
e	22	39	43	0

V této matici je nejmenší hodnotou D_2 ((a,b),e)=22, proto ke klastru (a,b) připojíme prvek e.

* Odhad délky druhé větve

Označme uzel spojující klastr (a,b) a prvek e písmenem v. Kvůli ultrametricitě musí mít větve spojující klastr (a, b) a e v uzlu v stejnou délku: \delta(a,v)=\delta(b,v)=\delta(e,v)=22/2=11

Délku nové větve vypočteme následovně: \delta(u,v)=\delta(e,v)-\delta(a,u)=\delta(e,v)-\delta(b,u)=11-8.5=2.5 (viz výsledný dendrogram)

* Druhá aktualizace matice vzdáleností

Poté přistoupíme k aktualizaci matice D_2 na novou distanční matici D_3 (viz níže), zmenšenou o jeden řádek a jeden sloupec kvůli vzniku nového klastru (a,b) a e. Tučně zvýrazněné hodnoty v D_3 odpovídají novým vzdálenostem, vypočteným na základně proporcionálního průměru:

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

Výpočet nové vzdálenosti pomocí proporcionálního průměru umožňuje vzít v potaz větší velikost klastru (a,b - dva prvky) s ohledem na e (jeden prvek). Podobně vypočteme zbývající vzdálenost:

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

Proporcionální průměr tedy dává stejnou váhu všem počátečním vzdálenostem matice D_1. To je důvod, proč je metoda nevážená - ne s ohledem na matematický postup, ale s ohledem na počáteční vzdálenosti.

Třetí krok

Třetí shlukování

Znovu zopakujeme tři předchozí kroky, přičemž nejprve vytvoříme novou matici vzdáleností D_3.

	((a, b), e)	c	d
((a, b), e)	0	30	36
c	30	0	28
d	36	28	0

Nejmenší hodnotou této matice je D_3 (c,d)=28, takže spojíme prvky c a d .

* Odhad délky třetí větve

Písmenem w označme uzel, který spojuje prvky c a d. Větve spojující c a d v uzlu w pak mají délku \delta(c,w)=\delta(d,w)=28/2=14 (viz výsledný dendrogram)

* Třetí aktualizace matice vzdáleností

Nyní je třeba aktualizovat jen jednu hodnotu, přičemž je třeba mít na paměti, že každý z prvků c a d přispívají k výpočtu průměru hodnotou 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

Poslední krok

Finální matice D_4 je následující:

	((a, b), e)	(c,d)
((a, b), e)	0	33
(c,d)	33	0

Spojili jsme tudíž oba klastry ((a,b),e) a (c,d).

Písmenem r označme (kořenový) uzel, ve kterém spojíme klastry ((a,b),e) a (c,d). Větve klastrů ((a,b),e) a (c,d) vedoucí k uzlu r pak mají délky:

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

Vypočteme délky dvou zbývajících větví:

\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

Výsledný dendrogram UPGMA

400x400pixelů Dendrogram je nyní dokončen. +more Je ultrametrický, protože všechny konce větví (od a po e) jsou stejně vzdálené od uzlu r:.

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

Dendrogram je proto zakořeněn nejhlubším uzlem r, který je nazýván kořen.

Porovnání s jinými algoritmy

Alternativní klastrovací schémata zahrnují single linkage clustering (metoda nejbližšího souseda, jednospojná metoda), complete linkage clustering (metoda nejvzdálenějšího souseda, všespojná metoda) a WPGMA. Jednotlivé algoritmy se mezi sebou liší použitím jiných postupů při výpočtu vzdáleností mezi klastry v rámci tvorby nové matice. +more Nevýhodou nejjednodušší metody single linkage clustering je tzv. chaining phenomenon, při kterém dochází ke shlukování klastrů na základě jediného společného charakteru přestože jsou si jednotlivé prvky v klastru obecně nepodobné. Algoritmus Complete linkage clustering dokáže tuto nevýhodu řešit a tvoří klastry o přibližně stejných diametrech.

Single-linkage clustering	Complete-linkage clustering	Average linkage clustering: WPGMA	Average linkage clustering: UPGMA

.

Použití

Jde o jednu z nejpopulárnějších metod v ekologii. Požívá se pro klasifikaci vzorků (jako jsou např. +more vegetační snímky) na základě párových podobností jejich vlastností (jako je např. druhové složení). Mimo vegetační data může sloužit také například k pochopení trofické interakce mezi mořskými bakteriemi a protisty. * V bioinformatice se UPGMA používá k tvorbě fenetických stromů (fenogramů). Metoda UPGMA byla původně navržena pro studie založené na proteinové elektroforéze, ale v současné době se nejčastěji používá k výpočtu vodících stromů pro sofistikovanější algoritmy. Tento algoritmus se používá například při výpočtu alignmentu sekvencí, kdy se na jeho základě tvoří pořadí, ve kterém budou sekvence alignovány. Vodící strom založený na UPGMA seskupuje nejpodobnějších sekvencí bez ohledu na jejich evoluční vývoj nebo fylogenetickou afinitu. * Při použití metody UPGMA ve fylogenetice se předpokládá konstantní rychlost evoluce (tzv. hypotéza molekulárních hodin) a že všechny vzorky byly odebrány současně. Nicméně se nepovažuje za vhodnou metodu pro odvozování fylogenetických vztahů. Metodu lze použít pouze pokud byly zmíněné předpoklady testovány a dobře zdůvodněny. Je důležité si uvědomit, že strom vytvořený na základě vzorků odebraných v různých časech by neměl vést k ultrametrickému stromu, dokonce i za podmínky „strict clock“.

Časová složitost

Základní použití UPGMA algoritmu ke konstrukci stromu má časovou komplexitu O(n^3). Pokud použijeme pro každý klastr haldu, abychom jednotlivé klastry udželi ve vzdálenosti od ostatních, redukujeme čas na O(n^2 \log n). +more Fionn Murtagh představil nějaké další přístupy pro speciální případy: časový algoritmus O(k3^kn^2) podle Day a Edelsbrunner pro k-dimensionální data, kde je optimální O(n^2) pro konstantní k, a další algoritmus O(n^2) pro omezené vstupy, pokud „shlukovací strategie vyhovuje reducibilitě“.

Odkazy

Reference

Související články

Shluková analýza * Hierarchické seskupování * Molekulární hodiny

Externí odkazy

[url=https://github. com/SergioFierens/ai4r/blob/master/lib/ai4r/clusterers/average_linkage. +morerb]Implementace klastrovacího algoritmu UPGMA v Ruby (AI4R)[/url] * [url=https://books. google. com/books. id=KBoHuoNRO5MC&pg=PA319&lpg=PA319&dq=UPGMA+clustering&source=bl&ots=9t_4R2kFgr&sig=c4jHFEouGm-KCxbg9lwKQZNnWcQ&hl=de&ei=G7kqSo_wFc2Rsga86MyeDA&sa=X&oi=book_result&ct=result&resnum=3]Příklad výpočtu UPGMA pomocí matice podobnosti[/url] * [url=http://www. slimsuite. unsw. edu. au/teaching/upgma/]Příklad výpočtu UPGMA pomocí distanční matice[/url].

Kategorie:Bioinformatika Kategorie:Shluková analýza