계층적 군집화

}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).

• 모든 내부 클러스터 분산의 합.
• 클러스터 병합 시 증가하는 분산의 양 (Ward의 방법^[8]).
• 두 클러스터가 동일한 분포 함수에서 생성되었을 확률 (V-linkage).

만약 가장 가까운 클러스터 쌍이 여러 개 존재하여 최소 거리가 동률인 경우, 어떤 쌍을 먼저 병합할지 무작위로 선택할 수 있다. 이 경우 여러 개의 구조적으로 다른 덴드로그램이 생성될 수 있다. 또는 동률인 모든 쌍을 동시에 병합하여 고유한 덴드로그램을 생성할 수도 있다.^[18]

군집화 과정은 사용자가 원하는 특정 개수의 클러스터가 만들어졌을 때 중단될 수 있다(개수 기준). 또한, 일부 연결 기준(예: 완전 연결)은 병합 단계가 진행될수록 클러스터 간 거리가 항상 증가하거나 같도록 보장한다. 이런 경우, 클러스터 간 거리가 특정 임계값을 초과하면 더 이상 병합하는 것이 의미 없다고 판단하여 군집화를 중단할 수도 있다(거리 기준). 그러나 모든 연결 기준이 이러한 속성을 가지는 것은 아니며, 예를 들어 중심점 연결(centroid-linkage)과 같은 일부 방법에서는 나중에 병합되는 클러스터 간의 거리가 이전에 병합된 클러스터 간의 거리보다 더 작아지는 소위 역전(inversion) 현상이 발생할 수도 있다.^[19]

2. 2. 분할형 (Divisive)

분할형 군집화(Divisive clustering)는 전체 데이터 집합을 하나의 클러스터로 간주하고 시작하여, 점차 더 작은 클러스터로 나누어 나가는 하향식(top-down) 접근 방식이다. 대표적인 알고리즘으로는 DIANA(DIvisive ANAlysis clustering)가 있다.^[20]

DIANA 알고리즘은 초기에 모든 데이터를 하나의 큰 클러스터에 넣고 시작한다. 그런 다음, 특정 기준에 따라 클러스터를 반복적으로 분할하는데, 일반적으로는 크기가 가장 큰 클러스터(예: 클러스터 내 두 객체 간의 거리가 가장 먼 클러스터)를 선택하여 분할한다. 이 과정은 각 객체가 자신만의 클러스터에 속하게 될 때까지, 즉 모든 객체가 분리될 때까지 계속된다.

하나의 클러스터를 두 개로 나누는 가능한 방법의 수는 데이터 개수가 n개일 때 $O(2^n)$으로 매우 많기 때문에, 모든 경우를 탐색하는 것은 비현실적이다. 따라서 실제로는 휴리스틱 방법을 사용하여 최적에 가까운 분할을 찾는다. DIANA 알고리즘은 다음과 같은 휴리스틱 전략을 사용한다.^[20]

1. 분할할 클러스터($C\_*$)를 선택한다. 보통 현재 클러스터들 중에서 직경(가장 멀리 떨어진 두 객체 간의 거리)이 가장 큰 클러스터를 선택한다.

2. 선택된 클러스터($C\_*$) 내에서, 다른 객체들과의 평균 이질성(거리 또는 비유사성의 평균값)이 가장 큰 객체($i^*$)를 찾는다. 이 객체는 현재 클러스터에서 가장 "어울리지 않는" 객체로 간주될 수 있다.

3. 이 가장 이질적인 객체($i^*$)를 이용하여 새로운 클러스터, 즉 분열 그룹($C\_\backslash textrm\{new\}$)을 만들기 시작한다. 처음에는 이 그룹에 $i^*$만 포함된다.

4. 원래 클러스터($C\_*$)에 남아 있는 다른 객체들을 검토한다. 각 객체($i$)에 대해, 원래 클러스터($C\_*$)에 남아 있는 다른 객체들과의 평균 이질성($\backslash frac\{1\}\{|C\_*|-1\}\backslash sum\_\{j\backslash in\; C\_*\backslash setminus\backslash \{i\backslash \}\}\; \backslash delta(i,j)$)과 새로 생긴 분열 그룹($C\_\backslash textrm\{new\}$) 내 객체들과의 평균 이질성($\backslash frac\{1\}$

\sum_{j\in C_\textrm{new}} \delta(i,j))을 비교한다.

5. 만약 어떤 객체($i$)가 원래 클러스터의 나머지 객체들보다 새로 생긴 분열 그룹에 더 가깝다면(즉, $D(i)\; =\; \backslash frac\{1\}\{|C\_*|-1\}\backslash sum\_\{j\backslash in\; C\_*\backslash setminus\backslash \{i\backslash \}\}\; \backslash delta(i,j)\; -\; \backslash frac\{1\}$

\sum_{j\in C_\textrm{new}} \delta(i,j) 값이 양수(+)로 크다면), 해당 객체를 분열 그룹($C\_\backslash textrm\{new\}$)으로 이동시킨다. 이 과정은 더 이상 분열 그룹으로 이동할 객체가 없을 때까지 (즉, 모든 남은 객체에 대해 $D(i)$ 값이 음수(-)가 될 때까지) 반복된다.

6. 분할이 완료되면, 원래 클러스터($C\_*$)는 크기가 줄어들고, 새로운 클러스터($C\_\backslash textrm\{new\}$)가 생성된다. 이 두 클러스터를 기존 클러스터 목록에 추가하고, 전체 클러스터 수가 데이터 개수($n$)와 같아질 때까지 위의 과정을 반복한다.

이 과정은 마치 기존 클러스터에서 일부 객체를 "떼어내어" 새로운 클러스터를 만드는 것처럼 보이지만, 실제로는 가장 이질적인 객체를 중심으로 새로운 클러스터를 "형성"하고 여기에 유사한 객체들을 점진적으로 "이동"시켜 기존 클러스터를 "비워내는" 과정에 가깝다고 볼 수 있다.^[20]

DIANA 알고리즘의 결과는 덴드로그램으로 시각화할 수 있다. 각 분할 단계에서 새로 생성된 분열 그룹($C\_\backslash textrm\{new\}$)을 원래 클러스터($C\_*$)의 자식 노드로 연결하면, 전체 데이터를 루트로 하고 개별 데이터 포인트를 리프 노드로 하는 계층적 트리 구조를 만들 수 있다.^[20]

3. 클러스터 연결 (Cluster Linkage)

클러스터를 결합하거나(응집형) 분할할(분할형) 위치를 결정하기 위해서는 관찰 대상 집합 간의 비유사성을 측정해야 한다. 대부분의 계층적 군집화 방법에서는 데이터 집합 내 개별 관찰 간의 유클리드 거리와 같은 적절한 거리 ''d''를 사용하고, 집합 내 관찰들의 쌍별 거리에 기반한 함수인 연결 기준(Linkage Criteria)을 통해 집합 간의 비유사성을 정의한다. 사용하는 거리 척도는 어떤 객체가 가장 유사한지를 결정하는 반면, 연결 기준은 생성되는 클러스터의 모양에 영향을 미친다. 예를 들어, 완전 연결 방식은 단일 연결 방식보다 더 구형에 가까운 클러스터를 만드는 경향이 있다.

3. 1. 연결 기준 (Linkage Criteria)

클러스터를 결합하거나(응집형) 분할할(분할형) 위치를 결정하기 위해서는 관찰 대상 집합 간의 비유사성을 측정해야 한다. 대부분의 계층적 군집화 방법에서는 데이터 집합 내 개별 관찰 간의 유클리드 거리와 같은 적절한 거리 ''d''를 사용하고, 집합 내 관찰들의 쌍별 거리에 기반한 함수인 연결 기준(Linkage Criteria)을 통해 집합 간의 비유사성을 정의한다. 사용하는 거리 척도는 어떤 객체가 가장 유사한지를 결정하는 반면, 연결 기준은 생성되는 클러스터의 모양에 영향을 미친다. 예를 들어, 완전 연결 방식은 단일 연결 방식보다 더 구형에 가까운 클러스터를 만드는 경향이 있다.

연결 기준은 개별 관찰 간의 쌍별 거리를 이용하여 관찰 집합 간의 거리를 결정하는 함수이다.

두 관찰 집합 ''A''와 ''B'', 그리고 거리 ''d''에 대해 일반적으로 사용되는 연결 기준은 다음과 같다.^[5][6]

{| class="wikitable"

! 이름 !! 공식

|-

| 최대 또는 완전 연결 군집화 || $\backslash max\_\{a\backslash in\; A,\backslash ,\; b\backslash in\; B\}\; d(a,b)$

|-

| 최소 또는 단일 연결 군집화 || $\backslash min\_\{a\backslash in\; A,\backslash ,\; b\backslash in\; B\}\; d(a,b)$

|-

| 평균 연결 군집화 (비가중, UPGMA) || $\backslash frac\{1\}$

\sum_{a \in A }\sum_{ b \in B} d(a,b).

|-

| 평균 연결 군집화 (가중, WPGMA) || $d(i\; \backslash cup\; j,\; k)\; =\; \backslash frac\{d(i,\; k)\; +\; d(j,\; k)\}\{2\}.$

|-

| 중심 연결 군집화 (비가중, UPGMC) || $\backslash lVert\; \backslash mu\_A-\backslash mu\_B\backslash rVert^2$ (여기서 $\backslash mu\_A$와 $\backslash mu\_B$는 각각 ''A''와 ''B''의 중심)

|-

| 중앙값 연결 군집화 (가중, WPGMC) || $d(i\backslash cup\; j,\; k)\; =\; d(m\_\{i\backslash cup\; j\},\; m\_k)$ (여기서 $m\_\{i\backslash cup\; j\}\; =\; \backslash tfrac\{1\}\{2\}\backslash left(m\_i\; +\; m\_j\backslash right)$)

|-

| 다양한 연결 군집화^[7] || $\backslash sqrt[p]\{\backslash frac\{1\}$

\sum_{a \in A }\sum_{ b \in B} d(a,b)^p}, p\neq 0

|-

| Ward 연결^[8], 최소 제곱합 증가 (MISSQ)^[9] || $\backslash frac$

\lVert \mu_A - \mu_B \rVert ^2 = \sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 - \sum_{x\in A} \lVert x - \mu_{A} \rVert^2 - \sum_{x\in B} \lVert x - \mu_{B} \rVert^2

|-

| 최소 오차 제곱합 (MNSSQ)^[9] || $\backslash sum\_\{x\backslash in\; A\backslash cup\; B\}\; \backslash lVert\; x\; -\; \backslash mu\_\{A\backslash cup\; B\}\; \backslash rVert^2$

|-

| 분산 최소 증가 (MIVAR)^[9] || $\backslash frac\{1\}$

\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 - \frac{1}

\sum_{x\in A} \lVert x - \mu_{A} \rVert^2 - \frac{1}

\sum_{x\in B} \lVert x - \mu_{B} \rVert^2 = \text{Var}(A\cup B) - \text{Var}(A) - \text{Var}(B)

|-

| 최소 분산 (MNVAR)^[9] || $\backslash frac\{1\}$

\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 = \text{Var}(A\cup B)

|-

| 하우스도르프 연결^[10] || $\backslash max\_\{x\backslash in\; A\backslash cup\; B\}\; \backslash min\_\{y\backslash in\; A\backslash cup\; B\}\; d(x,y)$

|-

| 최소 합 메도이드 연결^[11] || $\backslash min\_\{m\backslash in\; A\backslash cup\; B\}\; \backslash sum\_\{y\backslash in\; A\backslash cup\; B\}\; d(m,\; y)$ (여기서 m은 결과 클러스터의 메도이드)

|-

| 최소 합 증가 메도이드 연결^[11] || $\backslash min\_\{m\backslash in\; A\backslash cup\; B\}\; \backslash sum\_\{y\backslash in\; A\backslash cup\; B\}\; d(m,y)\; -\; \backslash min\_\{m\backslash in\; A\}\; \backslash sum\_\{y\backslash in\; A\}\; d(m,y)\; -\; \backslash min\_\{m\backslash in\; B\}\; \backslash sum\_\{y\backslash in\; B\}\; d(m,y)$

|-

| 메도이드 연결^[12][13] || $d(m\_A,\; m\_B)$ (여기서 $m\_A$, $m\_B$는 이전 클러스터의 메도이드)

|-

| 최소 에너지 군집화 || $\backslash frac\; \{2\}\{nm\}\backslash sum\_\{i,j=1\}^\{n,m\}\; \backslash |a\_i-\; b\_j\backslash |\_2\; -\; \backslash frac\; \{1\}\{n^2\}\backslash sum\_\{i,j=1\}^\{n\}\; \backslash |a\_i-a\_j\backslash |\_2\; -\; \backslash frac\{1\}\{m^2\}\backslash sum\_\{i,j=1\}^\{m\}\; \backslash |b\_i-b\_j\backslash |\_2$

|}

위 표의 연결 기준 중 일부(예: WPGMA, WPGMC)는 재귀적으로만 계산할 수 있으며, 많은 경우 Lance-Williams 공식을 사용하여 재귀적으로 계산하는 것이 더 효율적이다. 하지만 하우스도르프 연결이나 메도이드 연결과 같은 다른 기준들은 더 느린 전체 공식을 사용하여 거리를 계산해야 할 수도 있다.

이 외에도 다른 연결 기준들이 존재한다.

• 후보 클러스터들이 동일한 분포 함수에서 생성될 확률 (V-연결)
• k-최근접 이웃 그래프의 차수(degree)의 곱 (그래프 차수 연결)^[14]
• 두 클러스터를 병합했을 때 특정 클러스터 설명자(클러스터 품질 측정 지표)의 증가량^[15][16][17]

특히 널리 사용되는 연결 기준은 다음과 같이 두 클러스터 $\backslash mathcal\{A\}$와 $\backslash mathcal\{B\}$ 사이의 거리를 정의한다.

• 최대 연결(Complete-linkage): 각 클러스터에 속한 요소 간 거리의 최댓값.
• 최소 연결(Single-linkage): 각 클러스터에 속한 요소 간 거리의 최솟값.
• 평균 연결(Average-linkage): 각 클러스터에 속한 요소 간 거리의 평균값. UPGMA 등에서 사용된다.
• Ward 연결: 클러스터를 병합했을 때 발생하는 클러스터 내 분산의 증가량.

최소 거리가 동일한 경우가 발생하면, 어떤 쌍을 먼저 병합할지에 따라 여러 구조적으로 다른 덴드로그램이 생성될 수 있다. 또는 모든 동률 쌍을 동시에 결합하여 고유한 덴드로그램을 생성할 수도 있다.^[18] 일부 연결 기준(예: 중심점 연결)에서는 병합이 진행될수록 클러스터 간 거리가 오히려 줄어드는 역전(inversion) 현상이 발생할 수도 있다.^[19]

4. 계산 복잡도

'''계층적 응집 군집화'''(HAC)의 표준 알고리즘은 시간 복잡도가 $\backslash mathcal\{O\}(n^3)$이며 $\backslash Omega(n^2)$의 메모리가 필요하다. 이는 데이터 포인트 수(n)가 중간 크기만 되어도 계산 속도가 매우 느려질 수 있음을 의미한다.

그러나 몇 가지 특수한 경우에는 더 효율적인 알고리즘이 존재한다. 최단 연결 군집화를 위한 '''SLINK''' 알고리즘^[2]과 최장 연결 군집화를 위한 CLINK 알고리즘^[3]은 $\backslash mathcal\{O\}(n^2)$의 시간 복잡도를 가진다.

일반적인 경우, 힙 자료 구조를 사용하면 실행 시간을 $\backslash mathcal\{O\}(n^2\; \backslash log\; n)$으로 줄일 수 있다. 이는 표준 알고리즘의 $\backslash mathcal\{O\}(n^3)$보다는 개선된 것이지만, 메모리 요구량이 더 늘어난다는 단점이 있어 실제 적용에 제약이 따를 수 있다. 사분 트리를 활용하면 $\backslash mathcal\{O\}(n)$의 공간 복잡도로 $\backslash mathcal\{O\}(n^2)$의 총 실행 시간을 달성하는 방법도 제안되었다.^[4]

한편, 분할 군집화의 경우 모든 가능한 분할을 탐색하는 전수 조사는 $\backslash mathcal\{O\}(2^n)$의 시간 복잡도를 가지므로 현실적으로 사용하기 어렵다. 따라서 ''k''-평균과 같은 더 빠른 휴리스틱(heuristic) 방법을 사용하여 분할을 찾는 것이 일반적이다.

5. 응용 사례 (Agglomerative clustering example)

예를 들어, 위 그림의 데이터를 군집화한다고 가정하고, 유클리드 거리를 거리 척도로 사용한다고 하자.

계층적 군집화 덴드로그램은 다음과 같다.

특정 높이에서 트리를 자르면 선택된 정밀도에서 분할 군집화가 생성된다. 이 예시에서, 덴드로그램의 두 번째 행(상단에서부터) 이후를 자르면 군집 {a} {b c} {d e} {f}가 생성된다. 세 번째 행 이후를 자르면 군집 {a} {b c} {d e f}가 생성되는데, 이는 더 거친 군집화로, 군집의 수는 더 적지만 군집의 크기는 더 크다.

이 방법은 군집을 점진적으로 병합하여 개별 요소로부터 계층 구조를 구축한다. 이 예시에서는 {a} {b} {c} {d} {e} 및 {f}의 6개의 요소가 있다. 첫 번째 단계는 군집에서 병합할 요소를 결정하는 것이다. 일반적으로, 선택된 거리에 따라 가장 가까운 두 요소를 취한다.

선택적으로, 이 단계에서 거리 행렬을 구성할 수도 있는데, 여기서 ''i''번째 행 ''j''번째 열의 숫자는 ''i''번째와 ''j''번째 요소 사이의 거리이다. 그런 다음, 군집화가 진행됨에 따라 군집이 병합되고 거리가 업데이트되면서 행과 열이 병합된다. 이것은 이러한 유형의 군집화를 구현하는 일반적인 방법이며, 군집 간의 거리를 캐싱하는 이점이 있다. 간단한 응집형 군집화 알고리즘은 단일 연결 군집화 페이지에 설명되어 있으며, 다양한 유형의 연결(아래 참조)에 쉽게 적용할 수 있다.

가장 가까운 두 요소 ''b''와 ''c''를 병합했다고 가정하면, 이제 {''a''}, {''b'', ''c''}, {''d''}, {''e''} 및 {''f''}의 군집이 있으며, 이를 더 병합하려고 한다. 이를 위해서는 {a}와 {b c} 사이의 거리를 측정해야 하므로, 두 군집 사이의 거리를 정의해야 한다.

일반적으로 두 군집 $\backslash mathcal\{A\}$와 $\backslash mathcal\{B\}$ 사이의 거리는 다음 중 하나이다.

• 각 군집의 요소 간의 최대 거리 (완전 연결 군집화라고도 함):

:: $\backslash max\; \backslash \{\backslash ,\; d(x,y)\; :\; x\; \backslash in\; \backslash mathcal\{A\},\backslash ,\; y\; \backslash in\; \backslash mathcal\{B\}\backslash ,\backslash \}.$

• 각 군집의 요소 간의 최소 거리 (단일 연결 군집화라고도 함):

:: $\backslash min\; \backslash \{\backslash ,\; d(x,y)\; :\; x\; \backslash in\; \backslash mathcal\{A\},\backslash ,\; y\; \backslash in\; \backslash mathcal\{B\}\; \backslash ,\backslash \}.$

• 각 군집의 요소 간의 평균 거리 (평균 연결 군집화라고도 하며, 예를 들어 UPGMA에서 사용):

:: $\{1\; \backslash over$

}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).

• 모든 내부 군집 분산의 합.
• 병합될 군집의 분산 증가 (Ward의 방법^[8])
• 후보 군집이 동일한 분포 함수에서 생성될 확률 (V-연결).

최소 거리가 동률인 경우, 쌍이 무작위로 선택되므로 여러 구조적으로 다른 덴드로그램을 생성할 수 있다. 또는 모든 동률 쌍을 동시에 결합하여 고유한 덴드로그램을 생성할 수 있다.^[18]

군집의 수가 충분히 작아지면 군집화를 중단할 수 있다(수 기준). 일부 연결은 또한 응집이 이전 응집보다 군집 간 더 큰 거리에서 발생하도록 보장할 수 있으며, 군집을 병합하기에 너무 멀리 떨어져 있으면 군집화를 중단할 수 있다(거리 기준). 그러나, 예를 들어, 중심점 연결의 경우, 소위 역전^[19] (반전, 초거리성 이탈)이 발생할 수 있다.

]

소프트웨어	설명
ALGLIB	C++ 및 C#에서 여러 계층적 군집화 알고리즘 (단일 연결, 완전 연결, 와드)을 구현하며 O(n²) 메모리와 O(n³) 실행 시간을 갖는다.
ELKI	여러 계층적 군집화 알고리즘, 다양한 연결 전략, 효율적인 SLINK,[2] CLINK[3] 및 Anderberg 알고리즘, 덴드로그램에서 유연한 클러스터 추출 및 다양한 다른 군집 분석 알고리즘을 포함한다.
줄리아	Clustering.jl 패키지 내에 구현되어 있다.[21]
옥타브	MATLAB의 GNU 아날로그로 "linkage" 함수에서 계층적 군집화를 구현한다.
오렌지	데이터 마이닝 소프트웨어 스위트로, 대화형 덴드로그램 시각화를 통해 계층적 군집화를 포함한다.
R	계층적 군집화를 위한 기능을 제공하는 내장 함수[22] 및 패키지가 있다.[23][24][25]
SciPy	효율적인 SLINK 알고리즘을 포함하여 Python에서 계층적 군집화를 구현한다.
scikit-learn	Python에서 계층적 군집화를 구현한다.
Weka	계층적 클러스터 분석을 포함한다.