[ML] 계층적 클러스터링(hierarchical clustering)

---

병합적 클러스터링 (Agglomerative)

 

상향식(bottom-up) 접근으로 클러스터링을 수행한다. 즉 각 샘플을 하나의 클러스터로 보고 가장 유사도가 높은 두 군집을 반복적으로 병합해나간다. 유사도는 일반적으로 거리를 기준으로 한다.

거리를 기준으로 하기 때문에 가장 먼저 모든 샘플 간 거리 행렬(distance matrix)을 계산하고, 각 샘플을 크기 $ 1 $ 의 클러스터로 생각한다. 거리(distance)가 가장 작은 두 클러스터를 합쳐 새 클러스터를 생성하고, 다시 거리 행렬을 업데이트한다. 모든 클러스터가 하나의 클러스터가 될 때 까지 이를 반복한다.

병합 과정을 링키지 행렬(linkage matrix)에 기록할 수 있는데 크기는 $ (n-1) \times 4 $ 이다. 각 행은 병한된 두 클러스터의 인덱스와 두 클러스터 간의 거리, 새로 생긴 클러스터 안에 포함된 원보 데이터 포인트의 총 개수를 포함한다.

군집 개수를 사전에 정하는 것이 아니라 군집화된 결과를 보고 적절히 선택할 수 있고, 다양한 연결 기준을 통해 데이터 특성에 맞게 활용할 수 있다는 장점이 있다.

그러나 데이터셋 크기가 커지면 $ O(n^2) $ 이사의 거리 계산이 필요해 계산 비용, 메모리 부담이 크며, 한번 병합 후 되돌릴 수 없기 때문에 초기 단계의 잘못된 결정이 이후 구조에 영향을 미친다.

 

---

분할적 클러스터링 (Divisive)

 

하향식(top-down) 분할이다. 모든 샘플을 하나의 군집으로 보고 가장 이질적인 군집을 반복적으로 분할해 나간다. 병합적 방법에 비해 드물게 쓰이고, 계산 비용이 더 크다는 단점이 있다.

 

---

덴드로그램 (Dendrogram)

 

계층 구조를 트리 형태로 시각화한 그래프로 계층적 클러스터링을 한 후 시각화하는 방법으로 가장 많이 쓰인다.

트리 높이는 군집 간 거리를 나타내며 원하는 군집 개수 K에 대응하는 높이에서 수평선을 그어 잘라주면 그 아래에 있는 서브트리가 최종 군집이 된다.