[Hierarchical Clustering] CHAMELEON

CHAMELEON

Dynamic modeling을 이용한 bottom-up 방식의 hierarchical clustering method이다.

두 cluster 간 interconnectivity와 closeness가 상대적으로 크면 두 cluster를 merge한다.

 

이를 통해 주변 상황에 맞게(dynamic하게) merge 할 수 있다.

단, 몇 개의 cluster로 나눌 것인지 미리 정해주어야 한다.

 

CHAMELEON은 성능은 괜찮지만 scalability가 좋지 않다.

 

• Relative Interconnectivity
  • edge의 수를 기준으로 판단
  • 두 그룹 간 edge cut의 수 / 두 개 각각의 edge cut 수의 평균
  • $RI(C_i, C_j) = \frac{|EC_{\{  C_i, C_j \}}|}{(|EC_{C_i}| + |EC_{C_j}|)/2}$
• Relative Closeness
  • edge의 weight으로 판단
  • edge에는 similarity가 존재 → similairty를 weight으로 삼아서 판단
  • $RC(C_i, C_j) = \frac{\bar{S}_{EC_{\{C_i, C_j\}}} } {(|C_i| \bar{S}_{EC_{C_i}} + |C_j| \bar{S}_{EC_{C_j}} )/(|C_i| + |C_j|)}$

 

방법

1. K-nearnest neightbor graph를 그린다.
   • node : 각 object
   • edge : 각 node와 가장 가까운 k개 node와의 link
2. 2 단계의 알고리즘을 거친다.
   1. Graph partitioning algorithm
      • 만들어진 그래프를 잘게 쪼개서 확실히 같은 cluster에 속하는 node끼리만 연결되도록 한다.
      • 쪼개는 방법 : minimize the edge cut(METIS)
        • 쪼개지는 크기가 비슷해야 한다.
        • edge cut(잘리는 edge)의 weight을 최소화 하는 방향으로 쪼갠다.
      • 분류할 object의 수를 줄일 수 있다.
   2. Agglomerative(bottom-up) hierarchical clustering algorithm
      • sub-cluster를 합쳐나가면서 cluster를 만든다.
      • relative interconnectivity와 relative closeness가 상대적으로 큰 cluster를 합침