계층적 클러스터링(hierarchical clustering)은 데이터 객체들을 클러스터 트리 형태로 점진적으로 병합해 나가는 방식으로 작동합니다. 계층적 클러스터링 알고리즘은 상향식(bottom-up) 방식과 하향식(top-down) 방식으로 나뉩니다. 다만 정확한 계층적 클러스터링 기법은 병합 또는 분할 결정이 한번 내려지면 이를 조정할 수 없다는 점에서 한계를 가집니다.
계층적 클러스터링의 주요 요소
1. 전역 목적 함수의 부재
병합형(agglomerative) 계층적 클러스터링 기법은 각 단계에서 어떤 클러스터를 병합(분할형 기법의 경우 분할)해야 할지 지역적으로 판단하기 위해 여러 가지 요소를 활용합니다.
이러한 접근 방식은 복잡한 조합 최적화 문제를 직접 풀어야 하는 부담을 피할 수 있는 클러스터링 알고리즘을 만들어냅니다.
2. 다양한 클러스터 크기 처리 능력
병합형 계층적 클러스터링에서 중요한 요소 중 하나는 병합되는 클러스터들의 상대적 크기를 어떻게 고려할 것인가입니다. 이는 무게중심(centroid), Ward 방법, 그룹 평균(group average)처럼 합을 포함하는 클러스터 근접성 방식에만 적용됩니다.
여기에는 두 가지 방식이 있습니다. 하나는 모든 클러스터를 동등하게 취급하는 가중(weighted) 방식이고, 다른 하나는 각 클러스터에 속한 데이터 포인트 수를 고려하는 비가중(unweighted) 방식입니다. 여기서 '가중' 또는 '비가중'이라는 용어는 클러스터가 아니라 데이터 포인트를 기준으로 한다는 점에 유의해야 합니다. 즉, 크기가 다른 클러스터를 동등하게 취급하면 서로 다른 클러스터의 포인트에 서로 다른 가중치가 부여되고, 반대로 클러스터 크기를 고려하면 서로 다른 클러스터의 포인트에 동일한 가중치가 부여됩니다.
3. 병합 결정의 최종성
병합형 계층적 클러스터링 알고리즘은 모든 포인트 쌍의 유사도 정보를 활용할 수 있기 때문에 두 클러스터의 병합에 대해 좋은 지역적(local) 결정을 내리는 경향이 있습니다. 그러나 일단 두 클러스터를 병합하기로 결정하면 이후에 이를 되돌릴 수 없으며, 이로 인해 지역 최적화 요소가 전역 최적화 기준이 되지 못하는 문제가 발생합니다.
예를 들어, Ward 방법에서는 K-평균(K-means)의 '제곱 오차 최소화' 기준을 사용해 어떤 클러스터를 병합할지 결정하지만, 각 단계의 클러스터들이 전체 SSE(제곱 오차 합) 관점에서 국소 최솟값을 나타내지는 않습니다. 실제로 클러스터는 고정된 것이 아니라, 한 클러스터에 속한 포인트가 자신이 속한 클러스터의 무게중심보다 다른 클러스터의 무게중심에 더 가까울 수도 있습니다.
병합 결정 한계를 극복하는 방법
병합이 최종적이라는 한계를 극복하려는 몇 가지 방법이 존재합니다. 하나는 트리의 가지들을 재배열하여 전역 목적 함수를 개선하는 방식으로 계층적 클러스터링을 보완하는 것이며, 다른 하나는 K-평균과 같은 분할(partitional) 클러스터링 기법으로 작은 클러스터들을 먼저 생성한 뒤, 이 작은 클러스터들을 시작점으로 삼아 계층적 클러스터링을 수행하는 것입니다.