Ward 연결법

Ward 연결법 (Ward Linkage) #

Ward 연결법은 계층적 클러스터링에서 사용되는 연결 기준(linkage criterion) 중 하나로, 클러스터 내 분산의 증가를 최소화하는 방향으로 클러스터를 병합하는 방법이다. 이 방법은 비교적 균등한 크기의 구형 클러스터를 생성하는 경향이 있다.

주요 개념 #

  • 클러스터 내 제곱합 (Within-cluster Sum of Squares, WSS): 각 클러스터 내 데이터 포인트들과 클러스터 중심 간의 거리 제곱합이다.
  • Ward 거리: 두 클러스터를 병합했을 때 증가하는 WSS의 양을 의미한다.
  • 분산 최소화: 병합 시 전체 분산의 증가량을 최소화하는 것을 목표로 한다.

알고리즘 특징 #

  • 각 단계에서 클러스터 내 분산의 증가를 최소화하는 두 클러스터를 병합한다.
  • 덴드로그램(dendrogram)을 생성하여 계층적 구조를 시각화할 수 있다.
  • 비교적 균등한 크기의 클러스터를 형성하는 경향이 있다.
  • 구형에 가까운 클러스터에 가장 적합하다.

계산 방법 #

두 클러스터 A와 B를 병합할 때의 Ward 거리는 다음과 같이 계산된다:

$$\Delta(A,B) = \frac{|A| \cdot |B|}{|A| + |B|} \|\mu_A - \mu_B\|^2$$

여기서:

  • |A|, |B|는 각각 클러스터 A, B의 크기
  • μA, μB는 각각 클러스터 A, B의 중심

장점과 단점 #

  • 장점

    • 구형 클러스터에 매우 효과적이다.
    • 비교적 균등한 크기의 클러스터를 생성한다.
    • 이론적 기반이 탄탄하다.
    • 덴드로그램을 통한 시각적 해석이 용이하다.

  • 단점

    • 구형이 아닌 클러스터에는 적합하지 않다.
    • 계산 복잡도가 높아 대용량 데이터에 부적합하다.
    • 이상치에 민감할 수 있다.

Ward 연결법은 계층적 클러스터링에서 가장 널리 사용되는 방법 중 하나로, 특히 균등한 크기의 구형 클러스터를 찾고자 할 때 매우 효과적이다.

  • Languages