UPGMA - UPGMA - Wikipedia

UPGMA (o'rtacha arifmetikasi bilan vaznsiz juftlik usuli) oddiy aglomerativ (pastdan yuqoriga) ierarxik klasterlash usul. Usul odatda bog'liqdir Sokal va Michener.^[1]

UPGMA usuli unga o'xshaydi vaznli variant, the WPGMA usul.

E'tibor bering, o'lchovsiz atama barcha masofalar hisoblangan har bir o'rtacha qiymatga teng ravishda qo'shilishini anglatadi va unga erishilgan matematikani nazarda tutmaydi. Shunday qilib, WPGMA-da oddiy o'rtacha vaznli natijani va UPGMA-da mutanosib o'rtacha o'lchovsiz natijani beradi (ishlaydigan misolga qarang ).^[2]

Algoritm

UPGMA algoritmi ildiz otgan daraxtni yaratadi (dendrogram ) mavjud tuzilishni juftlik shaklida aks ettiradi o'xshashlik matritsasi (yoki a o'xshashlik matritsasi Har bir qadamda eng yaqin ikkita klaster yuqori darajadagi klasterga birlashtiriladi. Har qanday ikkita klaster orasidagi masofa ${ displaystyle { mathcal {A}}}$ va ${ displaystyle { mathcal {B}}}$, har bir o'lcham (ya'ni, kardinallik ) ${ displaystyle {| { mathcal {A}} |}}$ va ${ displaystyle {| { mathcal {B}} |}}$, barcha masofalarning o'rtacha qiymati sifatida qabul qilinadi ${ displaystyle d (x, y)}$ juft narsalar orasidagi ${ displaystyle x}$ yilda ${ displaystyle { mathcal {A}}}$ va ${ displaystyle y}$ yilda ${ displaystyle { mathcal {B}}}$, ya'ni har bir klaster elementlari orasidagi o'rtacha masofa:

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

Boshqacha qilib aytganda, har bir klaster bosqichida birlashtirilgan klasterlar orasidagi yangilangan masofa ${ displaystyle { mathcal {A}} cup { mathcal {B}}}$ va yangi klaster ${ displaystyle X}$ ning mutanosib o'rtacha qiymati bilan berilgan ${ displaystyle d _ {{ mathcal {A}}, X}}$ va ${ displaystyle d _ {{ mathcal {B}}, X}}$ masofalar:

${ 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 algoritmi ildiz otgan dendrogramlarni ishlab chiqaradi va doimiy stavka bo'yicha taxminni talab qiladi, ya'ni u ultrametrik ildizdan har bir novdaning uchiga qadar bo'lgan masofalar teng bo'lgan daraxt. Maslahatlar molekulyar ma'lumotlar bo'lganda (ya'ni, DNK, RNK va oqsil ) bir vaqtning o'zida namuna olingan ultrametriklik taxmin taxmin qilish bilan baravar bo'ladi molekulyar soat.

Ish namunasi

Ushbu ishlaydigan misol a ga asoslangan JC69 dan hisoblangan genetik masofa matritsasi 5S ribosomal RNK beshta bakteriyalarning ketma-ketligi: Bacillus subtilis (${ displaystyle a}$), Bacillus stearothermophilus (${ displaystyle b}$), Laktobatsillus viridescens (${ displaystyle c}$), Acholeplasma modikum (${ displaystyle d}$) va Micrococcus luteus (${ displaystyle e}$).^[3][4]

Birinchi qadam

• Birinchi klaster

Keling, bizda beshta element bor deb taxmin qilaylik ${ displaystyle (a, b, c, d, e)}$ va quyidagi matritsa ${ displaystyle D_ {1}}$ ular orasidagi juftlik masofalari:

Ushbu misolda, ${ displaystyle D_ {1} (a, b) = 17}$ ning eng kichik qiymati ${ displaystyle D_ {1}}$, shuning uchun biz elementlarga qo'shilamiz ${ displaystyle a}$ va ${ displaystyle b}$.

• Birinchi filial uzunligini taxmin qilish

Ruxsat bering ${ displaystyle u}$ tugunni belgilang ${ displaystyle a}$ va ${ displaystyle b}$ endi ulangan. O'rnatish ${ displaystyle delta (a, u) = delta (b, u) = D_ {1} (a, b) / 2}$ elementlarning ishlashini ta'minlaydi ${ displaystyle a}$ va ${ displaystyle b}$ dan teng masofada joylashgan ${ displaystyle u}$. Bu kutganga mos keladi ultrametriklik gipoteza ${ displaystyle a}$ va ${ displaystyle b}$ ga ${ displaystyle u}$ keyin uzunliklarga ega bo'ling ${ displaystyle delta (a, u) = delta (b, u) = 17/2 = 8.5}$ (yakuniy dendrogramga qarang )

• Birinchi masofa matritsasini yangilash

Keyin dastlabki masofa matritsasini yangilashga kirishamiz ${ displaystyle D_ {1}}$ yangi masofa matritsasiga ${ displaystyle D_ {2}}$ (pastga qarang), klasterlanganligi sababli hajmi bir qatorga va bitta ustunga qisqartirilgan ${ displaystyle a}$ bilan ${ displaystyle b}$.Qalin qiymatlar ${ displaystyle D_ {2}}$ tomonidan hisoblab chiqilgan yangi masofalarga mos keladi masofalarni o'rtacha hisoblash birinchi klasterning har bir elementi o'rtasida ${ displaystyle (a, b)}$ va qolgan elementlarning har biri:

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

Kursatilgan qiymatlar ${ displaystyle D_ {2}}$ matritsaning yangilanishi ularga ta'sir qilmaydi, chunki ular birinchi klasterda qatnashmagan elementlar orasidagi masofaga to'g'ri keladi.

Ikkinchi qadam

• Ikkinchi klaster

Endi yangi masofa matritsasidan boshlab, avvalgi uchta qadamni takrorlaymiz ${ displaystyle D_ {2}}$

Bu yerda, ${ displaystyle D_ {2} ((a, b), e) = 22}$ ning eng kichik qiymati ${ displaystyle D_ {2}}$, shuning uchun biz klasterga qo'shilamiz ${ displaystyle (a, b)}$ va element ${ displaystyle e}$.

• Ikkinchi filial uzunligini taxmin qilish

Ruxsat bering ${ displaystyle v}$ tugunni belgilang ${ displaystyle (a, b)}$ va ${ displaystyle e}$ endi ulangan. Ultrametriklik cheklanganligi sababli filiallar birlashadi ${ displaystyle a}$ yoki ${ displaystyle b}$ ga ${ displaystyle v}$va ${ displaystyle e}$ ga ${ displaystyle v}$ teng va quyidagi uzunlikka ega:${ displaystyle delta (a, v) = delta (b, v) = delta (e, v) = 22/2 = 11}$

Yo'qolgan filial uzunligini chiqaramiz:${ displaystyle delta (u, v) = delta (e, v) - delta (a, u) = delta (e, v) - delta (b, u) = 11-8.5 = 2.5}$ (yakuniy dendrogramga qarang )

• Ikkinchi masofa matritsasini yangilash

Keyin yangilashga o'tamiz ${ displaystyle D_ {2}}$ yangi masofa matritsasiga ${ displaystyle D_ {3}}$ (pastga qarang), klasterlanganligi sababli hajmi bir qatorga va bitta ustunga qisqartirilgan ${ displaystyle (a, b)}$ bilan ${ displaystyle e}$. Qalin qiymatlar ${ displaystyle D_ {3}}$ tomonidan hisoblab chiqilgan yangi masofalarga mos keladi mutanosib o'rtacha:

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

Ushbu mutanosib o'rtacha qiymat tufayli ushbu yangi masofani hisoblash katta o'lchamlarni tashkil etadi ${ displaystyle (a, b)}$ nisbatan klaster (ikkita element) ${ displaystyle e}$ (bitta element). Xuddi shunday:

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

Shuning uchun mutanosib o'rtacha matritsaning boshlang'ich masofalariga teng og'irlik beradi ${ displaystyle D_ {1}}$. Bu usulning sababi shu vaznsiz, matematik protseduraga nisbatan emas, balki dastlabki masofalarga nisbatan.

Uchinchi qadam

• Uchinchi klasterlash

Yangilangan masofa matritsasidan boshlab yana uchta qadamni takrorlaymiz ${ displaystyle D_ {3}}$.

Bu yerda, ${ displaystyle D_ {3} (c, d) = 28}$ ning eng kichik qiymati ${ displaystyle D_ {3}}$, shuning uchun biz elementlarga qo'shilamiz ${ displaystyle c}$ va ${ displaystyle d}$.

• Uchinchi filial uzunligini taxmin qilish

Ruxsat bering ${ displaystyle w}$ tugunni belgilang ${ displaystyle c}$ va ${ displaystyle d}$ endi ulangan. Filiallar birlashmoqda ${ displaystyle c}$ va ${ displaystyle d}$ ga ${ displaystyle w}$ keyin uzunliklarga ega bo'ling ${ displaystyle delta (c, w) = delta (d, w) = 28/2 = 14}$ (yakuniy dendrogramga qarang )

• Uchinchi masofa matritsasini yangilash

Ikkala elementni yodda tutgan holda, yangilanish uchun bitta yozuv mavjud ${ displaystyle c}$ va ${ displaystyle d}$ har birining hissasi bor ${ displaystyle 1}$ ichida o'rtacha hisoblash:

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

Yakuniy qadam

Final ${ displaystyle D_ {4}}$ matritsa:

Shunday qilib, biz klasterlarga qo'shilamiz ${ displaystyle ((a, b), e)}$ va ${ displaystyle (c, d)}$.

Ruxsat bering ${ displaystyle r}$ (root) tugunini belgilang ${ displaystyle ((a, b), e)}$ va ${ displaystyle (c, d)}$ endi ulangan. Filiallar birlashmoqda ${ displaystyle ((a, b), e)}$ va ${ displaystyle (c, d)}$ ga ${ displaystyle r}$ keyin uzunliklarga ega bo'ling:

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

Qolgan ikkita filial uzunligini chiqaramiz:

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

Dendrogram endi tugallandi.^[5] Bu ultrametrik, chunki barcha maslahatlar (${ displaystyle a}$ ga ${ displaystyle e}$) dan teng masofada joylashgan ${ displaystyle r}$ :

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

Shuning uchun dendrogram ildiz otgan ${ displaystyle r}$, uning eng chuqur tuguni.

Boshqa aloqalar bilan taqqoslash

Shu bilan bir qatorda bog'lanish sxemalari bitta bog'lanish klasteri, to'liq bog'lanish klasteri va WPGMA o'rtacha bog'lanish klasteri. Boshqa bog'lanishni amalga oshirish shunchaki yuqoridagi algoritmning masofa matritsasini yangilash bosqichlari davomida klasterlararo masofalarni hisoblash uchun boshqa formuladan foydalanish masalasidir. To'liq bog'lanish klasteri muqobil bitta bog'lash klasterlash usulining kamchiliklarini oldini oladi - deb ataladi zanjirli hodisa, bu erda bitta bog'lanish klasteri orqali hosil bo'lgan klasterlar bitta elementlar bir-biriga yaqin bo'lganligi sababli birlashtirilishi mumkin, garchi har bir klasterdagi ko'plab elementlar bir-biriga juda uzoq bo'lsa ham. To'liq bog'lanish taxminan teng diametrdagi ixcham klasterlarni topishga intiladi.^[6]

Bir xildan turli xil klasterlash usullari bo'yicha olingan dendrogramlarni taqqoslash masofa matritsasi.

Bitta havolali klasterlash.	To'liq bog'lanish klasteri.	O'rtacha bog'lanish klasteri: WPGMA.	O'rtacha bog'lanish klasteri: UPGMA.

Foydalanadi

• Yilda ekologiya, bu namunaviy birliklarni (masalan, o'simlik uchastkalari) tegishli tavsiflovchi o'zgaruvchilardagi juftlik o'xshashliklari asosida (masalan, turlar tarkibi) tasniflashning eng mashhur usullaridan biridir.^[7] Masalan, dengiz bakteriyalari va protistlar o'rtasidagi trofik o'zaro ta'sirni tushunish uchun foydalanilgan.^[8]
• Yilda bioinformatika, Yaratish uchun UPGMA ishlatiladi fenetik daraxtlar (fenogrammalar). UPGMA dastlab foydalanish uchun mo'ljallangan edi oqsil elektroforezi tadqiqotlar olib boradi, ammo hozirgi vaqtda ko'pincha murakkab algoritmlar uchun qo'llanma daraxtlarini ishlab chiqarish uchun foydalaniladi. Ushbu algoritm, masalan, ketma-ketlikni tekislash protseduralar, chunki u ketma-ketliklarni tekislash tartibini taklif qiladi. Darhaqiqat, yo'riq daraxti evolyutsion tezligi yoki filogenetik yaqinligidan qat'i nazar, eng o'xshash ketma-ketliklarni birlashtirishga qaratilgan va bu aynan UPGMA ning maqsadi^[9]
• Yilda filogenetik, UPGMA doimiy evolyutsiyani nazarda tutadi (molekulyar soat gipotezasi ) va barcha ketma-ketliklar bir vaqtning o'zida namuna olinganligi va agar bu taxmin sinovdan o'tmagan va ishlatilgan ma'lumotlar to'plami uchun asoslanmagan bo'lsa, munosabatlar xulosasi uchun yaxshi ko'rib chiqilgan usul emas. E'tibor bering, "qat'iy soat" ostida ham turli vaqtlarda olingan ketma-ketliklar ultrametrik daraxtga olib kelmasligi kerak.

Vaqtning murakkabligi

UPGMA daraxtini qurish algoritmini ahamiyatsiz amalga oshirish mavjud ${ displaystyle O (n ^ {3})}$ vaqtning murakkabligi va har bir klaster uchun boshqa klasterdan masofani saqlash uchun uyumdan foydalanish uning vaqtini qisqartiradi ${ displaystyle O (n ^ {2} log n)}$. Fionn Murtag maxsus holatlar bo'yicha ba'zi boshqa yondashuvlarni taqdim etdi, a ${ displaystyle O (k3 ^ {k} n ^ {2})}$ Day va Edelsbrunner tomonidan vaqt algoritmi^[10] optimal bo'lgan k o'lchovli ma'lumotlar uchun ${ displaystyle O (n ^ {2})}$ doimiy k uchun va boshqasi ${ displaystyle O (n ^ {2})}$ cheklangan yozuvlar algoritmi, "aglomerativ strategiya pasayish xususiyatini qondirganda".^[11]

Shuningdek qarang

• Qo'shni qo'shilish
• Klaster tahlili
• Bitta havolali klasterlash
• To'liq bog'lanish klasteri
• Ierarxik klasterlash
• DNK evolyutsiyasining modellari
• Molekulyar soat

Adabiyotlar

Tashqi havolalar

• Ruby (AI4R) da UPGMA klaster algoritmini amalga oshirish
• O'xshashlik matritsasi yordamida UPGMA-ni hisoblash
• Masofa matritsasi yordamida UPGMA-ni hisoblash