UPGMA - UPGMA - Wikipedia

UPGMA (metoda neváženého páru s aritmetickým průměrem) je jednoduchá aglomerace (zdola nahoru) hierarchické shlukování metoda. Metoda je obecně přičítána Sokal a Michener.^[1]

Metoda UPGMA je podobná metodě vážený varianta, WPGMA metoda.

Všimněte si, že nevážený člen naznačuje, že všechny vzdálenosti přispívají rovnoměrně ke každému průměru, který je počítán, a neodkazuje na matematiku, jíž je dosaženo. Jednoduché průměrování ve WPGMA tedy vytváří vážený výsledek a proporcionální průměrování v UPGMA vytváří nevážený výsledek (viz pracovní příklad ).^[2]

Algoritmus

Algoritmus UPGMA vytváří zakořeněný strom (dendrogram ), která odráží strukturu přítomnou v páru matice podobnosti (nebo a matice odlišnosti V každém kroku se nejbližší dva klastry spojí do klastru vyšší úrovně. Vzdálenost mezi libovolnými dvěma klastry ${ displaystyle { mathcal {A}}}$ a ${ displaystyle { mathcal {B}}}$, každá o velikosti (tj., mohutnost ) ${ displaystyle {| { mathcal {A}} |}}$ a ${ displaystyle {| { mathcal {B}} |}}$, je považován za průměr všech vzdáleností ${ displaystyle d (x, y)}$ mezi dvojicemi předmětů ${ displaystyle x}$ v ${ displaystyle { mathcal {A}}}$ a ${ displaystyle y}$ v ${ displaystyle { mathcal {B}}}$, tj. Střední vzdálenost mezi prvky každého klastru:

${ displaystyle {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 vytváření klastrů aktualizovaná vzdálenost mezi spojenými klastry ${ displaystyle { mathcal {A}} pohár { mathcal {B}}}$ a nový klastr ${ displaystyle X}$ je dáno proporcionálním průměrováním ${ displaystyle d _ {{ mathcal {A}}, X}}$ a ${ displaystyle d _ {{ mathcal {B}}, X}}$ vzdálenosti:

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

Algoritmus UPGMA vytváří zakořeněné dendrogramy a vyžaduje předpoklad konstantní rychlosti - to znamená, že předpokládá ultrametrický strom, ve kterém jsou vzdálenosti od kořene ke každému konci větve stejné. Když hroty jsou molekulární data (tj., DNA, RNA a protein ), které byly odebrány současně, ultrametricita předpoklad se stává ekvivalentem předpokladu a molekulární hodiny.

Pracovní příklad

Tento pracovní příklad je založen na a JC69 genetická matice vzdálenosti počítaná z 5S ribozomální RNA seřazení sekvencí pěti bakterií: Bacillus subtilis (${ displaystyle a}$), Bacillus stearothermophilus (${ displaystyle b}$), Lactobacillus viridescens (${ displaystyle c}$), Acholeplasma modicum (${ displaystyle d}$), a Micrococcus luteus (${ displaystyle e}$).^[3][4]

První krok

• První shlukování

Předpokládejme, že máme pět prvků ${ displaystyle (a, b, c, d, e)}$ a následující matice ${ displaystyle D_ {1}}$ párových vzdáleností mezi nimi:

V tomto příkladu ${ displaystyle D_ {1} (a, b) = 17}$ je nejmenší hodnota ${ displaystyle D_ {1}}$, takže spojujeme prvky ${ displaystyle a}$ a ${ displaystyle b}$.

• Odhad délky první větve

Nechat ${ displaystyle u}$ označte uzel, ke kterému ${ displaystyle a}$ a ${ displaystyle b}$ jsou nyní připojeni. Nastavení ${ displaystyle delta (a, u) = delta (b, u) = D_ {1} (a, b) / 2}$ zajišťuje, že prvky ${ displaystyle a}$ a ${ displaystyle b}$ jsou ve stejné vzdálenosti od ${ displaystyle u}$. To odpovídá očekávání ultrametricita hypotéza. Spojení větví ${ displaystyle a}$ a ${ displaystyle b}$ na ${ displaystyle u}$ pak mají délky ${ displaystyle delta (a, u) = delta (b, u) = 17/2 = 8,5}$ (viz závěrečný dendrogram )

• První aktualizace matice vzdálenosti

Poté pokračujeme v aktualizaci počáteční matice vzdálenosti ${ displaystyle D_ {1}}$ do nové matice vzdálenosti ${ displaystyle D_ {2}}$ (viz níže), zmenšená o jeden řádek a jeden sloupec kvůli shlukování ${ displaystyle a}$ s ${ displaystyle b}$Tučné hodnoty v ${ displaystyle D_ {2}}$ odpovídají novým vzdálenostem vypočítaným podle průměrné vzdálenosti mezi každým prvkem prvního klastru ${ displaystyle (a, b)}$ a každý ze zbývajících prvků:

${ displaystyle D_ {2} ((a, b), c) = (D_ {1} (a, c) krát 1 + D_ {1} (b, c) krát 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 }$

Kurzíva hodnoty v ${ displaystyle D_ {2}}$ nejsou ovlivněny aktualizací matice, protože odpovídají vzdálenostem mezi prvky, které nejsou zahrnuty v prvním klastru.

Druhý krok

• Druhé shlukování

Nyní zopakujeme tři předchozí kroky, počínaje novou maticí vzdálenosti ${ displaystyle D_ {2}}$

Tady, ${ displaystyle D_ {2} ((a, b), e) = 22}$ je nejmenší hodnota ${ displaystyle D_ {2}}$, takže se připojíme ke klastru ${ displaystyle (a, b)}$ a prvek ${ displaystyle e}$.

• Odhad délky druhé větve

Nechat ${ displaystyle v}$ označte uzel, ke kterému ${ displaystyle (a, b)}$ a ${ displaystyle e}$ jsou nyní připojeni. Z důvodu omezení ultrametricity se větve spojují ${ displaystyle a}$ nebo ${ displaystyle b}$ na ${ displaystyle v}$, a ${ displaystyle e}$ na ${ displaystyle v}$ jsou stejné a mají následující délku:${ Displaystyle delta (a, proti) = delta (b, v) = delta (e, v) = 22/2 = 11}$

Dedukujeme délku chybějící větve:${ Displaystyle delta (u, proti) = delta (e, proti) - delta (a, u) = delta (e, v) - delta (b, u) = 11-8,5 = 2,5}$ (viz závěrečný dendrogram )

• Aktualizace druhé matice vzdálenosti

Poté pokračujeme v aktualizaci ${ displaystyle D_ {2}}$ do nové matice vzdálenosti ${ displaystyle D_ {3}}$ (viz níže), zmenšená o jeden řádek a jeden sloupec kvůli shlukování ${ displaystyle (a, b)}$ s ${ displaystyle e}$. Tučné hodnoty v ${ displaystyle D_ {3}}$ odpovídají novým vzdálenostem vypočítaným podle proporcionální průměrování:

${ displaystyle D_ {3} (((a, b), e), c) = (D_ {2} ((a, b), c) krát 2 + D_ {2} (e, c) krát 1) / (2 + 1) = (25,5 krát 2 + 39 krát 1) / 3 = 30}$

Díky tomuto proporcionálnímu průměru odpovídá výpočet této nové vzdálenosti větší velikosti ${ displaystyle (a, b)}$ shluk (dva prvky) s ohledem na ${ displaystyle e}$ (jeden prvek). Podobně:

${ displaystyle D_ {3} (((a, b), e), d) = (D_ {2} ((a, b), d) krát 2 + D_ {2} (e, d) krát 1) / (2 + 1) = (32,5 krát 2 + 43 krát 1) / 3 = 36}$

Proporcionální průměrování proto dává stejnou váhu počátečním vzdálenostem matice ${ displaystyle D_ {1}}$. To je důvod, proč metoda je 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 opakujeme tři předchozí kroky, počínaje aktualizovanou maticí vzdálenosti ${ displaystyle D_ {3}}$.

Tady, ${ displaystyle D_ {3} (c, d) = 28}$ je nejmenší hodnota ${ displaystyle D_ {3}}$, takže spojujeme prvky ${ displaystyle c}$ a ${ displaystyle d}$.

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

Nechat ${ displaystyle w}$ označte uzel, ke kterému ${ displaystyle c}$ a ${ displaystyle d}$ jsou nyní připojeny ${ displaystyle c}$ a ${ displaystyle d}$ na ${ displaystyle w}$ pak mají délky ${ Displaystyle delta (c, w) = delta (d, w) = 28/2 = 14}$ (viz závěrečný dendrogram )

• Aktualizace třetí matice vzdálenosti

Je třeba aktualizovat jeden záznam, který má na paměti tyto dva prvky ${ displaystyle c}$ a ${ displaystyle d}$ každý má příspěvek ve výši ${ displaystyle 1}$ v průměrný výpočet:

${ displaystyle D_ {4} ((c, d), ((a, b), e)) = (D_ {3} (c, ((a, b), e)) krát 1 + D_ {3 } (d, ((a, b), e)) krát 1) / (1 + 1) = (30 krát 1 + 36 krát 1) / 2 = 33}$

Poslední krok

Finále ${ displaystyle D_ {4}}$ matice je:

Takže se připojujeme ke klastrům ${ displaystyle ((a, b), e)}$ a ${ displaystyle (c, d)}$.

Nechat ${ displaystyle r}$ označit (kořenový) uzel, ke kterému ${ displaystyle ((a, b), e)}$ a ${ displaystyle (c, d)}$ jsou nyní připojeny ${ displaystyle ((a, b), e)}$ a ${ displaystyle (c, d)}$ na ${ displaystyle r}$ pak mají délky:

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

Dedukujeme dvě zbývající délky větví:

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

Dendrogram UPGMA

Dendrogram je nyní dokončen.^[5] Je to ultrametrické, protože všechny tipy (${ displaystyle a}$ na ${ displaystyle e}$) jsou ve stejné vzdálenosti od ${ displaystyle r}$ :

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

Dendrogram je tedy zakořeněn pomocí ${ displaystyle r}$, jeho nejhlubší uzel.

Srovnání s jinými vazbami

Mezi alternativní schémata propojení patří shlukování s jediným spojením, kompletní shlukování vazeb, a Průměrné shlukování propojení WPGMA. Implementace jiného propojení je jednoduše otázkou použití jiného vzorce pro výpočet meziklastrových vzdáleností během kroků aktualizace matice vzdálenosti výše uvedeného algoritmu. Kompletní shlukování vazeb se vyhne nevýhodě alternativní metody shlukování jednoho propojení - tzv fenomén řetězení, kde mohou být klastry vytvořené prostřednictvím seskupení s jednou vazbou vynuceny společně kvůli tomu, že jednotlivé prvky jsou blízko u sebe, i když mnoho prvků v každém klastru může být od sebe velmi vzdálených. Kompletní propojení má tendenci najít kompaktní shluky přibližně stejných průměrů.^[6]

Porovnání dendrogramů získaných různými klastrovacími metodami ze stejného matice vzdálenosti.

Seskupování pomocí jednoho propojení.	Kompletní shlukování.	Průměrné shlukování vazeb: WPGMA.	Průměrné shlukování vazeb: UPGMA.

Použití

• v ekologie, je to jedna z nejpopulárnějších metod pro klasifikaci jednotek vzorkování (například vegetačních ploch) na základě jejich párových podobností v příslušných proměnných deskriptorů (jako je druhové složení).^[7] Například se používá k pochopení trofické interakce mezi mořskými bakteriemi a protisty.^[8]
• v bioinformatika, UPGMA se používá pro vytvoření fenetický stromy (fenogramy). UPGMA byl původně navržen pro použití v elektroforéza bílkovin studií, ale v současné době se nejčastěji používá k výrobě vodicích stromů pro sofistikovanější algoritmy. Tento algoritmus se používá například v zarovnání sekvence postupy, protože navrhuje jedno pořadí, ve kterém budou sekvence zarovnány. Cílem průvodce je seskupit nejpodobnější sekvence bez ohledu na jejich evoluční rychlost nebo fylogenetické spříznění, a to je přesně cíl UPGMA.^[9]
• v fylogenetika, UPGMA předpokládá konstantní rychlost vývoje (hypotéza molekulárních hodin ) a že všechny sekvence byly vzorkovány současně a nejde o dobře pokládanou metodu pro odvození vztahů, pokud tento předpoklad nebyl testován a odůvodněn pro použitý soubor dat. Všimněte si, že ani za „přísných hodin“ by sekvence vzorkované v různých časech neměly vést k ultrametrickému stromu.

Časová složitost

Triviální implementace algoritmu pro konstrukci stromu UPGMA má ${ displaystyle O (n ^ {3})}$ časová složitost a použití haldy pro každý klastr k udržení jeho vzdáleností od jiného klastru snižuje jeho čas na ${ displaystyle O (n ^ {2} log n)}$. Fionn Murtagh představil některé další přístupy pro speciální případy, a ${ displaystyle O (k3 ^ {k} n ^ {2})}$ časový algoritmus Day a Edelsbrunner^[10] pro k-rozměrná data, která jsou optimální ${ displaystyle O (n ^ {2})}$ pro konstantu k a další ${ displaystyle O (n ^ {2})}$ algoritmus pro omezené vstupy, když „aglomerační strategie splňuje vlastnost redukovatelnosti“.^[11]

Viz také

• Soused se připojil
• Shluková analýza
• Seskupování pomocí jednoho propojení
• Kompletní shlukování
• Hierarchické shlukování
• Modely evoluce DNA
• Molekulární hodiny

Reference

externí odkazy

• Implementace klastrového algoritmu UPGMA v Ruby (AI4R)
• Příklad výpočtu UPGMA pomocí matice podobnosti
• Příklad výpočtu UPGMA pomocí matice vzdálenosti