Изворни код странице УПГМА

'''УПГМА''' ({{јез-ен|'''U'''nweighted '''P'''air '''G'''roup '''M'''ethod with '''A'''rithmetic Mean}}) представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су [[екологија]] и [[биоинформатика]]. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.

УПГМА конструише филогенетско стабло са кореном ([[дендрограм]]) који описује структуру [[матрица сличности]] ( или матрица различитости ).

У сваком кораку, два најбижа кластера се комбинују у већи. Растојање између било која два кластера А и Б представља просек свих растојања између парова објеката "x" из A и "y" из B.
::<math> {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y)</math>

Конструкцију алгоритма описали су Sokal и Michener.<ref>{{cite journal |author=Sokal R and Michener C |title=A statistical method for evaluating systematic relationships |journal=University of Kansas Science Bulletin |volume=38 |pages=1409ֱ438 |year=1958}}</ref> Fionn Murtagh је описао оптимални <math>O(n^2)</math> алогоритам за конструкцију УПГМА стабла.<ref>{{cite journal |last=F|first=Murtagh|title=Complexities of Hierarchic Clustering Algorithms: the state of the art |journal=Computational Statistics Quarterly |volume=1 |pages=101ֱ13 |year=1984}}</ref>


== Алгоритам ==
# Доделити сваки таксон сопственом кластеру
# Дефинисати један лист за сваки таксон и поставити га на висину 0
# Све док има више од два кластера
# Одредити два кластера са најмањим растојањем <math>d(i,j)</math>
# Дефинисати нови кластер <math> C_k = C_i \cup C_k </math>
# Дефинисати чвор к са потомцима i и ј и поставити га на висину <math>d(i,j)/2</math>
# Заменити кластере i и j кластером к
# Израчунати растојање између к и осталих кластера
# Спојити последња два кластера i и j кореном на висини <math>d(i,j)/2</math>

== Пример ==
Нека је задата следећа матрица растојања:
{| class="wikitable" style="text-align:center; width:100px; height:100px;"
|+ 
|-
!
! А
! B
! C
! D
! E
! F
|-
! B
| 2 
|-
! C
| 4 || 4 
|-
! D
| 6 || 6 || 6
|-
! E
| 6 || 6 || 6 || 4
|-
! F
| 8 || 8 || 8 || 8 || 8 || 8
|}
Бирамо два таксона са најмањим растојањем. То су А и B. Висина дрвета је <math> d(A,B)/2 = 2/2 = 1 </math>



Рачунамо растојање новог кластера АB у односу на преостале таксоне.
{| class="wikitable" style="text-align:center; width:100px; height:100px;"
|+ 
|-
!
! АB
! C
! D
! E
|-
! C
| 4
|-
! D
| 6 || 6
|-
! E
| 6 || 6 || 4
|-
! F
| 8 || 8 || 8 || 8 
|}
Таксони са најмањим растојањем су D и E. Висина дрвета је <math> d(D,E)/2 = 4/2 = 2 </math>



Рачунамо растојање новог кластера DE у односу на преостале таксоне.
{| class="wikitable" style="text-align:center; width:100px; height:100px;"
|+ 
|-
!
! АB
! C
! DЕ
|-
! C
| 4
|-
! DЕ
| 6 || 6
|-
! F
| 8 || 8 || 8
|}
Висина дрвета: <math> d(C,AB)/2 = 4/2 = 2 </math>





Рачунамо растојање новог кластера ABC у односу на преостале таксоне.
{| class="wikitable" style="text-align:center; width:100px; height:100px;"
|+ 
|-
!
! АBC
! DЕ
|-
! DE
| 6
|-
! F
| 8 || 8
|}
Висина дрвета: <math> d(ABC,DE)/2 = 6/2 = 3 </math>




Рачунамо растојање новог кластера ABCDE у односу на преостале таксоне.
{| class="wikitable" style="text-align:center; width:100px; height:100px;"
|+ 
|-
!
! АBCDE
|-
! F
| 8
|}
Висина дрвета: <math> d(ABCDE,F)/2 = 8/2 = 4 </math>

== Види још ==
* [[Спајање суседа]]
* [[Кластер анализа]]
* [[Хијерархијско кластеровање]]
* [[Молекуларни сат]]

== Референце ==
{{reflist}}

{{нормативна контрола}}

[[Категорија:Informatika]]