[Hierarchical Clustering] DIANA (Divisive Analysis)

DIANA (DIvisive ANAlysis)

Top-down 방식의 hierarchical clustering method이다.

Splus 같이 statistical analysis packages에 구현되어있다.

 

개념적으로는 AGNES(bottom-up)과 반대이지만 순서적으로 완전히 역순은 아니다.

각 object를 하나의 cluster로 만들기 위해 과정을 반복해나간다.

 

Divisive vs. Agglometrative

n개의 object가 속해있는 전체 cluster를 두 개의 cluster로 나눌 때 complexity는

• agglomerative
  • $_n C _2 = \frac{n(n-1)}{2}$
  • 가능한 모든 조합에 대해 distance를 계산
• divisive
  • $2^{n-1} - 1$
  • (각 요소를 2개 중 하나에 배정하는 경우 - 하나로만 뭉치는 경우) / (2개 구분 제거)
  • cost가 agglomerative 보다 상대적으로 높다.
  • cost가 매우 크기 때문에 모든 경우를 다 볼 수 없다.

 

---

구현

Naive Method

1. n개의 objects를 하나의 cluster에 속해있다고 간주한다.
2. Cluster를 두 개의 작은 cluster로 나눈다.
3. 모든 cluster가 single object로만 구성될 때 까지 반복해 나간다.
   • n-1 번 수행하면 single object가 된다.

 

Reduce Cost

모든 경우를 다 볼 수 없기 때문에 아래와 같은 과정으로 수행한다.

1. Splinter seed 선택 → $O(n(n-1))$
   1. 다른 object들과의 평균 dissimilarity가 가장 높은 object를 찾는다. 
   2. 선택된 object를 새로운 cluster(splinter group)으로 만든다.
2. Reassign
   1. splinter group 밖의 나머지 object($i$)들을 돌면서 $D_i$를 계산한다.
      • $D_i = [averaged\_d(i, j) (j \notin R_{splinter \; group})] - averaged \_ d(i, j) (j \in R_{splinter \; group})$
      • splinter group에 속하지 않는 object들과의 평균 거리 - splinter group에 속하는 object들과의 평균 거리
   2. $D_h$가 가장 큰 object h를 찾고, $D_h > 0$이면 splinter group으로 배치한다.
   3. 모든 object의 $D_h$가 음수가 될 때 까지 reassign 과정을 반복한다.
3. Pick next
   • diameter가 큰 cluster를 선택하고 reassign 과정을 반복한다.
   • diameter : cluster 내의 모든 object pair 간 dissimilarity의 최댓값
4. 모든 cluster가 하나의 object로만 구성될 때 까지 위 과정을 반복한다.