계층적 군집화(Hierarchical clustering)는 계층적 군집 분석(HCA)이라고도 불리며, 데이터 마이닝과 통계 분야에서 군집의 계층 구조를 구축하는 군집 분석 방법이다. k-평균과 같은 분할적 방법과 달리 군집 수를 사전에 지정할 필요가 없으며, 계층적 군집화는 중첩된 구조를 생성하여 어느 수준에서든 절단하여 다양한 수의 군집을 얻을 수 있다. 결과는 일반적으로 병합 또는 분할의 순서를 보여주는 나무 모양의 다이어그램인 덴드로그램으로 제시된다. 이 접근법은 생물학, 사회 과학, 기계 학습과 같은 분야에서 탐색적 데이터 분석에 널리 사용된다.
계층적 군집화의 주요 장점은 유연성이다. 유효한 거리 측정법을 모두 사용할 수 있으며, 관측값 자체가 필요하지 않고 거리 행렬만 있으면 된다. 그러나 단일 연결 거리라는 특수한 경우를 제외하고는, 어떤 알고리즘도 완전 탐색 없이 최적해를 보장할 수 없으며, 이 경우 시간 복잡도는 O(2^n)이다.
응집적 및 분할적 전략
계층적 군집화 전략은 일반적으로 응집적(agglomerative)과 분할적(divisive)의 두 가지 범주로 나뉜다. 종종 "상향식" 접근법이라고 불리는 응집적 군집화는 각 데이터 포인트를 개별 군집으로 시작한다. 각 단계에서 알고리즘은 선택된 거리 측정법(예: 유클리드 거리)과 연결 기준(예: 단일 연결, 완전 연결)에 따라 가장 유사한 두 군집을 병합한다. 이 과정은 모든 데이터 포인트가 단일 군집으로 결합되거나 중지 기준이 충족될 때까지 계속된다. 응집적 방법은 단순성과 소규모에서 중간 규모 데이터 세트에 대한 계산 효율성 덕분에 더 일반적으로 사용된다.
"하향식" 접근법으로 알려진 분할적 군집화는 모든 데이터 포인트를 단일 군집으로 시작하여 재귀적으로 더 작은 군집으로 분할한다. 각 단계에서 알고리즘은 군집을 선택하고 결과 군집 간의 거리를 최대화하는 기준을 사용하여 두 개 이상의 하위 집합으로 나눈다. 분할적 방법은 덜 일반적이지만, 먼저 크고 뚜렷한 군집을 식별하는 것이 목표일 때 유용할 수 있다. 일반적으로 병합과 분할은 탐욕적 방식으로 결정되며, 이는 알고리즘이 전역 구조를 고려하지 않고 각 단계에서 지역적으로 최적의 선택을 한다는 것을 의미한다.
복잡성 및 알고리즘
계층적 응집적 군집화(HAC)의 표준 알고리즘은 시간 복잡도가 O(n^3)이고 Ω(n^2) 메모리를 필요로 하므로 중간 규모의 데이터 세트에도 너무 느리다. 그러나 일부 특수한 경우에는 O(n^2) 복잡도의 최적 효율적 응집적 방법이 알려져 있다. 단일 연결의 경우 SLINK, 완전 연결의 경우 CLINK가 그것이다. 힙을 사용하면 일반적인 경우의 실행 시간을 O(n^3) 대신 O(n^2 log n)으로 줄일 수 있지만, 추가 메모리 요구 사항이 발생한다. 많은 경우 이 접근법의 메모리 오버헤드는 실용적으로 사용하기에는 너무 크다. 쿼드트리를 사용하여 O(n) 공간으로 O(n^2) 총 실행 시간을 보여주는 방법도 존재한다.
완전 탐색을 사용하는 분할적 군집화는 O(2^n)이지만, k-평균과 같은 더 빠른 휴리스틱을 사용하여 분할을 선택하는 것이 일반적이다. 이러한 휴리스틱은 최적성을 계산 가능성과 맞바꾸어 분할적 방법을 더 큰 데이터 세트에 적용할 수 있게 한다.
거리 측정법
연결 기준이 관측값 집합 간의 비유사성을 계산하는 방법을 결정하는 반면, 기본 거리 측정법은 개별 관측값 간의 비유사성을 측정하는 방법을 결정한다. 계층적 군집화는 유효한 거리 측정법을 모두 허용하므로, 측정법 선택은 데이터의 특성에 따라 결정되며 결과 군집화에 상당한 영향을 미칠 수 있다.
유클리드 거리는 연속 수치 데이터에 가장 널리 사용되는 측정법이다. 이는 유클리드 공간에서 두 점 사이의 직선 거리에 해당하며 대부분의 통계 소프트웨어에서 기본 선택이다. 맨해튼 거리(도시 블록 또는 L1 거리라고도 함)는 특성 간 절대 차이의 합이다. 특성이 서로 다른 척도로 측정되거나 데이터에 이상값이 포함된 경우 선호되는 경우가 많으며, 유클리드 거리보다 큰 편차에 덜 민감하다. 코사인 거리는 두 개의 0이 아닌 벡터 간의 각도 비유사성을 측정하며 텍스트 분석 및 기타 고차원 설정에서 일반적으로 사용된다.
연결 기준
연결 기준은 두 군집 간의 거리를 개별 구성원 간의 거리에서 계산하는 방법을 결정한다. 단일 연결(또는 최근접 이웃)은 두 군집의 임의의 두 점 사이의 최소 거리를 사용하며, 길고 사슬 모양의 군집을 생성하는 경향이 있다. 완전 연결(또는 최원거리 이웃)은 최대 거리를 사용하며, 컴팩트하고 구형의 군집을 생성하는 경향이 있다. 평균 연결은 모든 점 쌍 사이의 평균 거리를 사용하여 두 가지 사이의 절충안을 제공한다. Ward의 방법은 총 군집 내 분산을 최소화하여 연속 데이터에 널리 사용된다. 연결 기준의 선택은 결과 덴드로그램의 형태와 해석을 극적으로 바꿀 수 있다.
응용 및 한계
계층적 군집화는 여러 분야에서 사용된다. 생물학에서는 유전적 유사성을 기반으로 계통수를 구축하는 데 사용된다. 마케팅에서는 유사한 행동을 가진 고객을 세그먼트로 나누는 데 도움을 준다. 이미지 분석에서는 픽셀이나 특징을 그룹화할 수 있다. 인공 지능에서 계층적 군집화는 탐색적 데이터 분석을 위한 비지도 학습 기법으로, 그리고 다른 알고리즘의 전처리 단계로 자주 사용된다.
장점에도 불구하고 계층적 군집화에는 한계가 있다. 알고리즘의 탐욕적 특성은 일단 병합 또는 분할이 이루어지면 되돌릴 수 없어 차선의 결과를 초래할 수 있다. 표준 알고리즘의 계산 복잡성은 사용을 중간 규모의 데이터 세트로 제한하지만, 특정 연결 기준에 대한 최적화된 구현이 존재한다. 또한 덴드로그램의 해석은 주관적일 수 있으며, 거리 측정법과 연결 기준의 선택에는 도메인 지식이 필요하다.