linkage

계층적 병합 군집 트리

구문

Z = linkage(X)

Z = linkage(X,method)

Z = linkage(X,method,metric)

Z = linkage(X,method,metric,'savememory',value)

Z = linkage(X,method,pdist_inputs)

Z = linkage(y)

Z = linkage(y,method)

설명

Z = linkage(X)는 입력 데이터 행렬 X의 행으로 구성된 계층적 군집을 포함하는 트리를 인코딩하는 행렬 Z를 반환합니다.

Z = linkage(X,method)는 군집 간의 거리를 측정하는 방법인 method를 사용하여 트리를 생성합니다. 자세한 내용은 연결 항목을 참조하십시오.

Z = linkage(X,method,metric)은 X의 행 간의 거리를 계산하는 pdist 함수에 metric을 전달하여 군집화를 수행합니다.

value가 'on'인 경우 Z = linkage(X,method,metric,'savememory',value)는 메모리 절약 알고리즘을 사용하고, value가 'off'인 경우 표준 알고리즘을 사용합니다.

Z = linkage(X,method,pdist_inputs)는 X의 행 간의 거리를 계산하는 pdist 함수에 pdist_inputs를 전달합니다. pdist_inputs 인수는 'seuclidean', 'minkowski' 또는 'mahalanobis' 측정법과 추가 거리 측정법 옵션으로 구성됩니다.

Z = linkage(y)는 거리 행렬의 벡터 표현 y를 사용합니다. y는 pdist로 계산되거나 pdist의 출력 형식을 따르는 더욱 일반적인 비유사성 행렬일 수 있습니다.

Z = linkage(y,method)는 군집 간의 거리를 측정하는 방법인 method를 사용하여 트리를 생성합니다.

예제

데이터를 군집화하고 결과를 플로팅하기

20,000개의 관측값을 갖는 표본 데이터를 임의로 생성합니다.

rng(0,"twister") % For reproducibility
X = rand(20000,3);

ward 연결 방법을 사용하여 계층적 군집 트리를 생성합니다. 이 경우, clusterdata 함수의 SaveMemory 옵션은 기본적으로 "on"으로 설정됩니다. 일반적으로, X의 차원과 사용 가능한 메모리를 기준으로 SaveMemory에 가장 적합한 값을 지정합니다.

Z = linkage(X,"ward");

데이터를 최대 네 개의 그룹으로 군집화하고 결과를 플로팅합니다.

c = cluster(Z,MaxClust=4);
scatter3(X(:,1),X(:,2),X(:,3),10,c)

cluster는 데이터에서 네 개의 그룹을 식별합니다.

클래스에 대한 군집 할당 비교하기

fisheriris 데이터 세트에서 최대 세 개의 군집을 찾고 꽃의 군집 할당을 알려진 분류와 비교합니다.

표본 데이터를 불러옵니다.

load fisheriris

"average" 방법과 "chebychev" 측정법을 사용하여 계층적 군집 트리를 생성합니다.

Z = linkage(meas,"average","chebychev");

데이터에서 최대 세 개의 군집을 찾습니다.

T = cluster(Z,MaxClust=3);

Z에 대한 덴드로그램 플롯을 생성합니다. 3개의 군집을 표시하기 위해 마지막에서 세 번째 연결과 마지막에서 두 번째 연결 간의 중간 절단을 ColorThreshold로 사용합니다.

cutoff = median([Z(end-2,3) Z(end-1,3)]);
dendrogram(Z,ColorThreshold=cutoff,ShowCut=true)

Z의 마지막 두 행을 표시하여 세 개의 군집이 어떻게 하나로 결합되었는지를 확인합니다. linkage는 연결 값으로 1.7583을 사용하여 293번째(주황색) 군집을 297번째(파란색) 군집과 결합하여 298번째 군집을 형성합니다. 그런 다음 linkage는 296번째(빨간색) 군집과 298번째 군집을 결합합니다.

lastTwo = Z(end-1:end,:)

lastTwo = 2×3

  293.0000  297.0000    1.7583
  296.0000  298.0000    3.4445

군집 할당은 세 가지 종에 대응됩니다. 예를 들면, 군집 중 하나에 두 번째 종의 꽃은 50송이, 세 번째 종의 꽃은 40송이가 포함되어 있습니다.

crosstab(T,species)

ans = 3×3

     0     0    10
     0    50    40
    50     0     0

계층적 트리에서 군집화 스텝 관측하기

examgrades 데이터 세트를 불러옵니다.

load examgrades

linkage를 사용하여 계층적 트리를 생성합니다. 'single' 방법과, 지수를 3으로 하여 민코프스키(Minkowski) 측정법을 사용합니다.

Z = linkage(grades,'single',{'minkowski',3});

25번째 군집화 스텝을 관측합니다.

Z(25,:)

ans = 1×3

   86.0000  137.0000    4.5307

linkage는 86번째 관측값과 137번째 군집을 결합하여 인덱스가 $120+25=145$인 군집을 구성합니다. 여기서 120은 grades에 포함된 총 관측값 개수이고, 25는 Z의 행 번호입니다. 86번째 관측값과 137번째 군집에 포함된 모든 점 간의 최단 거리는 4.5307입니다.

비유사성 행렬을 사용하여 데이터 군집화하기

비유사성 행렬을 사용하여 계층적 병합 군집 트리를 생성합니다.

비유사성 행렬 X를 지정한 다음 squareform을 사용하여 linkage가 받는 벡터 형식으로 변환합니다.

X = [0 1 2 3; 1 0 4 5; 2 4 0 6; 3 5 6 0];
y = squareform(X);

'complete'을 두 군집 간 거리 계산 방법으로 지정하고 linkage를 사용하여 군집 트리를 생성합니다. Z의 처음 두 열은 linkage가 군집을 어떻게 결합하는지를 보여줍니다. Z의 세 번째 열은 군집 간 거리를 제공합니다.

Z = linkage(y,'complete')

Z = 3×3

     1     2     1
     3     5     4
     4     6     6

Z에 대한 덴드로그램 플롯을 생성합니다. x축은 트리의 리프 노드에 대응되고, y축은 군집 간의 연결 거리에 대응됩니다.

dendrogram(Z)

입력 인수

X — 입력 데이터

숫자형 행렬

입력 데이터로, 둘 이상의 행을 가진 숫자형 행렬로 지정됩니다. 행은 관측값을 나타내고, 열은 범주 또는 차원을 나타냅니다.

데이터형: single | double

method — 군집 간 거리를 계산하는 알고리즘입니다.

'single' (디폴트 값) | 'average' | 'centroid' | 'complete' | ...

군집 간 거리를 계산하는 알고리즘으로, 다음 표에 나와 있는 값 중 하나로 지정됩니다.

방법	설명
'average'	비가중 평균 거리(UPGMA)
'centroid'	중심 거리(UPGMC)로, 유클리드 거리에만 적합함
'complete'	최장 거리
'median'	가중 질량 중심 거리(WPGMC)로, 유클리드 거리에만 적합함
'single'	최단 거리
'ward'	내부 제곱 거리(최소 분산 알고리즘)로, 유클리드 거리에만 적합함
'weighted'	가중 평균 거리(WPGMA)

이러한 방법에 대한 자세한 내용은 연결 항목을 참조하십시오.

metric — 거리 측정법

'euclidean' (디폴트 값) | 'squaredeuclidean' | 'seuclidean' | 'mahalanobis' | 함수 핸들 | ...

거리 측정법으로, pdist 함수가 받는 모든 측정법으로 지정됩니다. 이러한 측정법은 다음 표에 설명되어 있습니다.

값	설명
'euclidean'	유클리드 거리(디폴트 값)
'squaredeuclidean'	제곱 유클리드 거리입니다. (이 옵션은 효율성을 위해서만 제공됩니다. 삼각 부등식을 충족하지 않습니다.)
'seuclidean'	표준화된 유클리드 거리입니다. 관측값 간의 각 좌표 차이는 표준편차 S = std(X,'omitnan')의 대응 요소로 나누어져 스케일링됩니다. S에 다른 값을 지정하려면 DistParameter를 사용하십시오.
'fasteuclidean'	예측 변수 개수가 10개 이상인 경우 시간을 아끼는 대체 알고리즘을 사용하여 계산된 유클리드 거리입니다. 속도가 더 빠른 이 알고리즘은 정확도가 떨어질 수 있습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.
'fastsquaredeuclidean'	예측 변수 개수가 10개 이상인 경우 시간을 아끼는 대체 알고리즘을 사용하여 계산된 제곱 유클리드 거리입니다. 속도가 더 빠른 이 알고리즘은 정확도가 떨어질 수 있습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.
'fastseuclidean'	예측 변수 개수가 10개 이상인 경우 시간을 아끼는 대체 알고리즘을 사용하여 계산된 표준화된 유클리드 거리입니다. 속도가 더 빠른 이 알고리즘은 정확도가 떨어질 수 있습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.
'mahalanobis'	마할라노비스 거리로, X의 표본 공분산 C = cov(X,'omitrows')를 사용하여 계산됩니다. C에 대해 다른 값을 지정하려면 DistParameter를 사용하십시오. 여기서 행렬 C는 양의 정부호 대칭 행렬입니다.
'cityblock'	도시 블록 거리
'minkowski'	민코프스키 거리입니다. 디폴트 지수는 2입니다. 다른 지수 P를 지정하려면 DistParameter를 사용하십시오. 여기서 P는 지수의 양의 스칼라 값입니다.
'chebychev'	체비쇼프 거리(최대 좌표 차이)
'cosine'	1에서 점 간의 끼인각에 대한 코사인을 뺀 값(벡터로 처리됨)
'correlation'	1에서 점 간의 표본 상관을 뺀 값(일련의 값으로 처리됨)
'hamming'	해밍 거리로, 서로 다른 좌표의 비율
'jaccard'	0이 아닌 두 좌표의 값이 서로 다른 비율인 자카드 계수를 1에서 뺀 값
'spearman'	1에서 관측값 간 표본 스피어만의 순위 상관 계수를 뺀 값(일련의 값으로 처리됨)
@distfun	사용자 지정 거리 함수 핸들입니다. 거리 함수의 형식은 다음과 같습니다. function D2 = distfun(ZI,ZJ) % calculation of distance ... 여기서 ZI는 단일 관측값을 포함하는 1×n 벡터입니다. ZJ는 여러 관측값을 포함하는 m2×n 행렬입니다. distfun은 임의 개수의 관측값을 갖는 행렬 ZJ를 받아야 합니다. D2는 거리로 구성된 m2×1 벡터이고, D2(k)는 관측값 ZI와 ZJ(k,:) 간의 거리입니다. 데이터가 희소 형식이 아닌 경우 일반적으로 함수 핸들 대신 내장 거리 측정법을 사용하면 더욱 신속하게 거리를 계산할 수 있습니다.

자세한 내용은 거리 측정법 항목을 참조하십시오.

metric 대신 pdist_inputs를 사용하여 'seuclidean', 'minkowski' 또는 'mahalanobis'에 대해 pdist의 추가 입력 인수 DistParameter를 지정할 수 있습니다.

데이터형: char | string | function_handle

pdist_inputs — 거리 측정법과 거리 측정법 옵션

셀형 배열

거리 측정법과 거리 측정법 옵션으로, 함수 pdist에 대한 두 개의 입력 인수 Distance와 DistParameter가 쉼표로 구분되어 포함된 셀형 배열로 지정됩니다. 이 인수는 'seuclidean', 'minkowski' 또는 'mahalanobis'를 지정하는 경우에만 유효합니다.

예: {'minkowski',5}

데이터형: cell

value — 'savememory' 옵션을 나타내는 플래그

'on' | 'off'

'savememory' 옵션을 나타내는 플래그로, 'on' 또는 'off'로 지정됩니다. 'on'으로 설정하면 linkage가 거리 행렬을 계산하지 않고 군집을 생성합니다. method가 'centroid', 'median' 또는 'ward'이고 metric이 'euclidean'인 경우에만 'on'으로 설정할 수 있습니다.

value가 'on'인 경우, linkage 실행 시간은 차원 수(X 열의 개수)에 비례합니다. value가 'off'인 경우, linkage 메모리 요구 사항은 N²에 비례합니다(여기서 N은 관측값 개수임). value에 대한 최적의 설정(시간이 가장 적게 걸림)은 문제 차원 수, 관측값 개수, 사용 가능한 메모리에 따라 달라집니다. 디폴트 value 설정은 최적의 설정에 대한 대략적인 근삿값입니다.

디폴트 값은 X의 열 개수가 20개 이하이거나 컴퓨터에 거리 행렬을 저장하는 데 충분한 메모리가 없는 경우 'on'입니다. 그렇지 않은 경우 디폴트 값은 'off'입니다.

예: 'savememory','on'

y — 거리

숫자형 벡터

거리로, pdist 함수의 출력값과 같은 형식을 갖는 숫자형 벡터로 지정됩니다.

• m개 행을 갖는 행렬의 관측값 쌍에 대응되는, 길이가 m(m – 1)/2인 행 벡터

• (2,1), (3,1), ..., (m,1), (3,2), ..., (m,2), ..., (m,m – 1)) 순서로 정렬된 거리

y는 pdist의 출력 형식을 따르는 더욱 일반적인 비유사성 행렬일 수 있습니다.

데이터형: single | double

출력 인수

Z — 계층적 병합 군집 트리

숫자형 행렬

계층적 병합 군집 트리로, 숫자형 행렬로 반환됩니다. Z는 (m – 1)×3 행렬이고, 여기서 m은 원래 데이터에 포함된 관측값 개수입니다. Z의 1열과 2열은 이진 트리를 구성할 수 있도록 쌍으로 연결된 군집 인덱스를 포함합니다. 리프 노드에는 1에서 m까지 번호가 지정됩니다. 리프 노드는 모든 상위 군집의 생성 기반이 되는 한원소 군집입니다. 행 Z(I,:)에 대응되는 새로 구성된 군집 각각에는 인덱스 m + I가 할당됩니다. 요소 Z(I,1) 및 Z(I,2)는 군집 m + I를 구성하는 2개 성분을 갖는 군집에 대한 인덱스를 포함합니다. m – 1개의 상위 군집이 군집화 트리의 내부 노드에 대응됩니다. Z(I,3)은 행 Z(I,:)에 병합된 두 군집 간의 연결 거리를 포함합니다.

예를 들어, 30개의 초기 노드가 있는 트리를 만드는 경우를 살펴보겠습니다. 스텝 12에서 군집 5와 군집 7이 결합되었고 이 스텝에서 두 군집 간의 거리는 1.5라고 가정합니다. 그러면 Z(12,:)은 [5 7 1.5]입니다. 새로 구성된 군집은 인덱스 12 + 30 = 42를 가집니다. 군집 42가 이후 행에 표시된다면, 이는 함수가 스텝 12에서 생성된 군집을 어떤 더 큰 군집에 결합하는 것입니다.

데이터형: single | double

세부 정보

연결

연결(linkage)은 두 군집 간의 거리입니다.

다양한 방법에서 사용되는 연결을 설명하기 위해 다음 표기법이 사용됩니다.

• 군집 r은 군집 p와 q에서 구성됩니다.

• n_r은 군집 r에 포함된 객체의 개수입니다.

• x_ri는 군집 r의 i번째 객체입니다.

• 단일 연결(최근접이웃이라고도 함)은 두 군집에 포함된 객체 간의 가장 작은 거리를 사용합니다.

  $$d(r,s)=\min (dist(x_{ri},x_{sj})),i\in (i,\mathrm{...},n_r),j\in (1,\mathrm{...},n_s)$$

• 완전 연결(최장 이웃이라고도 함)은 두 군집에 포함된 객체 간의 가장 큰 거리를 사용합니다.

  $$d(r,s)=\max (dist(x_{ri},x_{sj})),i\in (1,\mathrm{...},n_r),j\in (1,\mathrm{...},n_s)$$

• 평균 연결은 두 군집에 포함된 모든 객체 쌍 간의 평균 거리를 사용합니다.

  $$d(r,s)=\frac{1}{n_r{n}_s}{\displaystyle \sum _{i=1}^{n_r}{\displaystyle \sum _{j=1}^{n_s}dist(x_{ri},x_{sj})}}$$

• 중심 연결은 두 군집의 중심 간의 유클리드 거리를 사용합니다.

  $$d(r,s)={\Vert {\overline{x}}_r-{\overline{x}}_s\Vert }_2,$$

  여기서

  $${\overline{x}}_r=\frac{1}{n_r}{\displaystyle \sum _{i=1}^{n_r}{x}_{ri}}$$

• 중앙값 연결은 두 군집의 가중 중심 간의 유클리드 거리를 사용합니다.

  $$d(r,s)={\Vert {\tilde{x}}_r-{\tilde{x}}_s\Vert }_2,$$

  여기서 $${\tilde{x}}_r$$ 및 $${\tilde{x}}_s$$는 군집 r 및 군집 s에 대한 가중 중심입니다. 군집 r이 군집 p와 군집 q를 결합하여 생성된 경우, $${\tilde{x}}_r$$은 다음과 같이 재귀적으로 정의됩니다.

  $${\tilde{x}}_r=\frac{1}{2}({\tilde{x}}_p+{\tilde{x}}_q)$$

• 와드 연결(Ward Linkage)은 제곱의 증분 합, 즉 두 군집을 결합한 결과로 생성되는 군집 내 제곱합의 증분을 사용합니다. 군집 내 제곱합은 군집에 포함된 모든 객체와 군집 중심 간의 거리에 대한 제곱합으로 정의됩니다. 제곱합 측정값은 linkage가 사용하는 다음 식의 거리 측정법 d(r,s)와 같습니다.

  $$d(r,s)=\sqrt{\frac{2n_r{n}_s}{(n_r+n_s)}}{\Vert {\overline{x}}_r-{\overline{x}}_s\Vert }_2,$$

  여기서

  • $${\Vert \Vert }_2$$는 유클리드 거리입니다.

  • $${\overline{x}}_r$$ 및 $${\overline{x}}_s$$는 군집 r 및 군집 s의 중심입니다.

  • n_r 및 n_s는 군집 r 및 군집 s에 포함된 요소의 개수입니다.

  일부 참고 문헌에서는 와드 연결에서 n_rn_s에 인자 2를 곱하지 않습니다. linkage 함수는 이 인자를 사용하여 두 한원소 군집 간의 거리가 유클리드 거리와 같아지도록 합니다.

• 가중 평균 연결은 두 군집 간의 거리에 대한 재귀적 정의를 사용합니다. 군집 r이 군집 p와 군집 q를 결합하여 생성된 경우, r과 다른 군집 s 간의 거리는 p와 s 간의 거리와 q와 s 간의 거리의 평균으로 정의됩니다.

  $$d\left(r,s\right)=\frac{\left(d\left(p,s\right)+d\left(q,s\right)\right)}{2}$$

팁

• y가 거리 행렬의 벡터 표현인 경우 linkage(y) 계산이 느려질 수 있습니다. 'centroid', 'median', 'ward' 방법에 대해 linkage는 y가 유클리드 거리인지 여부를 확인합니다. y 대신 X를 전달하여 시간이 많이 걸리는 이 확인 작업을 피할 수 있습니다.

• 'centroid' 방법과 'median' 방법은 단조적(Monotonic)이지 않은 군집 트리를 생성할 수 있습니다. 이 결과는 두 군집 r과 s의 합집합에서 세 번째 군집까지의 거리가 r과 s 간의 거리보다 작을 경우에 발생합니다. 이 경우, 디폴트 방향으로 그린 덴드로그램에서 리프로부터 루트 노드까지의 경로는 아래쪽 방향의 일부 단계를 지나게 됩니다. 이 결과를 방지하려면 다른 방법을 사용하십시오. 다음 Figure는 비단조적 군집 트리를 보여줍니다.

  

  이 경우, 군집 1과 군집 3이 새 군집으로 결합되며, 이 새 군집과 군집 2 간의 거리는 군집 1과 군집 3 간의 거리보다 작습니다. 그 결과 비단조적 트리가 생성됩니다.

• 트리를 표시하기 위한 dendrogram, 점을 군집에 할당하기 위한 cluster, 일치하지 않는 측정값을 계산하기 위한 inconsistent, 코페네틱 상관 계수(Cophenetic Correlation Coefficient)를 계산하기 위한 cophenet를 비롯한 다른 함수에 출력값 Z를 제공할 수 있습니다.

버전 내역

R2006a 이전에 개발됨

참고 항목

cluster | clusterdata | cophenet | dendrogram | inconsistent | kmeans | pdist | silhouette | squareform

도움말 항목

• 계층적 군집화