계층적 군집화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

계층적 군집화는 개별 데이터 포인트를 점진적으로 병합하거나 전체 데이터 집합을 분할하여 데이터의 계층 구조를 형성하는 군집화 방법이다. 응집형 군집화는 가장 유사한 클러스터를 병합하는 상향식 방식이며, 분할형 군집화는 클러스터를 분할하는 하향식 방식이다. 클러스터 간의 거리를 정의하는 연결 기준에 따라 단일 연결, 완전 연결, 평균 연결 등 다양한 방식으로 군집화를 수행할 수 있으며, 계산 복잡도는 알고리즘에 따라 다르다. 계층적 군집화는 유클리드 거리와 덴드로그램을 활용하여 데이터를 시각화하고 분석하는 데 사용되며, 다양한 프로그래밍 언어와 소프트웨어에서 구현되어 활용된다.

계층적 군집화

📚 더 읽어볼만한 페이지

클러스터 분석 알고리즘 - 기댓값 최대화 알고리즘
클러스터 분석 알고리즘 - DBSCAN
DBSCAN은 밀도 기반 공간 클러스터링 알고리즘으로, 데이터 공간에서 밀도가 높은 영역을 클러스터로 식별하는 비지도 학습 방법이며, 핵심점, 직접 도달 가능점, 도달 가능점, 이상치라는 네 가지 기본 개념을 바탕으로 임의의 모양을 가진 클러스터를 찾을 수 있다는 장점이 있다.

1. 개요
2. 종류
- 2.1. 응집형 (Agglomerative)
- 2.2. 분할형 (Divisive)
3. 클러스터 연결 (Cluster Linkage)
- 3.1. 연결 기준 (Linkage Criteria)
4. 계산 복잡도
5. 응용 사례 (Agglomerative clustering example)

2. 종류

계층적 군집화는 크게 두 가지 방식으로 나눌 수 있다: 응집형(agglomerative) 방식과 분할형(divisive) 방식이다.

* 응집형 (Agglomerative): 개별 데이터 포인트 각각을 하나의 클러스터로 간주하고 시작하여, 가장 유사한 클러스터들을 점진적으로 병합해 나가는 상향식(bottom-up) 접근법이다. 모든 데이터가 하나의 큰 클러스터에 속할 때까지 병합 과정을 반복한다.
* 분할형 (Divisive): 전체 데이터셋을 하나의 클러스터로 보고 시작하여, 특정 기준에 따라 점차 더 작은 클러스터들로 나누어 나가는 하향식(top-down) 접근법이다. 각 데이터 포인트가 개별 클러스터가 될 때까지 분할 과정을 반복한다.

2.1. 응집형 (Agglomerative)

--

응집형 방식은 개별 데이터 포인트(요소)에서 시작하여 가장 유사한 클러스터들을 점진적으로 병합해 나가는 상향식(bottom-up) 방법이다. 초기에는 각 데이터 포인트가 하나의 독립된 클러스터를 형성한다. 알고리즘은 반복적으로 가장 가까운 두 클러스터를 찾아 하나의 클러스터로 합치는 과정을 모든 데이터 포인트가 단일 클러스터에 속할 때까지 계속한다.

예를 들어, 위 그림의 데이터를 유클리드 거리를 거리 척도로 사용하여 군집화한다고 가정해 보자. 이 과정을 시각화한 것이 오른쪽의 덴드로그램이다. 덴드로그램을 특정 높이에서 가로로 자르면, 그 높이에 해당하는 군집 구조를 얻을 수 있다. 예를 들어, 덴드로그램의 위에서 두 번째 가로선(병합 단계) 이후에 자르면 {a}, {b c}, {d e}, {f}라는 4개의 군집이 생성된다. 세 번째 가로선 이후에 자르면 {a}, {b c}, {d e f}라는 3개의 군집이 생성되며, 이는 군집 수는 적지만 각 군집의 크기는 더 큰, 상대적으로 덜 세분화된 군집화 결과이다.

알고리즘의 첫 단계에서는 어떤 요소들을 먼저 병합할지 결정한다. 보통 미리 정의된 거리 척도에 따라 가장 가까운 두 요소를 선택하여 병합한다. 예를 들어, 위 예시에서는 요소 'b'와 'c'가 가장 가깝다고 가정하고 이 둘을 병합하여 {b, c}라는 새로운 클러스터를 만든다. 그러면 현재 클러스터는 {a}, {b, c}, {d}, {e}, {f}가 된다.

이 과정에서 거리 행렬을 미리 계산해 두면 효율적이다. 거리 행렬은 각 요소 쌍 사이의 거리를 저장한 행렬이다. 군집화가 진행되면서 클러스터들이 합쳐지면, 이 거리 행렬의 행과 열도 함께 병합되고 클러스터 간의 거리가 새롭게 계산되어 업데이트된다. 이는 응집형 군집화를 구현하는 일반적인 방식이며, 클러스터 간의 거리를 캐싱하여 계산 효율성을 높이는 장점이 있다. 간단한 응집형 군집화 알고리즘은 단일 연결 군집화 문서에 설명되어 있으며, 다양한 연결(linkage) 기준에 쉽게 적용될 수 있다.

다음 단계로 넘어가기 위해서는 새로 생성된 클러스터({b, c})와 다른 클러스터({a}, {d}, {e}, {f}) 간의 거리를 계산해야 한다. 따라서 두 클러스터

\mathcal{A}

와

\mathcal{B}

사이의 거리를 어떻게 정의할지가 중요하다. 일반적으로 사용되는 클러스터 간 거리 정의(연결 기준)는 다음과 같다.

* 최대 연결 (Complete-linkage clustering): 두 클러스터에 속한 모든 데이터 포인트 쌍 간의 거리 중 최댓값. 완전 연결 군집화라고도 한다.
:

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

* 최소 연결 (Single-linkage clustering): 두 클러스터에 속한 모든 데이터 포인트 쌍 간의 거리 중 최솟값. 단일 연결 군집화라고도 한다.
:

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

* 평균 연결 (Average-linkage clustering): 두 클러스터에 속한 모든 데이터 포인트 쌍 간의 거리의 평균값. UPGMA와 같은 방법에서 사용된다.
:

{1 \over

👆

좌우로 밀어서 보기

}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).
* 모든 내부 클러스터 분산의 합.
* 클러스터 병합 시 증가하는 분산의 양 (Ward의 방법).
* 두 클러스터가 동일한 분포 함수에서 생성되었을 확률 (V-linkage).

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

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

2.2. 분할형 (Divisive)

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

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

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

1. 분할할 클러스터( $C_*$ )를 선택한다. 보통 현재 클러스터들 중에서 직경(가장 멀리 떨어진 두 객체 간의 거리)이 가장 큰 클러스터를 선택한다.
2. 선택된 클러스터( $C_*$ ) 내에서, 다른 객체들과의 평균 이질성(거리 또는 비유사성의 평균값)이 가장 큰 객체( $i^*$ )를 찾는다. 이 객체는 현재 클러스터에서 가장 "어울리지 않는" 객체로 간주될 수 있다.
3. 이 가장 이질적인 객체( $i^*$ )를 이용하여 새로운 클러스터, 즉 분열 그룹( $C_\textrm{new}$ )을 만들기 시작한다. 처음에는 이 그룹에 $i^*$ 만 포함된다.
4. 원래 클러스터( $C_*$ )에 남아 있는 다른 객체들을 검토한다. 각 객체( $i$ )에 대해, 원래 클러스터( $C_*$ )에 남아 있는 다른 객체들과의 평균 이질성( $\frac{1}{|C_*|-1}\sum_{j\in C_*\setminus\{i\}} \delta(i,j)$ )과 새로 생긴 분열 그룹( $C_\textrm{new}$ ) 내 객체들과의 평균 이질성( $\frac{1}$

👆

좌우로 밀어서 보기

\sum_{j\in C_\textrm{new}} \delta(i,j))을 비교한다.
5. 만약 어떤 객체(

i

)가 원래 클러스터의 나머지 객체들보다 새로 생긴 분열 그룹에 더 가깝다면(즉,

D(i) = \frac{1}{|C_*|-1}\sum_{j\in C_*\setminus\{i\}} \delta(i,j) - \frac{1}

👆

좌우로 밀어서 보기

\sum_{j\in C_\textrm{new}} \delta(i,j) 값이 양수(+)로 크다면), 해당 객체를 분열 그룹(

C_\textrm{new}

)으로 이동시킨다. 이 과정은 더 이상 분열 그룹으로 이동할 객체가 없을 때까지 (즉, 모든 남은 객체에 대해

D(i)

값이 음수(-)가 될 때까지) 반복된다.
6. 분할이 완료되면, 원래 클러스터(

C_*

)는 크기가 줄어들고, 새로운 클러스터(

C_\textrm{new}

)가 생성된다. 이 두 클러스터를 기존 클러스터 목록에 추가하고, 전체 클러스터 수가 데이터 개수(

n

)와 같아질 때까지 위의 과정을 반복한다.

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

DIANA 알고리즘의 결과는 덴드로그램으로 시각화할 수 있다. 각 분할 단계에서 새로 생성된 분열 그룹(

C_\textrm{new}

)을 원래 클러스터(

C_*

)의 자식 노드로 연결하면, 전체 데이터를 루트로 하고 개별 데이터 포인트를 리프 노드로 하는 계층적 트리 구조를 만들 수 있다.

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

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

3.1. 연결 기준 (Linkage Criteria)

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

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

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

👆

좌우로 밀어서 보기

이름

공식

최대 또는 완전 연결 군집화

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

최소 또는 단일 연결 군집화

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

평균 연결 군집화 (비가중, UPGMA)

\frac{1}{>A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b).

평균 연결 군집화 (가중, WPGMA)

d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}.

중심 연결 군집화 (비가중, UPGMC)

\lVert \mu_A-\mu_B\rVert^2

(여기서

\mu_A

와

\mu_B

는 각각 A와 B의 중심)

중앙값 연결 군집화 (가중, WPGMC)

d(i\cup j, k) = d(m_{i\cup j}, m_k)

(여기서

m_{i\cup j} = \tfrac{1}{2}\left(m_i + m_j\right)

)

다양한 연결 군집화

\sqrt[p]{\frac{1}{>A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b)^p}, p\neq 0

Ward 연결, 최소 제곱합 증가 (MISSQ)

\frac{>A|\cdot|B|}

👆

좌우로 밀어서 보기

\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)

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

분산 최소 증가 (MIVAR)

\frac{1}{>A\cup B|}\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)	\frac{1}{>A\cup B\|}\sum_{x\in A\cup B} \lVert x - \mu_{A\cup B} \rVert^2 = \text{Var}(A\cup B)
하우스도르프 연결	$\max_{x\in A\cup B} \min_{y\in A\cup B} d(x,y)$
최소 합 메도이드 연결	$\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m, y)$ (여기서 m은 결과 클러스터의 메도이드)
최소 합 증가 메도이드 연결	$\min_{m\in A\cup B} \sum_{y\in A\cup B} d(m,y) - \min_{m\in A} \sum_{y\in A} d(m,y) - \min_{m\in B} \sum_{y\in B} d(m,y)$
메도이드 연결	$d(m_A, m_B)$ (여기서 $m_A$ , $m_B$ 는 이전 클러스터의 메도이드)
최소 에너지 군집화	\frac {2}{nm}\sum_{i,j=1}^{n,m} \>a_i- b_j\\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \\|a_i-a_j\\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \\|b_i-b_j\\|_2

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

이 외에도 다른 연결 기준들이 존재한다.
* 후보 클러스터들이 동일한 분포 함수에서 생성될 확률 (V-연결)
* k-최근접 이웃 그래프의 차수(degree)의 곱 (그래프 차수 연결)
* 두 클러스터를 병합했을 때 특정 클러스터 설명자(클러스터 품질 측정 지표)의 증가량

특히 널리 사용되는 연결 기준은 다음과 같이 두 클러스터

\mathcal{A}

와

\mathcal{B}

사이의 거리를 정의한다.
* [[완전 연결 군집화|최대 연결(Complete-linkage)]]: 각 클러스터에 속한 요소 간 거리의 최댓값.
* [[단일 연결 군집화|최소 연결(Single-linkage)]]: 각 클러스터에 속한 요소 간 거리의 최솟값.
* 평균 연결(Average-linkage): 각 클러스터에 속한 요소 간 거리의 평균값. UPGMA 등에서 사용된다.
* [[Ward's method|Ward 연결]]: 클러스터를 병합했을 때 발생하는 클러스터 내 분산의 증가량.

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

4. 계산 복잡도

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

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

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

한편, 분할 군집화의 경우 모든 가능한 분할을 탐색하는 전수 조사는 $\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} 사이의 거리를 측정해야 하므로, 두 군집 사이의 거리를 정의해야 한다.
일반적으로 두 군집

\mathcal{A}

와

\mathcal{B}

사이의 거리는 다음 중 하나이다.
* 각 군집의 요소 간의 최대 거리 (완전 연결 군집화라고도 함):
::

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

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

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

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

{1 \over

👆

좌우로 밀어서 보기

}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y).
* 모든 내부 군집 분산의 합.
* 병합될 군집의 분산 증가 (Ward의 방법)
* 후보 군집이 동일한 분포 함수에서 생성될 확률 (V-연결).

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

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

아이리스 데이터 세트에 대한 계층적 군집화 덴드로그램 (R 사용). [https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html 출처

]

오렌지 데이터 마이닝 스위트에서 계층적 군집화 및 대화형 덴드로그램 시각화.

👆

좌우로 밀어서 보기

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