[Cluster Analysis] Distance between Clusters

Distance between Clusters

Hierarchical clustering 할 때 cluster의 거리으로 어떤 것을 선택하는지에 따라 결과가 달라진다.

• single link
  • $dis(K_i, K_j) = min(t_{ip}, t_{jq})$ 
  • cluster 간 object pair의 거리 중 가장 가까운 것을 cluster의 거리로 취급한다.
• complete link
  • $dis(K_i, K_j) = max(t_{ip}, t_{jq})$ 
  • cluster 간 object pair의 거리 중 가장 먼 것을 cluster의 거리로 취급한다.
• average
  
  • $dis(K_i, K_j) = avg(t_{ip}, t_{jq})$
  • cluster 간 모든 object pair의 거리의 평균을 cluster의 거리로 취급한다.
• centorid
  • $dis(K_i, K_j) = dis(C_i, C_j)$ 
  • cluster의 centroid의 거리를 cluster의 거리로 취급한다.
  • 위의 방법들은 $O(n^2)$이지만 centroid를 이용하면 $O(N_1 + N_2)$라서 cost가 작다.
• mediod
  • $dis(K_i, K_j) = dis(M_i, M_j)$
  • cluster 간 mediod의 거리를 cluster의 거리로 취급한다.
  • real object를 대표값으로 설정한다.
  • outlier의 영향이 작다.

 

---

Centroid, Radius, Diameter

Numerical dataset에 대해 적용하는 기준이다.

 

• centroid (무게 중심)
  • $C_m = \frac{\sum^N_{i=1}(t_{ip})}{N}$ 
  • cluter의 중심이다.
  • 각 dimension에서의 평균값이다.
• radius (반경)
  • $R_m = \sqrt{\frac{\sum^N_{i=1}(t_{ip} - c_m)^2}{N}}$
  • 각 지점에서 centroid까지 차이의 제곱의 평균에 root를 씌운 것이다.
  • 표준편차와 유사하다. (표준편차 = $E(X^2) - (E(X))^2$)
• diameter (지름)
  • $D_m = \sqrt{\frac{\sum^N_{i=1}\sum^N_{i=1}(t_{ip} - t_{iq})^2}{N(N-1)}}$ 
  • 가능한 모든 object pair의 거리의 평균이다.
  • 위 수식에서는 자기 자신을 포함하지 않아 $N(N-1)$로 나눴지만 자기 자신까지 포함하면 $N^2$로 나눠도 된다.
  • 수학적으로는 radius의 2배이지만 여기서는 다르다.