전체 링크 클러스터링

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "완전한 링크 클러스터링" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

완전 연계 클러스터링은 집적 계층적 클러스터링의 몇 가지 방법 중 하나이다.공정의 시작에서 각 원소는 그 자체의 군집 안에 있다.그런 다음 모든 요소가 동일한 클러스터에 포함될 때까지 클러스터는 순차적으로 더 큰 클러스터로 결합된다.이 방법은 가장 먼 이웃 군집화라고도 알려져 있다.군집화 결과는 덴드로그램으로 시각화할 수 있는데, 군집 융합의 순서와 각 융화가 일어난 거리를 보여준다.^[1][2][3]

군집화 절차

각 단계에서 가장 짧은 거리로 분리된 두 군집이 결합된다.'가장 짧은 거리'의 정의는 서로 다른 응집성 군집화 방법을 구별하는 것이다.완전한 링크 군집화에서, 두 군집 사이의 연결은 모든 요소 쌍을 포함하며, 군집 사이의 거리는 서로 가장 멀리 떨어져 있는 두 요소 사이의 거리(각 군집마다 한 개씩)와 같다.어떤 단계에 머물러 있는 이들 링크 중 가장 짧은 연결은 요소들이 관여하는 두 군집의 융합을 야기한다.

Mathematically, the complete linkage function — the distance ${\displaystyle D(X,Y)}$ between clusters ${\displaystyle X}$ and ${\displaystyle Y}$ — is described by the following expression : ${\displaystyle D(X,Y)=\max _{x\in X,y\in Y}d(x,y)}$

어디에

• ${\displaystyle d}$( ${\displaystyle x}$, y${\displaystyle }$) ${\displaystyle d(x,y)}$은(는) $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle x\in$ X$}$과(는${\displaystyle )}$ y $\$ Y {\$displaystyle y\in$ Y};$$ 사이의 거리이다$$.
• ${\displaystyle X}$ ${\displaystyle X}$ 및$$ $Y{\displaystyle }$ ${\displaystyle Y}$은 두 가지 요소(클러스터) 집합이다.

알고리즘

순진한 계획

다음 알고리즘은 기존 클러스터가 새로운 클러스터로 병합되면서 근접 행렬의 행과 열을 지우는 응집형 구조다.$N{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle N}$ ${\displaystyle$ N$\times$ N$}$ 근접$$ 행렬 D에는 모든 거리 d(i,j)가 포함되어 있다.군집에는 시퀀스 번호 0,1,......, (n - 1)가 할당되며 L(k)은 k번째 군집화 수준이다.시퀀스 번호 m의 클러스터는 (m)으로 표시되고, 클러스터(r)와 (s) 사이의 근접성은 d[(r),(s)로 표시된다.

완전한 링크 클러스터링 알고리즘은 다음 단계로 구성된다.

1. ${\displaystyle \mathrm{레벨}}$ L${\displaystyle }$( ${\displaystyle 0}$)${\displaystyle }$= 0 ${\displaystyle$ L$(0)=0}$ 및 시퀀스$$ 번호 ${\displaystyle \mathrm{m}}$= 0 ${\displaystyle m=0}$을(를) 갖는 분리형 클러스터링으로 시작하십시오$.$
2. $d$${\displaystyle }$[${\displaystyle }$( ${\displaystyle r}$)${\displaystyle }$$,{\displaystyle }$(${\displaystyle s}$)$$, ( s ) , ( s${\displaystyle )}$에 따라 ${\displaystyle \mathrm{현재}}$ ${\displaystyle 클러스터링}$에서 ${\displaystyle \mathrm{가장}}$ 유사한${\displaystyle }$클러스터 ${\displaystyle 쌍}$을 찾으십시오. d [ ( r ) ,${\displaystyle }$( ) =$$$min$ d ${\displaystyle [}$ ( i${\displaystyle }$)${\displaystyle }$, ( ${\displaystyle j)]}$ ${\displaystyle$ d$[(r)],$ ( ) = ( ) = ] = #$min d[i,$ $(j)}.$
3. 시퀀스 번호: $m{\displaystyle }$= ${\displaystyle m}$+ ${\displaystyle 1}$ ${\displaystyle m=m+1$}을$($를) 증분하십시오$.$클러스터$({\displaystyle r}$) ${\displaystyle(r)}$ 및 $({\displaystyle s}$) ${\displaystyle(s)}$을(를) 단일 클러스터로$$ 병합하여 다음 클러스터링 $m{\displaystyle }$ ${\$$displaystyle$ $m$${\displaystyle \}}$을(를) 형성하십시오$.$ 이 클러스터링의 $수준$을 $($ ${\displaystyle )}$= d$r)],$로 설정하십시오$.$
4. 클러스터$({\displaystyle r}$) ${\displaystyle(r)}$ 및${\displaystyle }$(${\displaystyle s)}$ ${\displaystyle(s)}$에 해당하는 행과 열을 삭제하고 새로$$ 구성된 클러스터에 해당하는 행과 열을 추가하여 $D{\displaystyle }$ ${\displaystyle D$ 근접 행렬을 업데이트하십시오.The proximity between the new cluster, denoted ${\displaystyle (r,s)}$ and old cluster ${\displaystyle (k)}$ is defined as ${\displaystyle d[(r),(s)]=\max\{d[(k),(r)],d[(k),(s)]\}}$.
5. 모든 개체가 하나의 클러스터에 있으면 중지하십시오.그렇지 않으면 2단계로 이동하십시오.

최적 효율적 계획

위에서 설명한 알고리즘은 이해하기 쉽지만 복잡성 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3$ 1976년 5월 D.디파이즈는 단일 링크 클러스터링에 대한 유사한 알고리즘 SLINK에서 영감을 받아 CLINK (1977년 발행)^[4]로 알려진$$ 복잡성 $O{\displaystyle }$ (${\displaystyle {n\mathrm{}}^{}}$2 $){\displaystyle$O$(n^{2})$만 최적으로 효율적인 알고리즘을 제안했다.

이 구간은 확장이 필요하다.추가하면 도움이 된다.(2011년 10월)

작업 예제

작업 예는 5S 리보솜 RNA 시퀀스 정렬에서 계산된 JC69 유전자 거리 매트릭스를 기반으로 한다.바실러스 아열대($$${\displaystyle }$ subilis, ${\$$displaystyle$ $a}),$ 바실러스 스타어터모필루스(${\displaystyle }$ ${\displaystyle b}),$ 유산균 바이러스덴스(${\displaystyle }$ ${\displaystyle$ $c$$}),$ 아콜레플라즈마모디쿰(${\displaystyle }$ ${\$d$}),$ 마이크로코커스 루테우스($e}).$^[5][6]

1단계

• 첫 번째 군집화

5개 요소$({\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c,}$ ${\displaystyle d,}$ $){\displaystyle(a,b,c,d,e)}$와 그 요소들 사이의 쌍방향 거리의 다음$$ $행렬{\displaystyle {}_{}}$ ${\displaystyle {D1\mathrm{}}_{}}${\$displaystyle D_{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 {D\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$( ${\displaystyle a}$, ${\displaystyle b}$)${\displaystyle }$= ${\displaystyle 17}$ ${\displaystyle D_{1}(a$$,$$b$$)=17}$의 가장 작은 ${\displaystyle {값}_{}}$이므로$,$ ${\displaystyle a}$ 및$$ $b{\displaystyle }$ ${\displaystyle b}$ 요소에 $가입$한다$.$

• 첫 번째 분기 길이 추정

$u{\displaystyle }$ ${\displaystyle u}$이(가) $현재{\displaystyle }${\$displaystyle a}$과(와) b$${\$displaystyle b$}이$$(가) 연결된 노드를 나타내도록$$ 하십시오.설정 Δ${\displaystyle }$( ${\displaystyle a}$ ,${\displaystyle u}$)${\displaystyle }$= ${\displaystyle {\Delta \mathrm{}}_{}}$( b ,${\displaystyle u}$ ${\displaystyle )}$= ${\displaystyle {}_{}}$ 1${\displaystyle {}_{}}$( ${\displaystyle a}$, ${\displaystyle b}$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \delta (a,u)=\delta (b,u)=$$D\_{\displaystyle }$${1}(a,b)/2$}은$($는$)$ ${\displaystyle$ a$}$$$및 b {\$displaystyle$ b$$} $요소$가$u$ {\displaystyle $u}$로부터 동일하도록 보장한다$.$이는 초경량 가설의 예상에 해당한다.$그러면{\displaystyle }$$$ ${\displaystyle a}$ $및{\displaystyle }$ b$$ ${\displaystyle b}$을(를) $u{\displaystyle }$ ${\displaystyle u$${\displaystyle \}}$에 결합하는 분기의 길이 Δ${\displaystyle (,u}$)${\displaystyle }$= ${\displaystyle 17}$/ ${\displaystyle 2}$= 8${\displaystyle .5}$ ${\displaysty \delta(a,u)=17/2=8.5}($최종 덴드로그램 참조).$$

• 첫 번째 거리 행렬 업데이트

그런 다음 초기 근접 ${\displaystyle {매트릭스\mathrm{}}_{}}$ D$$1 {\$displaystyle D_{$1}를 새로운 $근접$ $D$ 2 {\$displaystyle$D_{2}}($아래{\displaystyle }$ 참조$).$ b {\$displaystyle$ b$}$을$($를) $가진$ {\$displaystyle$ a$}$의 클러스터링으로 인해 크기가 한 행과 한 열로 축소됨$.$ $D{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$에서 굵은 값$_{2$}는 첫 번째 군집$({\displaystyle }$ $a$, $b$)의 각 요소와 $나머지$ 각 요소 사이의 최대 거리를 유지하여 계산한 새로운 거리에 해당한다$.$

${\displaystyle D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c)=max(21,30)=30}$

${\displaystyle D_{2}(a,b),d)=max(D_{1}(a,d),D_{1}(b,d)=max(31,34)=34}$

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

$D{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}의 기울임꼴로 표시된 값은 첫 번째 군집에 포함되지 않은 요소 사이의 거리에 해당하므로 행렬 업데이트의 영향을 받지 않는다$$.

두 번째 단계

• 두 번째 군집화

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

	(a,b)	c	d	e
(a,b)	0	30	34	23
c	30	0	28	39
d	34	28	0	43
e	23	39	43	0

여기서 $D{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle (,}$ ${\displaystyle b}$)${\displaystyle }$, ${\displaystyle e}$)${\displaystyle }$= ${\displaystyle 23}$ ${\displaystyle D_{2}((a,b),e)=$$23}$의 가장 낮은 $값이므로$, 우리는 $클러스터{\displaystyle }$${\displaystyle (,}$ ${\displaystyle b}$ )${\displaystyle }$${\$$displaystyle$ $e}$ 요소와$$ 함께 클러스터(, b ) {\$displaystystyle$$(a,b)}$에 가입한다$.$

• 두 번째 분기 길이 추정

$v{\displaystyle }$ ${\displaystyle v}$이(${\displaystyle 가}$)${\displaystyle }$( ,${\displaystyle b}$) ${\displaystyle (a,b)}$ 및 $e$ ${\displaystyle e}$이(가) 연결된 노드를$$ 나타내도록 하십시오$$.Because of the ultrametricity constraint, the branches joining ${\displaystyle a}$ or ${\displaystyle b}$ to ${\displaystyle v}$, and ${\displaystyle e}$ to ${\displaystyle v}$, are equal and have the following total length: ${\displaystyle \delt$$a (a,v)=\cHB(b,v)=\cHB(e,v)=23/2=11.5}$

We deduce the missing branch length: ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3}$ (see the final dendrogram)

• 2차 거리 매트릭스

그런 다음 D ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}$$매트릭스를$$ 새로운 거리 매트릭스 ${\displaystyle {D\mathrm{}}_{}}$ 3 ${\$ D_${3}($아래 참조)로 업데이트하고$,{\displaystyle }$ $e{\displaystyle }$ ${\displaystyle e}$과${\displaystyle (,}$ ${\displaystyle b}$)$${\$displaystystyle (a,b)$의 클러스터링으로 인해 크기가 한 행과 한 열로 축소된다.$$

${\displaystyle D_{3}((a,b),e),c)=max(D_{2}(a,b),c),D_{2}(e,c)=max(30,39)=39}$

${\displaystyle D_{3}((a,b),e),d)=max(D_{2}(a,b),d),D_{2}(e,d)=max(34,43)=43}$

세 번째 단계

• 세 번째 군집화

업데이트된 거리 매트릭스 $D{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$에서 시작하여 이전 세 단계를 다시 반복한다$.$

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

여기서 $D{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$( c${\displaystyle }$, ${\displaystyle d}$)${\displaystyle }$= ${\displaystyle 28}$ ${\displaystyle D_{3}(c,d)=28}$은 D ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 가장 작은$$값이기$$ 때문에 요소 $c{\displaystyle }$ ${\displaystyle c}$ 및 $d$ ${\displaystyd}$에 가입한다$.$

• 세 번째 분기 길이 추정

$w{\displaystyle }$ ${\displaystyle w}$이(가) $c{\displaystyle }$ ${\displaystyle c}$ 및 $d{\displaystyle }$ ${\displaystyle d}$이(가) 연결된$$ 노드를 나타내도록 하십시오.$c{\displaystyle }$$$ ${\displaystyle c}$ 및 d ${\displaystyle d}$을(를) $w{\displaystyle }$ ${\displaystyle w}$에 연결하는 분기의 길이는 Δ${\displaystyle (c}$, ${\displaystyle w}$)${\displaystyle }$= ${\displaystyle 28}$/ ${\displaystyle 2\mathrm{}}$= ${\displaystyle 14}$ ${\displaysty \delta(c,w)=28/2=14}($마지막 덴드로그램 참조)$$

• 3차 거리 행렬 업데이트

There is a single entry to update: ${\displaystyle D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43}$

최종 단계

최종 $D{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$ 행렬은$$ 다음과 같다.

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

그래서 우리는 ${\displaystyle \mathrm{클러스터}}{\displaystyle }$(${\displaystyle a}$, ${\displaystyle b}$)${\displaystyle }$, e${\displaystyle }$) ${\displaystyle ((a,b),e)}$과$({\displaystyle c}$, ${\displaystyle d}$) ${\displaystyle (c,d)}$을(를) 결합한다$.$

$r{\displaystyle }$ ${\displaystyle r}$이(가${\displaystyle )}{\displaystyle }$(${\displaystyle }$, ${\displaystyle b}$)${\displaystyle }$, e${\displaystyle }$) ${\displaystyle ((a,b),e)}$ 및$$${\displaystyle }$(${\displaystyle c}$ ${\displaystyle ,}$d )$${\$displaystyle (c,d)}$이(가) 연결되는 (root) 노드를 나타내도록$$ 한다.$($ ${\displaystyle (,}$ ${\displaystyle b}$)${\displaystyle }$, ${\displaystyle e}$) {\$displaystyle ((a,b),e)}$ 및${\displaystyle }$( ,${\displaystyle d}$ )${\displaystyle }${\d) ${\d$ 디스플레이style $(c,d)}$을(를) r ${\displaystyle$ r$}$에 결합하는 분기의 길이는 다음과$$ 같다.

${\displaystyle \property ((a,b),e),r)=\property(c,d),r)=43/2=21.5}$

남은 두 가지 가지 가지 길이를 추론해 봅시다.

${\displaystyle \cHB(v,r)=\cHB((a,b,e),r)-\cHB(e,v)=21.5-11.5=10}$

${\displaystyle \property(w,r)=\property(c,d),r)-\properties(c,w)=21.5-14=7.5}$

전체 링크 덴드로그램

덴드로그램은 이제 완성되었다.모든 팁$({\displaystyle a}$ ~ $e$ ${\displaystyle e$이 r ${\displaystyle r}:$

$\d,r=\displaystyle \cHB=\displaystyle \b,r)=\display(b,r)=\display(c,r)=21.5}$

따라서 덴드로그램은 가장 깊은 노드인$$$r{\displaystyle }$ ${\displaystyle r}$에 의해 뿌리를 내린다.

다른 링크와의 비교

대안적 연결 체계에는 단일 연결 클러스터링과 평균 연결 클러스터링이 포함된다. 순진한 알고리즘에서 다른 연결을 구현하는 것은 단순히 근접 매트릭스의 초기 계산과 위의 알고리즘의 4단계에서 클러스터 간 거리를 계산하기 위해 다른 공식을 사용하는 것이다.그러나 임의의 연결에는 최적으로 효율적인 알고리즘을 사용할 수 없다.조정해야 할 수식은 굵은 텍스트를 사용하여 강조 표시했다.

완전한 연결 클러스터링은 비록 각 클러스터의 많은 요소들이 서로 매우 멀리 떨어져 있더라도 단일 연결 클러스터링을 통해 형성된 클러스터들이 서로 가까이 있기 때문에 함께 강제될 수 있는 소위 체인 현상이라는 대안적인 단일 연결 방법의 단점을 피한다.완전한 연결은 대략 같은 직경의 콤팩트한 군집을 찾는 경향이 있다.^[7]

동일한 거리 행렬에서 다른 군집화 방법으로 얻은 덴드로그램 비교.

단일 링크 클러스터링.	전체 링크 클러스터링	평균 연결 클러스터링: WPGMA	평균 연결 클러스터링: UPGMA.

참고 항목

• 군집 분석
• 계층적 군집화
• 분자시계
• 인접 결합
• 단일 링크 클러스터링
• UPGMA
• WPGMA

참조

추가 읽기

• Späth H (1980). Cluster Analysis Algorithms. Chichester: Ellis Horwood.