УПГМА

УПГМА (енгл. Unweighted Pair Group Method with Arithmetic Mean) представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су екологија и биоинформатика. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.

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

У сваком кораку, два најбижа кластера се комбинују у већи. Растојање између било која два кластера А и Б представља просек свих растојања између парова објеката "x" из A и "y" из B.

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

Конструкцију алгоритма описали су Sokal и Michener.^[1] Fionn Murtagh је описао оптимални $O(n^{2})$ алогоритам за конструкцију УПГМА стабла.^[2]

Алгоритам[уреди | уреди извор]

Доделити сваки таксон сопственом кластеру
Дефинисати један лист за сваки таксон и поставити га на висину 0
Све док има више од два кластера
Одредити два кластера са најмањим растојањем $d(i,j)$
Дефинисати нови кластер $C_{k}=C_{i}\cup C_{k}$
Дефинисати чвор к са потомцима i и ј и поставити га на висину $d(i,j)/2$
Заменити кластере i и j кластером к
Израчунати растојање између к и осталих кластера
Спојити последња два кластера i и j кореном на висини $d(i,j)/2$

Пример[уреди | уреди извор]

Нека је задата следећа матрица растојања:


	А	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. Висина дрвета је $d(A,B)/2=2/2=1$

Рачунамо растојање новог кластера АB у односу на преостале таксоне.


	АB	C	D	E
C	4
D	6	6
E	6	6	4
F	8	8	8	8

Таксони са најмањим растојањем су D и E. Висина дрвета је $d(D,E)/2=4/2=2$

Рачунамо растојање новог кластера DE у односу на преостале таксоне.


	АB	C	DЕ
C	4
DЕ	6	6
F	8	8	8

Висина дрвета: $d(C,AB)/2=4/2=2$

Рачунамо растојање новог кластера ABC у односу на преостале таксоне.


	АBC	DЕ
DE	6
F	8	8

Висина дрвета: $d(ABC,DE)/2=6/2=3$

Рачунамо растојање новог кластера ABCDE у односу на преостале таксоне.


	АBCDE
F	8

Висина дрвета: $d(ABCDE,F)/2=8/2=4$

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

^ Sokal R and Michener C (1958). „A statistical method for evaluating systematic relationships”. University of Kansas Science Bulletin. 38: 1409ֱ438.
^ F, Murtagh (1984). „Complexities of Hierarchic Clustering Algorithms: the state of the art”. Computational Statistics Quarterly. 1: 101ֱ13.

[1] Sokal R and Michener C (1958). „A statistical method for evaluating systematic relationships”. University of Kansas Science Bulletin. 38: 1409ֱ438.

[2] F, Murtagh (1984). „Complexities of Hierarchic Clustering Algorithms: the state of the art”. Computational Statistics Quarterly. 1: 101ֱ13.

[1]

[2]