계층적 군집화 방법이란? 핵심 원리와 두 가지 유형 총정리

계층적 군집화(hierarchical clustering)는 데이터 객체들을 하나의 클러스터 트리 구조로 묶어 나가는 대표적인 군집 분석 기법입니다. 이에 속한 알고리즘은 크게 상향식(bottom-up)과 하향식(top-down)으로 나뉩니다. 다만 계층적 군집화는 병합(merge) 또는 분할(split) 결정이 한번 내려지면 이를 되돌리거나 조정할 수 없기 때문에, 초기 판단에 따라 결과의 품질이 저하될 수 있다는 한계를 지닙니다.

클러스터 간 거리 측정 기준

클러스터의 병합 여부는 클러스터 사이의 거리를 기준으로 판단합니다. 널리 사용되는 클러스터 간 거리 측도는 다음과 같습니다. 여기서 mi는 클러스터 Ci의 평균값, ni는 Ci에 포함된 점(point)의 개수, |p − p′|는 두 점 p와 p′ 사이의 거리를 의미합니다.

계층적 군집화 방법의 두 가지 유형

1. 병합형 계층적 군집화 (Agglomerative Hierarchical Clustering, AHC)

AHC는 상향식(bottom-up) 군집화 방법으로, 각 클러스터가 더 작은 하위 클러스터들을 포함하는 계층 구조를 형성합니다. 처음에는 모든 객체를 각각 독립된 클러스터로 배치한 뒤, 이러한 원자적(atomic) 클러스터들을 점차 더 큰 클러스터로 병합해 나갑니다. 모든 객체가 하나의 클러스터에 속하게 되거나 특정 종료 조건을 충족하면 과정이 종료됩니다.

대부분의 계층적 군집화 방법이 이 유형에 해당하며, 서로 다른 기법들은 클러스터 간 유사도를 정의하는 방식에서만 차이를 보입니다.

대표적인 예로 AGNES(Agglomerative Nesting)라는 알고리즘이 있으며, 단일 연결(single-link) 기법을 활용합니다. 사각형 영역 안에 놓인 객체 집합을 예로 들면, 처음에는 각 객체가 자신만의 클러스터에 배치됩니다. 이후 클러스터 내에서 가장 가까운 객체들 사이의 유클리드 거리(Euclidean distance)가 최소가 되는 클러스터부터 순서대로 병합해 나갑니다.

2. 분리형 계층적 군집화 (Divisive Hierarchical Clustering, DHC)

DHC는 하향식(top-down) 접근 방식으로, 병합형에 비해 덜 사용됩니다. 작동 원리는 병합형 군집화와 동일하지만 진행 방향이 정반대입니다. 모든 객체를 포함하는 단일 클러스터에서 시작하여, 생성된 클러스터를 연속적으로 분할해 나갑니다. 개별 객체만 남은 클러스터가 되거나, 원하는 클러스터 수에 도달했거나, 가장 가까운 두 클러스터 간 거리가 특정 임계값을 초과하는 등의 종료 조건이 충족되면 중단합니다.

분리형 방법은 상위 수준에서 올바른 분할 결정을 내리기가 어렵기 때문에 일반적으로 널리 활용되지 않으며 실제 적용 사례도 드뭅니다. DIANA(Divisive Analysis)가 대표적인 분리형 계층적 군집화 방법의 예입니다. 병합형과 정반대 순서로 작동하며, 처음에 모든 객체를 하나의 클러스터에 배치한 후, 클러스터 내 인접 객체들 사이의 유클리드 거리가 최대가 되는 지점을 기준으로 클러스터를 분할해 나갑니다.

병합형 vs 분리형 한눈에 비교하기