집약적 계층적 군집화의 개념
집약적 계층적 군집화(Agglomerative Hierarchical Clustering)는 하향식(bottom-up) 방식의 군집화 기법으로, 각 군집(cluster)은 다시 하위 군집(sub-cluster)을 포함하고, 그 하위 군집 역시 또 다른 하위 군집을 가지는 계층 구조를 형성합니다. 이 기법은 모든 객체를 각각 하나의 독립된 군집에 배치하는 것에서 시작하여, 원자적 군집들을 점차 더 큰 상위 군집으로 병합해 나갑니다. 이 과정은 모든 객체가 하나의 군집에 속하게 되거나, 미리 정의된 종료 조건이 충족될 때까지 반복됩니다.
계층적 군집화에는 여러 가지 접근 방식이 존재하지만, 이들은 오직 군집 간 유사도(inter-cluster similarity)를 정의하는 방식에서만 차이를 보입니다.
AGNES(Agglomerative Nesting)의 동작 방식
대표적인 집약적 군집화 방법인 AGNES는 단일 연결(single-linkage) 기법을 활용하며 다음과 같이 동작합니다. 사각형 영역 안에 여러 객체들이 배치되어 있다고 가정해 봅시다. 초기에는 각 객체가 자신만의 군집에 속합니다. 이후 두 군집 내에서 서로 가장 가까운 객체들 사이의 유클리드 거리(Euclidean distance)가 최소가 되는 군집 쌍을 찾아 단계적으로 병합해 나갑니다.
덴드로그램(Dendrogram)을 통한 시각화
계층적 군집화의 결과는 덴드로그램(dendrogram)이라 불리는 나무 형태의 다이어그램으로 시각화할 수 있습니다. 덴드로그램은 군집과 하위 군집 간의 관계뿐만 아니라, 군집들이 병합된 순서(병합 관점, agglomerative view) 또는 분할된 순서(분할 관점, divisive view)까지 한눈에 보여줍니다.
기본 집약적 계층적 군집화 알고리즘
- 필요한 경우 근접 행렬(proximity matrix)을 계산합니다.
- 반복(repeat):
- 가장 가까운 두 군집을 병합합니다.
- 새로 생성된 군집과 기존 군집들 간의 근접도를 반영하도록 근접 행렬을 갱신합니다.
- 하나의 군집만 남을 때까지 위 과정을 반복합니다.
군집 근접도의 정의: MIN, MAX, Group Average
군집 간 근접도는 일반적으로 특정 유형의 군집 관점에 따라 정의됩니다. 예를 들어, MIN, MAX, Group Average 등 여러 집약적 계층적 군집화 기법은 그래프 기반의 군집 관점에서 파생된 것입니다.
- MIN(단일 연결법): 서로 다른 군집에 속한 두 점 중 가장 가까운 두 점 사이의 근접도를 군집 간 근접도로 정의합니다. 그래프 용어로 표현하면, 서로 다른 노드 부분집합에 속한 두 노드를 연결하는 가장 짧은 간선(shortest edge)에 해당합니다.
- MAX(완전 연결법): 서로 다른 군집에 속한 두 점 중 가장 먼 두 점 사이의 근접도를 군집 간 근접도로 정의합니다. 그래프 용어로는 서로 다른 노드 부분집합에 속한 두 노드를 연결하는 가장 긴 간선(longest edge)입니다.
시간 및 공간 복잡도 분석
앞서 소개한 집약적 계층적 군집화 알고리즘은 근접 행렬을 필요로 합니다. 근접 행렬이 대칭(symmetric)이라고 가정하면, m개의 데이터 포인트에 대해 ½m² 개의 근접도 값을 저장해야 합니다. 또한 군집 정보를 추적하기 위해 필요한 공간은 군집 수에 비례하며, 단일 객체 군집(singleton cluster)을 제외하면 m-1개입니다. 따라서 전체 공간 복잡도는 O(m²)입니다.
계산 복잡도 관점에서도 기본 알고리즘의 분석은 비교적 간단합니다. 근접 행렬을 계산하는 데 O(m²)의 시간이 소요됩니다. 초기에 m개의 군집이 존재하고 매 반복마다 두 개의 군집이 하나로 병합되므로, 이후에는 m-1번의 반복이 발생합니다.