단일 링크 클러스터링
Single-linkage clustering통계에서 단일 링크 클러스터링은 계층적 클러스터링의 여러 방법 중 하나이다.이는 각 단계에서 아직 서로 동일한 클러스터에 속하지 않은 가장 가까운 요소 쌍을 포함하는 두 개의 군집을 결합하여 상향식(집적 군집화) 방식으로 군집을 그룹화하는 것에 기초한다.
이 방법의 단점은 동일한 성단의 주변 요소들이 작은 거리를 갖는 긴 얇은 성단을 생성하는 경향이 있지만 성단의 반대쪽 끝에 있는 요소들은 다른 성단의 두 요소들보다 서로 훨씬 더 멀리 떨어져 있을 수 있다는 것이다.이로 인해 데이터를 유용하게 세분화할 수 있는 클래스를 정의하기가 어려울 수 있다.[1]
응집형 군집화 방법 개요
응집적 군집화 프로세스의 초기에는 각 원소가 자신의 군집 안에 있다.그런 다음 클러스터는 순차적으로 더 큰 클러스터로 결합되며, 모든 요소가 동일한 클러스터에 속하게 된다.각 단계에서 가장 짧은 거리로 분리된 두 군집이 결합된다.연결 함수로 알려진 두 군집 사이의 거리를 결정하는 데 사용되는 함수는 응집성 군집화 방법을 구별하는 것이다.
단일 링크 군집화에서, 두 군집 사이의 거리는 서로 가장 가까운 두 요소(각 군집마다 하나씩)의 단일 한 쌍에 의해 결정된다.이러한 쌍방향 거리 중 가장 짧은 거리는 어느 단계에서나 유지되는 것으로 원소가 관련된 두 군집을 병합하게 한다.이 방법은 가장 가까운 이웃 군집화라고도 알려져 있다.군집화의 결과는 군집합이 이루어진 순서와 각 군집합이 이루어진 거리를 보여주는 덴드로그램으로 시각화할 수 있다.[2]
수학적으로 연결 함수 - 군집 X와 Y 사이의 거리 D(X,Y)는 표현으로 설명된다.
여기서 X와 Y는 군집으로 간주되는 원소의 두 집합이며, d(x,y)는 두 원소의 x와 y 사이의 거리를 나타낸다.
순진 알고리즘
다음 알고리즘은 기존 클러스터가 새로운 클러스터로 병합되면서 근접 행렬의 행과 열을 지우는 응집형 구조다.The proximity matrix contains all distances . The clusterings are assigned sequence numbers and is the level of the -th 군집화.시퀀스 번호 m의 클러스터는 (m)으로 표시되며, 클러스터) (r ) 및( 사이의 근접성은 [( r),( s) ), 로 표시된다
단일 연결 알고리즘은 다음 단계로 구성된다.
- L( )= 0 L 및 시퀀스 번호 = 0 을(를) 갖는 분리형 클러스터링으로 시작하십시오
- [( )(), ( s ) , ( s에 따라 에서 유사한클러스터 을 찾으십시오. d [ ( r ) ,( ) = d ( i), ( d ( ) = ( ) = ] = #
- 시퀀스 번호: = + }을를) 증분하십시오클러스터) 및 ) 을 (를) 단일 클러스터로 병합하여 다음 클러스터링 을(를) 형성하십시오 이 클러스터링의 을 = d로 설정하십시오
- 클러스터) 및( 에 해당하는 행과 열을 삭제하고 새로 구성된 클러스터에 해당하는 행과 열을 추가하여 근접 행렬을 업데이트하십시오.The proximity between the new cluster, denoted and old cluster is defined as .
- 모든 개체가 하나의 클러스터에 있으면 중지하십시오.그렇지 않으면 2단계로 이동하십시오.
작업 예제
이 작업 예는 5S 리보솜 RNA 시퀀스 정렬에서 계산된 JC69 유전자 거리 매트릭스를 기반으로 한다.바실러스 아열대( subilis, 바실러스 스타어터모필루스( 유산균 바이러스덴스( 아콜레플라즈마모디쿰( d 마이크로코커스 루테우스([3][4]
1단계
- 첫 번째 군집화
5개 요소 와 그 요소들 사이의 쌍방향 거리의 다음 {\}이 있다고 가정해 봅시다.
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 |
이 예에서 1( , b)= 의 가장 낮은 이므로 우리는 을 및 b 의 클러스터링한다
- 첫 번째 분기 길이 추정
이(가) {\과 (와) b{\}이(가) 연결된 노드를 나타내도록 하십시오.설정 Δ( ,)= ( b , = 1( , )/ }은는 a및 b {\ b} 가 {\displaystyle 로부터 동일하도록 보장한다이는 초경량 가설의 예상에 해당한다. b 을(를) 에 결합하는 분기의 길이 Δ)= / = 8 최종 덴드로그램 참조).
- 첫 번째 거리 행렬 업데이트
그런 다음 초기 근접 D1 {\1}를 새로운 2 {\D_{2}}( 참조 b {\ b을를) {\ a의 클러스터링으로 인해 크기가 한 행과 한 열로 축소됨 에서 굵은 값}는 첫 번째 군집 , )의 각 요소와 각 요소 사이의 최소 거리를 유지하여 계산한 새로운 거리에 해당한다
}의 기울임꼴로 표시된 값은 첫 번째 군집에 포함되지 않은 요소 사이의 거리에 해당하므로 행렬 업데이트의 영향을 받지 않는다.
두 번째 단계
- 두 번째 군집화
이제 새로운 거리 D }}:에서 시작하여 이전의 세 가지 동작을 반복한다.
(a,b) | c | d | e | |
---|---|---|---|---|
(a,b) | 0 | 21 | 31 | 21 |
c | 21 | 0 | 28 | 39 |
d | 31 | 28 | 0 | 43 |
e | 21 | 39 | 43 | 0 |
Here, and are the lowest values of , so we join cluster with element and with element 스타일 .
- 두 번째 분기 길이 추정
이() (, b) c 및 이(가) 연결된 노드를 나타내도록 하십시오.초경량 제약 조건 때문에 에 displaystyle a b v{\ 을를 에 결합하는 분기는 동일하며 과 총를 .
We deduce the missing branch length: (see the final dendrogram)
- 2차 거리 매트릭스
그런 다음 D }}매트릭스를 거리 매트릭스 아래 참조)로 업데이트하고, ) 및 의 클러스터링으로 인해 크기가 2행과 2열로 축소된다.
최종 단계
최종 행렬은 다음과 같다.
(a,b),c,e) | d | |
---|---|---|
(a,b),c,e) | 0 | 28 |
d | 28 | 0 |
그래서 우리는 클러스터(, ), c, ) 및 을(를) 결합한다
이( ), , ) 및 이(가) 연결된 (root) 노드를 나타내도록 하십시오. 에 b), , e) d 을(를) 결합하는 분기의 길이는 다음과 같다.
우리는 남은 가지 길이를 추측한다:
싱글 링크 덴드로그램
덴드로그램은 이제 완성되었다. 팁 c e 이 r{\에서 등거리이기 때문에 초경량적이다.
따라서 덴드로그램은 가장 깊은 노드인 에 의해 뿌리를 내린다.
기타 링크
단일 연결 클러스터링에 대한 순진한 알고리즘은 기본적으로 최소 스패닝 트리에 대한 크러스칼의 알고리즘과 동일하다.단, 단일 연결 군집화에서는 군집이 형성되는 순서가 중요한 반면, 최소 스패닝 트리의 경우 중요한 것은 알고리즘이 선택한 거리를 형성하는 점 쌍들의 집합이다.
대안적 연계방안으로는 완전한 연계 클러스터링, 평균 연계 클러스터링(UPGMA, WPGMA), 워드의 방법 등이 있다.집적 군집화에 대한 순진한 알고리즘에서, 다른 연결 체계를 구현하는 것은 알고리즘에서 클러스터 간 거리를 계산하기 위해 다른 공식을 사용하는 것만으로 이루어질 수 있다.조정해야 할 수식은 위의 알고리즘 설명에서 굵은 텍스트를 사용하여 강조 표시했다.그러나 아래에서 설명하는 것과 같은 보다 효율적인 알고리즘은 동일한 방식으로 모든 연결 체계를 일반화하지는 않는다.
![]() | |||
단일 링크 클러스터링 | 전체 링크 클러스터링 | 평균 링크 클러스터링: WPGMA | 평균 연결 클러스터링: UPGMA |
더 빠른 알고리즘
single-linkage 집단 형성에 대한 순진한 알고리즘을 이해하지만 느린, 시간 복잡도와 함께 O1973년{O(n^{3})\displaystyle}.[5](n3), R.Sibson 시간 복잡성과 알고리즘을 제안했다 쉽다 O(n2){O(n^{2})\displaystyle}과 공간 복잡도 O(n){O(n)\displaystyle}(둘 다 최적)로 알려진 SLINK..슬링크 알고리즘은 개의 번호 항목 집합에 있는 클러스터링을 두 함수에 의해 나타낸다.이러한 기능은 항목 과 (와) 하나 이상의 큰 번호가 있는 항목을 모두 포함하는 가장 작은 클러스터 을(를) 찾음으로써 모두 결정된다.첫 번째 기능인 은는) i 을(를) 클러스터 에서 가장 큰 번호의 항목에 매핑한다두 번째 함수인 은는) 항목 을(를) 클러스터 C의 생성과 관련된 거리에 매핑한다 이러한 함수를 기능 값에 매핑하는 두 개의 배열로 저장하면 공간 ) 가 충분하다t: 군집화 자체를 결정하는 방법.Sibson이 보여주듯이, 새로운 항목이 항목 집합에 추가되었을 때, 동일한 방법으로 표현된 증강 집합에 대한 새로운 단일 링크 클러스터링을 나타내는 업데이트된 기능은 O ( 의 기존 클러스터링으로부터 구성할 수 있다그런 다음 SLINK 알고리즘은 항목을 하나씩 반복하여 클러스터링의 표현에 추가한다.[6][7]
동일한 최적 시간과 공간 경계에서 실행되는 대안 알고리즘은 최소 스패닝 트리에 대한 순진한 알고리즘과 크러스칼의 알고리즘 사이의 동등성에 기초한다.크러스칼의 알고리즘을 사용하는 대신, 주어진 항목과 거리의 최소 스패닝 트리(군집화 제외)를 구성하기 O(2 ) O와 O(){\ O(가 걸리는 이진 힙이 없는 변형으로 Prim의 알고리즘을 사용할 수 있다.그런 다음 최소 스패닝 트리의 가장자리에 의해 형성된 희소 그래프에 크러스칼의 알고리즘을 적용하면 ) 과 ( On) {\ O이 추가 시간 내에 클러스터링 자체가 생성된다[8]
참고 항목
참조
- ^ Everitt B (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.
- ^ Legendre P, Legendre L (1998). Numerical Ecology. Developments in Environmental Modelling. Vol. 20 (Second English ed.). Amsterdam: Elsevier.
- ^ Erdmann VA, Wolters J (1986). "Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences". Nucleic Acids Research. 14 Suppl (Suppl): r1-59. doi:10.1093/nar/14.suppl.r1. PMC 341310. PMID 2422630.
- ^ Olsen GJ (1988). "Phylogenetic analysis using ribosomal RNA". Methods in Enzymology. 164: 793–812. doi:10.1016/s0076-6879(88)64084-5. PMID 3241556.
- ^ Murtagh F, Contreras P (2012). "Algorithms for hierarchical clustering: an overview". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. Wiley Online Library. 2 (1): 86–97. doi:10.1002/widm.53.
- ^ Sibson R (1973). "SLINK: an optimally efficient algorithm for the single-link cluster method" (PDF). The Computer Journal. British Computer Society. 16 (1): 30–34. doi:10.1093/comjnl/16.1.30.
- ^ Gan G (2007). Data clustering : theory, algorithms, and applications. Philadelphia, Pa. Alexandria, Va: SIAM, Society for Industrial and Applied Mathematics American Statistical Association. ISBN 9780898716238.
- ^ Gower JC, Ross GJ (1969). "Minimum spanning trees and single linkage cluster analysis". Journal of the Royal Statistical Society, Series C. 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439. MR 0242315..