WPGMA - WPGMA

WPGMA (Žosmý Pvzduch Group Mzpůsob s Arithmetic Mean) je jednoduchý aglomerát (zdola nahoru) hierarchické shlukování metoda, obecně připisovaná Sokal a Michener.^[1]

Metoda WPGMA je podobná té její nevážený varianta, UPGMA metoda.

Algoritmus

Algoritmus WPGMA vytvoří kořenový strom (dendrogram ), která odráží strukturu přítomnou v páru matice vzdálenosti (nebo a matice podobnosti ). V každém kroku řekněme nejbližší dva klastry ${ displaystyle i}$ a ${ displaystyle j}$, jsou sloučeny do klastru vyšší úrovně ${ displaystyle i cup j}$. Pak jeho vzdálenost k dalšímu klastru ${ displaystyle k}$ je prostě aritmetický průměr průměrných vzdáleností mezi členy ${ displaystyle k}$ a ${ displaystyle i}$ a ${ displaystyle k}$ a ${ displaystyle j}$ :

${ displaystyle d _ {(i cup j), k} = { frac {d_ {i, k} + d_ {j, k}} {2}}}$

Algoritmus WPGMA vytváří zakořeněné dendrogramy a vyžaduje předpoklad konstantní rychlosti: produkuje ultrametrický strom, ve kterém jsou vzdálenosti od kořene ke každému konci větve stejné. Tento ultrametricita předpoklad se nazývá molekulární hodiny když tipy zahrnují DNA, RNA a protein data.

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}$).^[2][3]

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) + D_ {1} (b, c)) / 2 = (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}}$ matice 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}$ :${ displaystyle D_ {3} (((a, b), e), c) = (D_ {2} ((a, b), c) + D_ {2} (e, c)) / 2 = ( 25,5 + 39) /2=32,25}$

Za zmínku stojí toto průměrný výpočet nové vzdálenosti nepočítá s větší velikostí ${ 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) + D_ {2} (e, d)) / 2 = ( 32,5 + 43) /2=37,75}$

Postup zprůměrování proto dává diferenciální váhu počátečním vzdálenostem matice ${ displaystyle D_ {1}}$. To je důvod, proč metoda je váž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. Větve se připojují ${ 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 jednu položku:${ displaystyle D_ {4} ((c, d), ((a, b), e)) = (D_ {3} (c, ((a, b), e)) + D_ {3} (d , ((a, b), e))) / 2 = (32,25 + 37,75) / 2 = 35}$

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) = 35/2 = 17,5})$

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

${ Displaystyle delta (v, r) = delta (((a, b), e), r) - delta (e, v) = 17,5-11 = 6,5}$

${ Displaystyle delta (w, r) = delta ((c, d), r) - delta (c, w) = 17,5-14 = 3,5}$

Dendrogram WPGMA

Dendrogram je nyní dokončen. 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) = 17,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 UPGMA klastrování průměrného propojení. 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ů.^[4]

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.

Viz také

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

Reference