계층적 군집화

통계 수치해석 마지막 수정: 2026-08-31 04:52:38

1. 개요[편집]

계층적 군집화 Hierarchical Clustering
방향	병합형(bottom-up) · 분할형(top-down)
출력	덴드로그램 — 군집 수는 사후에 절단으로 결정
연결 기준	단일 · 완전 · 평균(UPGMA) · 중심 · 워드
통합 공식	램스-윌리엄스 갱신식
복잡도	소박 $O(n^3)$ → NN-체인 $O(n^2)$
메모리	거리행렬 $O(n^2)$ — 대용량의 벽
충실도 지표	코페네틱 상관계수

계층적 군집화(hierarchical clustering)는 자료를 하나의 평면적 분할로 나누는 대신, 군집이 군집을 포함하는 중첩 구조 전체를 만들어 내는 군집화 방법이다. 결과물은 라벨 벡터가 아니라 덴드로그램(dendrogram) — 어느 높이에서 자르느냐에 따라 군집 수가 달라지는 나무다.

k-평균 군집화와의 차이가 여기서 갈린다. k-평균은 $k$ 를 먼저 정해야 하고 그 값이 바뀌면 처음부터 다시 돌려야 하지만, 계층적 군집화는 한 번 돌려 놓고 나중에 절단 높이를 옮겨 가며 $k=2$ 도 $k=17$ 도 즉시 읽는다. “군집이 몇 개인지 모르겠다”는 상황, 그리고 “군집 안의 하위 구조가 궁금하다”는 상황이 이 방법의 홈그라운드다.

대가는 두 가지다. 병합이 되돌려지지 않는 탐욕적 결정이라 한 번 잘못 붙인 것은 영원히 붙어 있고, 거리행렬을 들고 있어야 해서 표본 수 수만을 넘기면 메모리부터 터진다.

2. 병합형과 분할형[편집]

병합형(agglomerative, AGNES)은 아래에서 위로 간다.

모든 점을 각자 하나의 군집으로 둔다( $n$ 개).
현재 군집들 중 가장 가까운 두 개를 찾아 합친다.
합쳐진 군집과 나머지 사이의 거리를 갱신한다.
군집이 하나 남을 때까지 2~3을 반복.

실무에서 “계층적 군집화”라고 하면 사실상 이쪽을 가리킨다. 3번의 “거리 갱신”을 어떻게 정의하느냐가 곧 연결 기준이고, 그것이 결과의 성격을 거의 다 결정한다.

분할형(divisive, DIANA)은 전체를 하나로 놓고 위에서부터 쪼갠다. 어느 지점에서 자를지 정확히 고르려면 $2^{n-1}-1$ 가지 이분을 봐야 하므로 실제로는 휴리스틱을 쓴다 — 가장 지름이 큰 군집을 골라 평균 비유사도가 가장 큰 점을 씨앗으로 떼어 내는 DIANA 방식, 또는 매번 k-평균 군집화로 둘로 쪼개는 이분 k-평균(bisecting k-means)이 대표적이다.

둘 중 어느 쪽이 나은가는 원하는 군집 수가 트리의 어느 쪽에 있느냐에 달렸다. 큰 덩어리 몇 개만 필요하면 분할형이 초반 몇 스텝으로 끝나고 전역 구조를 먼저 보므로 유리하고, 세밀한 하위 구조가 목적이면 병합형이 자연스럽다. 문헌과 소프트웨어 지원은 압도적으로 병합형 쪽에 몰려 있다.

3. 덴드로그램과 절단 높이[편집]

덴드로그램의 세로축은 두 군집이 합쳐진 시점의 거리다. 높이 $t$ 에서 수평으로 자르면 그 선 아래의 연결 성분들이 군집이 된다. 그래서 계층적 군집화에서 “군집 수 결정”은 모형 선택이 아니라 그림을 읽는 행위가 된다.

큰 도약을 찾는다. 병합 높이의 수열에서 갑자기 크게 뛰는 지점 바로 아래가 자연스러운 절단이다. 팔꿈치 방법의 계층 판본이며, 근거가 통계적이라기보다 시각적이라는 점은 정직하게 인정해야 한다.
실루엣이나 갭 통계량으로 후보 $k$ 를 비교한다. 실루엣 계수를 여러 절단 높이에 대해 계산해 최댓값을 고르는 것이 흔한 절충.
거리 임계값이 도메인에서 오는 경우가 최선이다. “RMSD 2 Å 이내는 같은 구조로 본다” 같은 기준이 있으면 $k$ 논쟁이 아예 사라진다.

덴드로그램이 그림으로 읽히려면 병합 높이가 단조 증가해야 한다. 대부분의 연결 기준은 이를 보장하지만, 중심 연결과 중앙값 연결은 역전(inversion)을 만들 수 있다 — 나중에 합쳐진 쌍이 더 낮은 높이에 그려져 가지가 아래로 꺾이는 기괴한 그림이 나온다. 그 두 기준이 실무에서 잘 안 쓰이는 결정적인 이유다.

주의할 것 하나. 덴드로그램에서 가지의 좌우 순서는 정보가 아니다. 각 병합에서 어느 쪽을 왼쪽에 그릴지는 $2^{n-1}$ 가지 자유가 있고 소프트웨어가 임의로 고른다. 잎의 순서를 보고 “A와 B가 이웃하니 비슷하다”고 읽으면 안 된다.¹

4. 연결 기준[편집]

$d(A,B)$ 를 군집 $A$ , $B$ 사이의 거리로 정의하는 방식.

기준	정의	성격과 편향
단일 (최소)	두 군집 원소 쌍 중 최소 거리	체이닝. 길쭉한 형태를 잘 잡지만 다리 하나로 이어짐
완전 (최대)	원소 쌍 중 최대 거리	조밀한 구형 선호. 큰 군집을 부수고 이상치에 민감
평균 (UPGMA)	모든 쌍 거리의 산술평균	단일과 완전의 절충, 계통학의 표준
중심	두 중심 사이 거리	역전 발생. 유클리드 전용
워드	병합으로 늘어나는 군집내 제곱합	크기가 비슷한 구형 군집 선호. 실무 기본값

단일 연결의 체이닝은 이 방법의 대표적 병리다. 서로 멀리 떨어진 두 군집이라도 그 사이에 점 몇 개가 징검다리처럼 놓여 있으면 통째로 이어진다. 그런데 이 성질이 곧 장점이 되는 자리도 있다 — 초승달 모양처럼 비볼록한 군집은 오직 단일 연결과 DBSCAN 계열만 잡는다. 이론적으로도 특별한데, 단일 연결 덴드로그램은 자료의 최소 신장 트리에서 간선을 무게 순으로 제거하며 얻는 것과 정확히 같다. 그래서 크러스컬 알고리즘 한 번이면 단일 연결 계층이 통째로 나온다.

워드 연결(Ward 1963)은 다르게 정의된다. 거리가 아니라 병합 비용을 최소화한다.

\Delta(A,B) = \frac{\lvert A\rvert\,\lvert B\rvert}{\lvert A\rvert+\lvert B\rvert}\, \bigl\lVert \boldsymbol\mu_A - \boldsymbol\mu_B \bigr\rVert^2

이 값이 정확히 $A$ 와 $B$ 를 합칠 때 늘어나는 군집내 제곱합(관성) 이다. 즉 워드 연결은 “매 단계에서 관성 증가가 가장 작은 병합을 고르는 탐욕 알고리즘”이고, 목적함수가 k-평균과 같다. 결과적으로 워드 덴드로그램을 $k$ 개로 자른 것은 k-평균의 계층적·탐욕적 판본이며, 실제로 k-평균의 초기 중심을 워드 결과로 잡는 것이 좋은 초기화 전략으로 알려져 있다. 두 방법이 비슷한 답을 내는 것은 우연이 아니라 같은 관성을 서로 다른 방식으로 줄이기 때문이다. 다만 워드는 관성이 정의되어야 하므로 유클리드 거리 전용이다 — 상관 거리 행렬에 워드를 걸면 소프트웨어는 아무 불평 없이 숫자를 뱉지만 그 숫자에는 근거가 없다.

5. 램스-윌리엄스 갱신식[편집]

위의 기준들이 제각각으로 보이지만, 사실 하나의 점화식의 특수해다. $A$ 와 $B$ 를 합쳐 $A\cup B$ 를 만들었을 때 제3의 군집 $C$ 와의 거리는

d(A\cup B,\, C) = \alpha_A d(A,C) + \alpha_B d(B,C) + \beta\, d(A,B) + \gamma\,\bigl\lvert d(A,C)-d(B,C)\bigr\rvert

로 쓸 수 있고, 계수 넷만 바꾸면 모든 기준이 나온다. 표에서 $n_A$ 등은 군집 크기, $n_{ABC}=n_A+n_B+n_C$ 다.

기준	$\alpha_A$	$\beta$	$\gamma$
단일	1/2	0	−1/2
완전	1/2	0	+1/2
평균 (UPGMA)	$n_A/(n_A{+}n_B)$	0	0
중심	$n_A/(n_A{+}n_B)$	$-n_An_B/(n_A{+}n_B)^2$	0
워드	$(n_A{+}n_C)/n_{ABC}$	$-n_C/n_{ABC}$	0

실용적 의미가 크다. 원본 자료 좌표가 없어도 거리행렬만 있으면 전 과정이 돌아가고, 구현이 기준마다 따로 필요 없이 계수 표 하나로 끝난다. 유전자 발현 프로파일이든 문서 유사도든 “거리는 정의할 수 있지만 벡터로는 못 쓰는” 자료에 계층적 군집화가 강한 이유가 이것이다(워드·중심 연결은 예외 — 유클리드 좌표를 전제한다).

6. 계산 복잡도 — 대용량에서 못 쓰는 이유[편집]

소박한 구현 $O(n^3)$ . 매 병합마다 거리행렬 전체를 훑어 최솟값을 찾으면 $O(n^2)$ , 이를 $n-1$ 번 하면 $O(n^3)$ .
우선순위 큐 $O(n^2\log n)$ . 각 군집의 최근접 이웃을 우선순위 큐로 관리한다. 갱신되는 항목이 많아 상수가 크다.
NN-체인 $O(n^2)$ . 임의의 점에서 출발해 최근접 이웃을 따라가다 상호 최근접 이웃 쌍(서로가 서로의 최근접)을 만나면 그 둘은 지금 합쳐도 최종 결과가 같다는 성질을 이용해, 체인을 유지하며 병합한다. 이 성질이 성립하려면 연결 기준이 축소 가능(reducible)해야 하는데 — 단일·완전·평균·워드는 만족하고 중심·중앙값은 만족하지 않는다. 역전이 생기는 기준과 정확히 겹친다는 것이 우연이 아니다.
SLINK / CLINK $O(n^2)$ 시간, $O(n)$ 공간. 단일 연결(SLINK, Sibson 1973)과 완전 연결(CLINK, Defays 1977)에 특화된 알고리즘. 거리행렬을 통째로 들고 있지 않아도 되는 것이 핵심이며, 거리를 필요할 때 계산하면 메모리 벽을 넘긴다.

$O(n^2)$ 는 이론적으로 최적이다 — 거리행렬을 한 번은 봐야 하니까. 문제는 그게 메모리에도 $O(n^2)$ 라는 것이다. $n=10^5$ 이면 배정밀도 거리행렬만 40 GB다. 그래서 대용량에서는

표본 수만 개로 계층 구조를 만들고 나머지는 가장 가까운 군집에 배정하거나,
BIRCH처럼 자료를 먼저 요약 트리로 압축한 뒤 그 요약에 계층적 군집화를 걸거나,
아예 DBSCAN이나 미니배치 k-평균처럼 선형에 가까운 방법으로 갈아탄다.

“일단 계층적으로 돌려 보고 구조를 파악한 다음, 확정된 $k$ 로 전체에 k-평균을 돌린다”는 2단 조합이 실무에서 가장 흔한 타협이다.

7. 거리 척도와 표준화 — 결과를 뒤집는 자리[편집]

알고리즘보다 거리 정의가 결과를 더 크게 바꾼다. 이건 과장이 아니라 실무에서 반복 확인되는 사실이다.

유클리드: 절대적 크기 차이에 반응한다. 워드·중심 연결의 전제.
상관 거리 $1-\rho$ : 크기를 무시하고 패턴의 모양만 본다. 유전자 발현이나 시계열 프로파일 군집화의 기본값. “값은 다르지만 같이 오르내리는 것”을 묶고 싶을 때.
마할라노비스 거리: 변수 간 상관을 보정한다. 공분산을 잘 추정할 수 있을 때만.
코사인·자카드: 희소 고차원(문서, 집합)에서.

그리고 표준화. 변수 단위가 mm와 MPa처럼 다르면 스케일이 큰 변수가 거리를 독점한다. $z$ -점수 표준화가 기본 처방이지만 만능은 아니다 — 잡음뿐인 변수도 분산 1로 부풀려 발언권을 똑같이 주기 때문이다. 실무 원칙은 “표준화 여부를 알고리즘이 아니라 도메인 지식으로 결정하고, 두 판본을 모두 돌려 결론이 바뀌는지 확인한다”에 가깝다. 이상치에 스케일이 끌려가는 것이 걱정되면 표준편차 대신 MAD로 나누는 로버스트 표준화를 쓴다(로버스트 통계).

고차원에서는 거리 자체가 의미를 잃는 차원의 저주가 그대로 작동하므로, 주성분 분석으로 먼저 줄이고 군집화하는 것이 표준 전처리다.

8. 덴드로그램은 얼마나 믿을 만한가[편집]

계층적 군집화는 자료에 계층 구조가 없어도 항상 덴드로그램을 그려 준다. 완전한 균일 난수를 넣어도 그럴듯한 나무가 나온다. 그래서 충실도 점검이 필요하다.

코페네틱 상관계수가 표준 도구다. 덴드로그램에서 점 $i,j$ 가 처음 같은 군집이 되는 높이를 코페네틱 거리 $c_{ij}$ 라 하고, 원래 거리 $d_{ij}$ 와의 피어슨 상관을 잰다.

r_c = \mathrm{corr}\bigl(\{d_{ij}\},\ \{c_{ij}\}\bigr)

1에 가까울수록 나무가 원래 거리 구조를 잘 보존한 것이다. 관행적으로 0.75 이상이면 받아들일 만하다고 보지만, 이건 임계값이라기보다 여러 연결 기준을 비교할 때의 상대적 잣대로 쓰는 것이 정직하다. 평균 연결(UPGMA)이 코페네틱 상관을 거의 항상 가장 높게 만드는데, 그것이 곧 “가장 의미 있는 군집화”라는 뜻은 아니다 — 정의상 평균 거리를 보존하도록 만들어졌으니 당연한 결과다.²

부트스트랩으로 자료를 재표집해 같은 가지가 몇 % 재현되는지 세는 안정성 검사도 널리 쓰인다(계통학의 부트스트랩 지지도가 그것). 알고리즘이 결정론적이라는 것과 결과가 안정적이라는 것은 전혀 다른 이야기다.

9. 시뮬레이션 현장에서[편집]

파라미터 스터디 결과의 군집화. 수백~수천 케이스를 돌린 뒤 응답이 비슷한 케이스들을 묶으면 설계 공간의 거동 영역 지도가 나온다. 유동이 부착에서 박리로 넘어가는 경계, 좌굴 모드가 바뀌는 경계 같은 것들이 군집 경계로 드러난다. 대리 모델을 영역별로 따로 세우는 국소 대리모형 전략의 출발점이며, 실험계획법의 추가 표본을 어디에 뿌릴지 정하는 데도 쓴다.
메시 분할과 도메인 분해. 병렬 해석에서 격자를 프로세서 수만큼 나누는 문제는 사실상 재귀적 이분이다. 그래프 분할 관점의 재귀 좌표/스펙트럴 이분이 전형적인 분할형 계층 절차이고, METIS 같은 다단계 기법의 조대화 단계는 정점을 짝지어 합치는 병합형 절차다. 목적함수가 관성이 아니라 간선 절단과 부하 균형이라는 점만 다르고 골격은 같다. 실제 해석 파이프라인의 이야기는 영역 분할법 문서 참고.
분자동역학 궤적의 구조 군집화. 분자동역학 궤적 수십만 프레임에서 대표 구조를 뽑는 표준 절차가 RMSD 거리행렬 위의 계층적 군집화다. 여기서 계층적 방법이 선호되는 이유가 분명하다 — “구조가 몇 종류인지”를 미리 알 수 없고, “RMSD 2 Å 이내면 같은 상태”처럼 절단 높이를 물리적으로 정할 수 있기 때문이다. 다만 프레임 수가 많아 $O(n^2)$ 거리행렬이 곧바로 벽이 되므로, 시간 간격을 성기게 잡거나 표본 후 배정 전략을 쓴다.
축소차수 모형의 스냅숏 군집화. 적합직교분해 기저 하나로 전 구간을 덮으면 모드 수가 폭발하는 강한 비선형 문제에서, 스냅숏을 먼저 군집화하고 군집마다 국소 기저를 만드는 전략이 있다. 계층 구조가 있으면 “몇 개의 국소 기저로 나눌지”를 정밀도 요구에 맞춰 사후에 조절할 수 있다. 축소차수모델 문서의 국소 ROM 절이 같은 이야기.
이상치의 조기 노출. 병합 순서에서 끝까지 혼자 남는 점이 곧 이상치 후보다. 덴드로그램 오른쪽 끝에 홀로 매달린 긴 가지 하나는 “이 케이스만 뭔가 다르다”는 신호이며, 이상치 탐지의 군집 기반 접근이 정확히 이 관찰을 알고리즘으로 만든 것이다.³

10. 한계[편집]

탐욕적이고 되돌릴 수 없다. 초반의 잘못된 병합은 끝까지 남는다. 전역 최적 계층을 찾는 문제가 아니라는 것을 인정하고 쓰는 도구다.
이상치에 약하다. 특히 완전 연결. 점 하나가 군집 지름을 결정하므로 병합 순서가 통째로 흔들린다.
$O(n^2)$ 메모리. 위에서 본 그대로.
군집이 없어도 나온다. 코페네틱 상관과 안정성 검사를 붙이지 않으면 난수에서 구조를 발견했다고 보고하게 된다.
연결 기준이 곧 군집의 정의다. “구형 군집”과 “이어진 덩어리”는 다른 개념이고, 단일 연결과 워드 연결은 서로 다른 질문에 답한다. 기본값을 그냥 쓰면 자기가 무슨 질문을 했는지 모르는 채로 답을 받게 된다.

밀도 기반(DBSCAN), 확률 기반(가우시안 혼합 모형), 그래프 기반(스펙트럴 군집화)과 비교해 계층적 군집화의 자리는 명확하다 — 군집 수를 모르고, 표본이 그리 많지 않고, 중첩 구조 자체가 답의 일부인 문제.

11. 관련 문서[편집]

그럼에도 히트맵 옆에 덴드로그램을 붙여 놓으면 사람은 반드시 잎 순서를 의미로 읽는다. 그래서 최적 잎 순서 정렬(optimal leaf ordering)이라는 별도의 알고리즘이 존재한다 — 트리 구조를 바꾸지 않는 범위에서 인접 잎의 거리 합이 최소가 되도록 좌우를 뒤집는 것. 그림이 예뻐지는 것 이상의 정보는 없지만, 사람이 그림을 오독하는 것을 막아 준다는 점에서는 정직한 도구다. ↩
“코페네틱”(cophenetic)이라는 단어는 표현형(phenetic) 분류학에서 왔다. 계층적 군집화의 용어 절반이 생물 분류학 출신인 것은 우연이 아니라, 1960년대 수리분류학(numerical taxonomy)이 이 방법론을 사실상 만들어 냈기 때문이다. 공학자가 쓰는 덴드로그램은 원래 종의 계통도였다. ↩
반대로 이 성질이 함정이 되기도 한다. 단일 연결에서 이상치는 마지막까지 안 붙는 게 아니라 아무 데나 붙어 다리를 놓는다. 이상치 하나가 떨어져 있던 두 군집을 이어 버리면 덴드로그램 상단이 통째로 무의미해진다. 군집화 전에 이상치를 한 번 훑는 것이 순서인 이유. ↩