[ML] Calinski-Harabasz Index (칼린스키-하라바츠 인덱스)

 Calinski-Harabasz Index는 Variance Ration Criterion (VRC) 라고도 알려져 있으며 직역하자면 분산 비율 기준이다, 데이터에서 최적의 클러스터 수를 결정하기 위한 평가 지표로. 1974년 칼린스키와 하라바츠가 제안했다. 평가 지표는 Internal Validation 기법과 External Validation 기법이 있는데 데이터에 label이 없을 시 Internal Validaiton 기법을 사용할 수 있으며 여기에는 Calinski-Harabasz Index 외에 Silhoutte Score, Davies-Bouldin Index 등이 있다.

 

 이 지표는 클러스터 간 분산 합계와 클러스터 내 분산 합계의 비율을 기반으로 한다. 직관적으로, 이 비율은 클러스터 내 비율에 대한 클러스터 간 분산을 측정한다. Calinski-Harabasz Index가 클수록 클러스터링이 잘 됐다는 것을 가르키는데, 이는 각 클러스터가 밀도가 높으면서 서로 잘 분리돼 있다는 것을 의미하기 때문이다.

 

 Calinski-Harabasz Index의 강점은 빠른 속도인데 데이터의 개수가 n 일 때 일반적인 시간 복잡도는 O(n)이다. 수식은 아래와 같다.

 

VRC(k) = [(Bk / (k - 1)) / (Wk / (N - k))]

Bk: 클러스터 간 분산 행렬
Wk: 클러스터 내 분산 행렬
k: 클러스터 개수
N: 데이터 개수

 

 예시를 통해 계산하는 법을 알아보자.

 

Cluster 1: 2, 4, 6 (평균 = 4)
Cluster 2: 10, 12, 14 (평균 = 12)
전체 평균 = (2+4+6+10+12+14)/6 = 8

Bk = 3*(4 - 8)^2 + 3*(12 - 8)^2
     = 3*(16) + 3*(16)
     = 96
Wk = (2-4)^2 + (4-4)^2 + (6-4)^2 + (10-12)^2 + (12-12)^2 + (14-12)^2
      = 4 + 0 + 4 + 4 + 0 + 4
      = 16
VRC(k) = [(Bk / (k - 1)) / (Wk / (N - k))]
             = [(96 / (2 - 1)) / (16 / (6 - 2))]
             = [96 / 1] / [16 / 4]
             = 96 / 4
             = 24

위 데이터에 대한 Calinski-Harabasz index는 24 다.

 

 

참고

- https://towardsdatascience.com/7-evaluation-metrics-for-clustering-algorithms-bdc537ff54d2

- https://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation

- https://scikit-learn.org/stable/modules/clustering.html#calinski-harabasz-index