병합 클러스터링(Agglomerative Clustering)이란?
병합 클러스터링은 상향식(bottom-up) 군집화 방법입니다. 이 방식에서는 클러스터 안에 하위 클러스터가 있고, 그 하위 클러스터 안에 또 다른 하위 클러스터가 있는 계층 구조를 형성합니다.
알고리즘은 각 객체를 자기만의 클러스터에 배치하는 것에서 출발합니다. 이후 이러한 원자적(atomic) 클러스터들을 점점 더 큰 클러스터로 병합해 나가며, 모든 객체가 하나의 클러스터에 모이거나 미리 정의된 종료 조건이 충족될 때까지 이 과정을 반복합니다. 여러 계층적 군집화 기법이 이 유형에 속하며, 이들 간의 차이는 오직 클러스터 간 유사도를 정의하는 방식에 있습니다.
AGNES 알고리즘의 작동 방식
대표적인 예로 AGNES(Agglomerative Nesting)라는 방법이 있으며, 이는 단일 연결(single-linkage) 기법을 사용합니다. 사각형 영역 안에 여러 객체가 놓여 있다고 가정해 보겠습니다. 초기 상태에서는 모든 객체가 각자 하나의 클러스터에 속합니다. 이후 클러스터 내에서 서로 가장 가까운 객체들 사이의 유클리드 거리가 최소가 되는 클러스터끼리 결합하는 등의 원칙에 따라, 클러스터들이 단계별로 병합됩니다.
K-평균(K-means)과의 차이
K-평균(K-means) 군집화는 처음부터 클러스터 수를 고정해 두고, 모든 데이터를 정확히 그 개수만큼의 클러스터에 할당하는 방식입니다.
반면 병합(agglomeration) 방식을 취하는 또 다른 계열의 접근법은, 모든 데이터 포인트가 각자 독립적인 클러스터를 이루는 상태에서 시작하여, 모든 포인트가 하나의 거대한 클러스터로 모일 때까지 점진적으로 결합해 나갑니다.
1단계: 유사도 행렬(Similarity Matrix) 생성
병합 클러스터링의 첫 번째 절차는 유사도 행렬을 만드는 것입니다. 유사도 행렬은 클러스터 쌍(pair-wise) 사이의 거리 또는 유사도를 기록한 표입니다. 초기 유사도 행렬에는 개별 레코드 쌍 간의 거리가 담깁니다.
유사도 측정 방법
레코드 간 유사도를 재는 데에는 여러 가지 척도가 사용됩니다.
- 유클리드 거리(Euclidean distance): 두 점 사이의 직선 거리
- 벡터 간 각도(angle between vectors): 방향의 유사성을 측정
- 범주형 필드 비율: 연결되는 범주형 필드와 연결되지 않는 범주형 필드의 비율
필요한 계산량
N개의 데이터 포인트에 대해 N개의 초기 클러스터가 존재하므로, 거리 테이블을 완성하려면 N²회의 측정 계산이 필요합니다. 다만 유사도 척도가 참 거리 메트릭(true distance metric)이라면 계산량을 절반으로 줄일 수 있습니다. 참 거리 메트릭은 Distance(X, Y) = Distance(Y, X)라는 대칭성을 만족하기 때문입니다.
2단계: 가장 유사한 클러스터 찾기와 병합
수학적으로 이 행렬은 하삼각 행렬(lower triangular matrix) 형태를 가집니다. 다음 절차는 행렬에서 가장 작은 값을 찾는 것입니다. 이 값은 서로 가장 유사한 두 클러스터를 의미합니다.
이 두 클러스터를 하나의 새로운 클러스터로 병합한 뒤, 부모 클러스터를 나타내던 두 개의 행을 제거하고, 병합된 클러스터와 나머지 클러스터들 사이의 거리를 정의하는 새로운 행으로 교체하여 유사도 행렬을 갱신합니다.
3단계: 병합 반복과 종료
이 시점에는 N − 1개의 클러스터가 남아 있고, 행렬에도 N − 1개의 행이 존재합니다. 병합 단계를 N − 1회 반복하면 결국 모든 데이터가 하나의 커다란 클러스터에 속하게 됩니다.
매 반복마다 어떤 클러스터들이 병합되었는지, 그리고 그 클러스터들 사이의 거리가 얼마였는지가 기록됩니다. 이러한 정보는 최종적으로 어떤 군집화 결과를 선택할지, 즉 적절한 클러스터 개수와 구조를 결정하는 근거로 활용됩니다.