업그마

UPGMA(산술 평균을 사용한 가중치 없는 쌍 그룹 방법)는 단순한 집적(상향식) 계층 군집화 방법입니다.이 방법은 일반적으로 Sokal과 Michener에 ^[1]기인한다.

UPGMA 방식은 WPGMA 방식과 유사합니다.

가중치 없는 항은 모든 거리가 계산되는 각 평균에 동일하게 기여함을 나타내며, 이 평균이 달성되는 산술은 참조하지 않습니다.따라서 WPGMA의 단순 평균은 가중 결과를 생성하고 UPGMA의 비례 평균은 가중되지 않은 결과를 생성한다(작업 ^[2]예 참조).

알고리즘.

UPGMA 알고리즘은 쌍별 유사도 매트릭스(또는 차등도 매트릭스)에 존재하는 구조를 반영하는 루트 트리(덴드로그램)를 구성합니다.각 단계에서 가장 가까운 두 군집이 더 높은 수준의 군집으로 결합됩니다.크기(즉, 카디널리티)${\displaystyle }{\displaystyle A\mathcal{}}$(\$displaystyle {\mathcal {A}})$ ${\displaystyle 및}$ $(\$$displaystyle${\mathcal {B}})의 두 $클러스터{\displaystyle \mathcal{}}$A$(\displaystyle$ {\$mathcal$ {B$})$와 $B(\$displaystyle {\mathcal {$B$ 사이의$$ 거리는 모든 $거리{\displaystyle (x)}$의 평균이 됩니다.$A$$(\$의 $객체{\displaystyle }$ 쌍$$x(\$displaystyle$x$)$와 B$$$(\$ {$B$의 y$(\displaystyle$ y$)$ 사이의$$ {\displaystyle d$(x,y),$ 즉 각 클러스터의 요소 간 평균 거리$:$

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

즉, 각 클러스터 단계에서 결합된 $클러스터{\displaystyle \mathcal{}}$ A${\displaystyle b\mathcal{}}$B {\$displaystyle {$$A}\cup$${\mathcal$ {B$}}$과$($$)$ $새로운{\displaystyle }$ 클러스터$$X {\$displaystyle$ X$}$ 사이의$$ 업데이트된 거리는 ${\displaystyle {A\mathcal{},}_{}}$ $,$ $X,$ ${\displaystyle {\mathrm{DIS}}_{}}$의 $비례{\displaystyle {}_{}}$ 평균에 의해 결정됩니다.$ystyle d_{\mathcal {B}},X}$ 거리$$:

$({displaystyle d_{\mathcal {A}}, X}, X} = flac {\mathcal {A}, X} + {\mathcal {B}, X} \cdot d_{\mathcal {B}, X} + {\mathcal {B})$

UPGMA 알고리즘은 루트 덴드로그램을 생성하며 일정한 비율의 가정이 필요하다. 즉, 루트로부터 모든 분기 팁까지의 거리가 동일한 초변형 트리를 가정한다.팁이 동시에 샘플링된 분자 데이터(DNA, RNA 및 단백질)인 경우, 초측정성 가정은 분자 시계를 가정하는 것과 같아진다.

작업 예

이 작업 예는 5개 세균의 5S 리보솜 RNA 배열 정렬에서 계산한 JC69 유전자 거리 매트릭스에 기초한다.$(\$$displaystyle$ a), ${\displaystyle }$(\$displaystyle$ b$),$ 락토바실루스 $(\style$ c$),$ $(\displaystyle$ d$),$ 마이크로코커스 $(\displaystyle$ e$)$^[3][4]

제1단계

• 첫 번째 클러스터링

5개의 요소$, b, c, d,$ $)$와 그 사이의 쌍방향 거리 $매트릭스{\displaystyle {}_{}}$ $($1})이$$$$ 있다고 가정합니다.

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

이 예에서는 ${\displaystyle {D1\mathrm{}}_{}a,}$ ${\displaystyle b)}$ $=$ ${\displaystyle 17}$({$displaystyle$ $D_{$$1}(a,$b)=$17)$이 ${\displaystyle {D1}_{}}$의$최소값{\displaystyle {}_{}}$({$1$이므로 $요소$와 $({displaystyle$ b$\})$를 결합합니다.

• 첫 번째 분기 길이 추정

$u$ { $displaystyle$u }는$$ \$displaystyle$ a$}$ $및$ b {$displaystyle$ b$}$가 현재 연결되어 있는 $노드$를 나타냅니다.${\displaystyle \mathrm{설정}}$ ${\displaystyle (}$ (${\displaystyle }$a ,${\displaystyle u}$ ) ${\displaystyle =\delta }$ (${\displaystyle }$b ,${\displaystyle u}$ ) ${\displaystyle =}$ ${\displaystyle {}_{}{1\mathrm{}}_{}}$ (${\displaystyle a}$ ,${\displaystyle b}$) /$$ ( \ $displaystyle \ display$ ($a$ , u ) = \$displaystyle$ ($a$ , u ) $=$D_${1}(a,b)/2를 사용$하면 $요소$$$$a와$$$$b$가$u$와$$등거리에 있음을 확인할 수 있습니다.이것은 초파형성 가설의 기대와 일치한다.$이어{\displaystyle }$ \$displaystyle$ a$$$\$$displaystyle$ b$\$$displaystyle$ u\displaystyle b${\displaystyle \}}$와$$b\displaystyle b$\displaystyle$ u${\displaystyle \backslash \mathrm{displaystyle}}$ $b$.5$}($최종 덴드로그램 참조)의 길이가${\displaystyle \mathrm{됩니다}}$.

• 첫 번째 거리 매트릭스 업데이트

그런 다음 초기 거리 $행렬{\displaystyle {}_{}}$ $(\$을 새로운 거리 $행렬{\displaystyle {}_{}}$ $(\$로 업데이트합니다(아래 참조). $(\${})의 굵은 값은 b$(\displaystyle$ b$)$와 $함께${\$displaystyle$d_${})$로 클러스터링되므로 크기가 1행 및 1열 감소됩니다.2$)}$은 첫 번째 클러스터$({\displaystyle a}$,$b )$의 각 요소와 나머지 각 요소 간의 거리를 평균하여 계산한 새로운 거리에 해당합니다.

$\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=32.5}$

${\displaystyle D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e)/2=(23+21)/2=22}$

$(\$의 기울임꼴 값은 첫 번째 클러스터에 포함되지 않은 요소 간의 거리에 대응하므로 매트릭스 업데이트의 영향을 받지 않습니다.

두 번째 단계

• 세컨드 클러스터링

이제 새로운 거리 $매트릭스{\displaystyle {}_{}}$ ${\displaystyle {D\mathrm{}}_{}}$ 2$({$ D_${2})$부터 시작하여 이전 세 단계를 반복합니다.

	(a, b)	c	d	e
(a, b)	0	25.5	32.5	22
c	25.5	0	28	39
d	32.5	28	0	43
e	22	39	43	0

$여기$서 ${\displaystyle {D2\mathrm{}}_{}}$( (${\displaystyle a}$ ,${\displaystyle }$b${\displaystyle }$) ,${\displaystyle e}$ ) ${\displaystyle =}$ ${\displaystyle 22}$ ${$ { $displaystyle$ $D_{2}$( ( $a$, b ) =$22$$\}$ 은$$ ${\displaystyle {D\mathrm{}}_{}}$ 2$$의 $최소치$이므로, ${\displaystyle \mathrm{클러스터}}{\displaystyle }$( a ,${\displaystyle b}$ $displaystyle ( a$ ,$$b )와 요소 e$$ { $displaystyle$e$\}$ 를 결합합니다.

• 두 번째 분기 길이 추정

$v{\displaystyle }${$displaystyle$ v$}$는 (${\displaystyle a,}$ $)$ {$displaystyle (a, b)}$ $및$ e {$displaystyle$ e$}$가 현재 연결되어 있는${\displaystyle }$노드를 나타냅니다.울트라메트릭성의 제약으로 인해$,$ \$displaystyle$a} $또는$ b {\$displaystyle$b$$}에서$v$ {\$displaystyle$ v$\}($$)$ 및 e {\$displaystyle$$$e}에서 v {\$displaystyle$$$v$}($)로 $결합$하는 브랜치는 동일하며 $길이$가 다음과 같습니다. ${\displaystyle (}$( a , ${\displaystyle v}$ ) $=$b ,${\displaystyle v}$ ) ${\displaystyle =}$ ${\displaystyle 22}$/ 2 ${\displaystyle =}$ $display$ sty ( e${\displaystyle }$, v ) = ${\displaystyle 22}$ / ${\displaystyle 2\mathrm{}}$ = {$$displaystystyle $11$ , $v$= { displaystyle displaystyledisplayst$델타(b,v)=\delta(e,v)=22/2=11}$

$누락$된 분기 길이를 추정합니다. ${\displaystyle (}$ (${\displaystyle u}$ ,${\displaystyle v}$ ) ${\displaystyle =}$( (${\displaystyle e}$ ,${\displaystyle v}$) -${\displaystyle }$) ( ${\displaystyle a}$,${\displaystyle u}$ ) ${\displaystyle =}$( (${\displaystyle e}$ ,${\displaystyle v}$) -${\displaystyle }$( (${\displaystyle b}$ ,${\displaystyle u}$ ) ${\displaystyle =11}$- ${\displaystyle 8}$. ${\displaystyle 5}$ 2.5 \$display$style \ display ($u$ )$=$ \ $display$ style ($e$ , $v$) \ $displan$ ( e , v ) \ $spa$, v ) \ sclan ( e , v ) \ $sclan$ ( $e$, v ) \ sclan ( e , v ) \ sclan ) \ slannel (

• 두 번째 거리 매트릭스 업데이트

그런 다음 $({$$displaystyle D_{$2})를$$ 새로운 거리 $매트릭스{\displaystyle {}_{}}$ $($ 참조)로 $업데이트{\displaystyle {}_{}}$ 합니다${\displaystyle .}$ (${\displaystyle a}$,$$b )${\displaystyle }$\ $displaystyle$(a , $b$) \ displaystyle ( a , b ) $e$ {\eringering eringeringering ${\displaystyle {eringeringering\mathrm{}}_{}}$ {\ （ a , b ) \ $displaystyle$ D _ { 3$$}$$$respond$ in in in in in in in in in in in in in ） $in$ in in in in in in in in in in in in in in in in {\ cor D_{ $displaystyle$ D_ ${$$$displayst비례 평균으로 계산된 새 거리에 대한 계산:

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

이 비례 평균 덕분에 이 새로운 거리는$$e\$displaystyle$e$}($하나의 $$요소)에 대해 (${\displaystyle a,}$ $)\$display style $($a, b)\$display$ (a, b)\display (a, b)\display style (a, b$)$ 클러스터$$$({\displaystyle }$2개 요소)의 더 큰 크기를 차지합니다.마찬가지로:

$\displaystyle D_{3}(((a,b,e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/366)$

따라서 비례 평균은 $매트릭스{\displaystyle {}_{}}$의 초기 거리({$displaystyle D_{1$와 동일한 가중치를 부여합니다.이것이 수학적 절차가 아니라 초기 거리에 대해 방법이 가중치가 부여되지 않는 이유이다.

세 번째 단계

• 세 번째 클러스터링

업데이트된 거리 $매트릭스{\displaystyle {}_{}}$ ${\displaystyle {D\mathrm{}}_{}}$ 3$({$ D_${3$부터 시작하여 이전 세 단계를 다시 설명합니다.

	(a,b,e)	c	d
(a,b,e)	0	30	36
c	30	0	28
d	36	28	0

$여기$서 D ${\displaystyle {3\mathrm{}}_{}}$(${\displaystyle c}$ ,${\displaystyle d}$ ) ${\displaystyle =}$ ${\displaystyle 28}$( \ $displaystyle$ $D$$$_ {$$$3$（$c$ , d$$) $= 28$ )은$$ D$$의 최소값이므로 $요소$$c$와$$d { $displaystyle$$$d$\}$를 $결합$합니다.

• 세 번째 분기 길이 추정

$\displaystyle$w는$$ c$\displaystyle$$c$와 d$\displaystyle$d가 현재$$ 연결되어 있는 $노드$를 나타냅니다.c$${\$displaystyle$ c$}$ 및$$ $d{\displaystyle }${\$displaystyle$ d$}$와$$w {\$displaystyle$ w$}$를 $연결$하는 브런치의 길이는 ${\displaystyle (}$ (${\displaystyle c}$ ,${\displaystyle w}$ ) ${\displaystyle =(}$ ( d${\displaystyle }$,${\displaystyle }$w ) ${\displaystyle =}$ ${\displaystyle 28}$ / ${\displaystyle 2\mathrm{}}$ $=$ ${\displaystyle 14}$ ( $displaystyle$\$displaystyle$ ($c$,$$w ) =$28$/ 2 = 14$$） （ displaystyledisplaystyle ( displaystyle ） ） ） 。

• 세 번째 거리 매트릭스 업데이트

갱신할 엔트리는 1개뿐입니다.단, $2개$의 요소$$$c$와$d$의 평균 계산에서 각각1$(\displaystyle$1)의 기여도를 가지는 것에 주의해 주세요.

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

마지막 단계

$최종{\displaystyle {}_{}}$ $({$4$$}) 매트릭스는 다음과 같습니다.

	(a,b,e)	(c,d)
(a,b,e)	0	33
(c,d)	33	0

${\displaystyle \mathrm{클러스터}}$( ( (${\displaystyle }$a ,${\displaystyle b}$)${\displaystyle }$, e )$${ $displaystyle$( $a$, b$$, e )${\displaystyle }$}${\displaystyle 및}$ (${\displaystyle }$c ,${\displaystyle d}$ ) { $displaystyle ( c$ ,$d$ )$\}$에 접속합니다.

$\displaystyle$r은 (a$$$$${\displaystyle ,}$ ${\displaystyle b}$ ${\displaystyle ),}$ $)$ {$displaystyle (a, b), e}$ 및${\displaystyle }$(${\displaystyle c,}$ $)$ {$displaystyle (c,d)}$이 연결되어 있는 (root) 노드를 나타냅니다.$($ ${\displaystyle a}$,${\displaystyle }$b ${\displaystyle )}$ ,${\displaystyle e}$) { $displaystyle ( a$ ,$b$) $\}{\displaystyle }$ 및$$ (${\displaystyle c}$ ,${\displaystyle d}$) { $displaystyle ( c$ , d$)}$ 를 r$$ { $displaystyle$ r$$} $에$${\displaystyle }$결합하는 브랜치에는 다음과 같은 ${\displaystyle \mathrm{길이}}$가 있습니다.

$\displaystyle \display ( ( ( a , b , e ) , r ) = \display ( ( c , d , r ) = 33 / 2 = 16 . 5 }$

나머지 2개의 분기 길이를 추정합니다.

$\displaystyle \displaystyle (v,r)=\display((a,b,e),r)-\display(e,v)=16.5-11=5.5}$

$\displaystyle \display(w,r)=\display(c,d),r)-\display(c,w)=16.5-14=2.5}$

UPGMA 덴드로그램

덴드로그램이 완료되었습니다.^[5]모든 팁(\$displaystyle$ a$)$에서 e$\displaystyle$ e$)$은$$r\$displaystyle$ r$:$

$\displaystyle \display (a,r)=\display (b,r)=\display (e,r)=\display (c,r)=\display (d,r)=16.5}$

따라서 덴드로그램은 가장 깊은 노드인$$r {\$displaystyle$r}에 $뿌리$를 두고 있습니다.

다른 링크와의 비교

대체 링크 방식으로는 단일 링크 클러스터링, 완전 링크 클러스터링 및 WPGMA 평균 링크 클러스터링이 있습니다.다른 링크의 실장은 상기 알고리즘의 거리 매트릭스 갱신 단계에서 클러스터 간 거리를 계산하기 위해 다른 공식을 사용하는 것에 불과합니다.완전한 링크 클러스터링을 통해 단일 링크 클러스터링을 통해 형성된 클러스터는 각 클러스터의 많은 요소가 서로 매우 멀리 떨어져 있더라도 서로 근접하여 강제로 함께 결합될 수 있는 이른바 체인 현상이라는 대체 단일 링크 클러스터링 방법의 단점을 피할 수 있습니다.완전 연결은 ^[6]지름이 거의 같은 콤팩트한 군집을 찾는 경향이 있습니다.

동일한 거리 행렬에서 서로 다른 클러스터링 방법으로 얻은 덴드로그램 비교.

단일 링크 클러스터링	완전한 링크 클러스터링	평균 링크 클러스터링: WPGMA.	평균 링크 클러스터링: UPGMA.

사용하다

• 생태학에서는 관련 기술자 변수(종 구성 ^[7]등)의 쌍별 유사성에 기초하여 표본 추출 단위(식물도 등)를 분류하는 가장 일반적인 방법 중 하나이다.예를 들어, 그것은 해양 박테리아와 ^[8]원생 동물 사이의 영양적 상호작용을 이해하기 위해 사용되어 왔다.
• 생물정보학에서 UPGMA는 페네틱 트리(phenetic tree)의 생성에 사용됩니다.UPGMA는 처음에는 단백질 전기영동 연구에 사용하도록 설계되었지만, 현재는 보다 정교한 알고리즘을 위한 가이드 트리를 제작하는 데 가장 많이 사용됩니다.예를 들어 이 알고리즘은 시퀀스가 정렬되는 순서를 제안하기 때문에 시퀀스 정렬 절차에서 사용됩니다.실제로, 가이드 트리는 진화 속도나 계통 발생 친화성에 관계없이 가장 유사한 시퀀스를 그룹화하는 것을 목표로 하며, 그것이 바로 UPGMA의^[9] 목표이다.
• 계통유전학에서 UPGMA는 일정한 진화율(분자 클럭 가설)을 가정하고 모든 시퀀스가 동시에 샘플링되었으며, 이 가정이 테스트되고 사용되는 데이터 세트에 대해 정당화되지 않는 한 관계를 추론하는 데 잘 알려진 방법은 아니다.'엄격한 클럭' 하에서도 서로 다른 시간에 샘플링된 시퀀스가 울트라메트릭 트리로 이어지면 안 된다는 점에 유의하십시오.

시간의 복잡성

UPGMA 트리를 구축하기 위한 알고리즘의 간단한 실장에서는${\displaystyle }$O$(n$3)의 시간 복잡도를 $가지며{\displaystyle }$, 각 클러스터에 대해 히프를 사용하여 다른 클러스터와의 거리를 유지하면 O${\displaystyle ({n\mathrm{}}^{}}$ ${\displaystyle 2}$ log${\displaystyle n}$n$$)의 시간이 단축됩니다.{n }\$displaystyle$ O$(n^{$$2$}\$log$n$\}).$ Mion Murtag $2$가 ${\displaystyle {표시}^{}}$됩니다${\displaystyle .}$$aystyle$ O$(n^{2})}$ 시공간$$ 알고리즘.^[10]

「 」를 참조해 주세요.

• 네이버 가입
• 클러스터 분석
• 단일 링크 클러스터링
• 완전한 링크 클러스터링
• 계층 클러스터링
• DNA 진화 모델
• 분자 시계

레퍼런스

외부 링크

• 루비(AI4R)에서의 UPGMA 클러스터링 알고리즘 구현
• 유사도 행렬을 사용한 UPGMA 계산 예제
• 거리 행렬을 사용한 UPGMA 계산 예시