Cluster 평가지표

최근 회사업무에서 클러스터링을 조금씩 활용해보고 있는데, 그 과정에서 학습하게 된 클러스터의 평가지표 내용을 정리한다.

 

Previous Knowledge

01. 필요성

클러스터링은 비지도 학습의 한 종류로, 별도의 가이드 없이 데이터의 특성만으로 데이터를 군집화(labeling 한다고도 볼 수 있겠네요)하는 방법론이다. 데 이터 특징을 잘 종합하여 클러스터링 하였다면, 각 클러스터에 붙여지는 이름을 label로 활용할 수도 있다.
다만 클러스터링을 수행하는 방법이 다양하고, 같은 방법론 안에서도 설정값에 따라 클러스터 성능은 다변한다. 따라서 주어진 데이터 세트에 대해 여러 번의 클러스터링을 시도할 여지가 존재하고, 각각의 시도에 대한 점수(scoring) 필요성이 생긴다.

 

02. 평가항목

클러스터를 평가하는 방법에는 적정 클러스터 갯수, 클러스터 결과에 대한 품질평가라는 2가지 접근이 존재한다. Distance Metric

클러스터링의 평가는 1. 비슷한 데이터끼리 하나의 클러스터로 분류되었는지, 2. 클러스터끼리는 잘 구분되었는지를 측정하는 방식으로 이루어진다.

따라서 Intra-Class Distance, Inter-Class Distance를 측정하는 것이 중요하다. 측정시에는 별도의 언급이 없다면 euclidean distance를 사용한다.

 

Intra-Class Distance

한 군집 내에서 데이터 간의 거리를 측정하는 방식에는 몇가지가 존재한다. 보통은 한 군집 내에서의 "변동성"에 대한 측도를 측정하고자 한다.

• Complete Diameter Distance: cluster 내 모든 데이터 조합에 대한 distance를 측정한다. 이상치에 약하고 computation cost가 크다.
• Average Diameter Distance: cluster 내 모든 데이터 조합에 대한 distance의 평균을 계산한다. 역시 이상치에 취약하고 computation cost가 크다
• Centroid Diameter Distance: cluster 내의 중심점(평균)인 centroid를 설정하고, 모든 데이터 포인트와 centroid 사이의 거리합을 평균한다. 연산량이 작다.

(bold로 표기한 측도는 연산효율적)

 

Inter-Class Distance

두 개의 클러스터가 얼마나 잘 구분되었는지를 어떻게 측정할까?

• Single Linkage Distance
  • 서로 다른 두 클러스터 간, 양 집합에 속하는 모든 데이터 사이의 거리 중 최솟값, d(C1, C2) = min d(a, b), where a is in C1, b is in C2
• Complete Linkage Distance
  • 서로 다른 두 클러스터 간, 양 집합에 속하는 모든 데이터 사이의 거리 중 최댓값, d(C1, C2) = max d(a, b), where a is in C1, b is in C2

• Average Linkage Distance: 두 클러스터 간, 모든 데이터 사이의 거리를 계산하고 평균한다.
• Centroid Linkage Distance: 두 클러스터의 centroid를 설정하고 그 사이의 거리만을 측정한다.
• Average of Centroid Linkage Distance: 1개 클러스터의 centroid를 설정하고, 나머지 대상 클러스터의 모든 데이터 포인트에 대한 거리 평균을 구한다.

(bold로 표기한 측도는 연산효율적)

---

 

Clustering Method

좋은 클러스터링 방법은 클러스터 내부의 데이터끼리는 가깝고, 클러스터끼리는 멀게 형성하도록 동작하고 모든 클러스터링 평가방법은 이에 기반한 다. 아래 해석은 이해하기 쉽도록 Centroid 기반으로 작성하였음.

 

01. Dunn Index

$$ DI_K= \frac{ \underset{1\leq i \leq j \leq K}{\min}  \delta (C_i, C_j)}{\underset{1\leq k\leq K}{\max}\Delta_k} $$

 

• denominator term(분모 항): pivot cluster의 centroid로부터 cluster 내의 모든 데이터 포인트와의 평균 거리값을 구한다. 이러한 과정을 k번 반복하여 k개의 centroid diameter distance 중 최댓값을 분모로 한다.
• numerator term: 모든 클러스터에 대해 centroid를 구한 후, 각 클러스터 간 거리를 k(k-1)/2 번 구한다. (centroid linkage distance) 이렇게 구한 값 중에서 최솟값을 분자로 한다.

클러스터의 개수 K를 지정하고 위 수식에 따라 동작한다. 분자가 크고, 분모가 작을수록 좋은 클러스터 체계로 판단한다.

 

02. Silhouette Score

$$ SC = \max_{1\leq J \leq K} \tilde{s}(J) $$

 

silhouette scoure는 dunn index와 마찬가지로 클러스터 간 거리가 멀고, 클러스터 내 거리가 가까우면 좋은 클러스터링이라고 평가한다. 다만, 인접한 군 만을 유사도 계산에 활용한다.
$tilde{s} (J)$ 는 J번째 클러스터의 silhouette score의 평균값이다. 따라서 silhouette score의 평균값 중 가장 큰 값을 silhouette score로 보고, 이 값 이 1에 가까울수록 좋은 클러스터링이라고 판단한다.

 

그런데 silhouette score가 무엇이길래 이 값이 크다면 좋은 클러스터링이라고 판단할까?

• silhouette score
  • 먼저 pivot cluster $ C_{I} $를 선정한 후, 이 클러스터에 속한 데이터 포인트 {i}에 대해 score a, b를 계산한다.
    • Intra-Class Distance: 
      • $ a(i) = \frac{1}{|C_{I}|-1}\sum_{j\in C_{I}, j\neq i} d(i, j) $
      • 클러스터 내부에 존재하는 자기자신을 제외한 데이터와의 거리합을 구한 뒤, (속한 클러스터 내 데이터 포인 트 개수 - 1) 로 나눈 값
    • Inter-Class Distance:
      • $ b(i) = \min_{J\neq I}\frac{1}{|C_J|}\sum_{j\in C_J}d(i, j) $
      •  모든 클러스터를 순회하며, 각 클러스터에 존재하는 데이터들 사이의 거리합을 target 클러스터의 데이터 포 인트 개수로 나눈 값들을 구한 후, "최솟값"을 구함
      • "최솟값"을 구하므로, 자연스럽게 최근접 클러스터와의 거리만 고려하게 된다.
  • 이제 a, b term을 기반으로 silhouette score를 계산할 수 있다.
    • $ s(i) $
      • $ s(i) = \begin{cases} \frac{b(i)-a(i)}{\max \{ a(i), b(i)\}}, & \text{ if } |C_I| > 1 \\ 0, & \text { if } |C_I|=1\end{cases} $
      • $ s(i) = \begin{cases} 1-a(i)/b(i), & \text{ if } a(i) < b(i) \\ 0, & \text{ if } a(i) = b(i) \\ b(i)/a(i) -1, &\text{ if } a(i)>b(i) \end{cases}\tag{2} $
    • 2번째 수식에 따라 silhouette score는 항상 -1에서 1사이 값임을 알 수 있다.
    • 좋은 클러스터링일수록 Intra-Class Distance인 a(i)는 작고 Inter-Class Distance b(i)는 커서 1에 가까워지는 경향이 된다는 것을 알 수 있다.

따라서 좋은 클러스터링이라면, Silhouette Score가 1에 가까운 큰값으로 도출된다. 다만, 모든 데이터 포인트에 대해서 계산해야하므로 연산량이 매우 많다.

 

 

03. Calinski-Harabasz Index

$$ CH = \left[ \frac{\sum_{k=1}^Kn_k \|c_k - c\|_2^2 }{K-1} \right]  / \left[ \frac{\sum_{k=1}^K\sum_{i=1}^{n_k} \| x_i^k-c_k \|_2^2}{n-K} \right ] $$

 

calinski-harabasz index는 "variation" 개념을 도입하여 직관적으로 클러스터링을 평가한다. 예컨대, 클러스터 간 변동은 크고, 클러스터 내 변동은 작으면 좋은 클러스터라고 평가한다.

이 방법론은 몇가지 notation을 정의하고 전개된다. 

• $ n$ : 전체 데이터 개수 
• $ c_{k} $: k번째 클러스터의 centroid 
• $ n_{k} $: k번째 클러스터의 데이터 포인트 개수 
• $ c $: 전체 데이터들의 중심점 (global centroid)

따라서 수식은 다음과 같이 해석될 수 있다.

• numerator term(분자항)
  • 모든 클러스터에 대해서(k=1,...,K) 각 클러스터의 centroid와 global centroid 거리를 구하고, 해당 클러스터의 데이터 개수만큼 가중치 를 준다. 그리고 sum한다.
  • 클러스터 centroid를 대상으로 하는 분산합에 가깝다. 따라서 해당 값이 클수록 각 클러스터끼리 잘 구분된다(흩어졌다)고 볼 수 있다.
• denominator term(분모항)
  • 각 클러스터의 데이터 포인트마다($ i=1,...n_{k} $) 해당 클러스터의 centroid와의 거리를 구하고 sum한다.
  • 이것을 모든 클러스터에 대해서($ k=1,...,K $) 진행한다.
  • 클러스터별 분산값을 구하고 합산한다음 $ (n - k) $, 전체 데이터개수와 클러스터 개수의 차이를 구한다음 나눈다.
  • 클러스터별 분산합에 가까운 개념이므로, 클러스터 내에서 분산이 작다면 선택한 클러스터링 기법이 같은 군집 내에서 데이터를 잘 모았다고 볼 수 있다.

분류할 K의 개수를 1에서부터 늘려가면서 반복적으로 CH값을 측정하여, 최적의 클러스터 개수를 평가할 수 있다.

 

04. Davies-Bouldin Index

$$ DB = \frac{1}{K}\sum_{k=1}^KD_k $$

 

DB Score는 모든 클러스터에 대해 군집화가 잘 "이루어지지 않는 정도"를 보는 측도이다. 따라서 "잘 안된 정도"인 DB Score는 작을수록 좋은 클러스터링이다.

$ D_{k} $ 값은 k번째 클러스터가 "클러스터링이 잘 안되었는지"를 측정한 점수이고, 따라서 이 값이 작을수록 좋은 클러스터링이다. k번째 클러스터가 얼마나 클러스터링이 잘 안되었는지를 측정하는 측도는 아래와 같다.

 

$$ D_k = \max_{l \neq k}R_{k, l} $$ 

 

k번째 클러스터가 얼마나 군집화가 안되었는지는 어떻게 측정할까? Davies-Bouldin Index에서는 k번째 클러스터에서 자기 자신을 제외한 다른 클러스터를 바라보았을 때, 얼마나 Relation이 존재하는지를 측정하는 $ R_{k, l} $ 을 모든 클러스터에 대해 측정하고, 그 값 중 최댓값, 즉 worst case를 k번째 클러스터가 얼마나 군집화가 실패했는지를 보는 기준으로 선택한다.

 

$$ R_{k, l} = \frac{S_k+S_l}{M_{k, l}} $$

$$ \begin{align}S_k &= \left( \frac{1}{n_k}\sum_{i=1}^{n_k}\| x_i^k-c_k \|_p^q \right)^{1/q} \\ M_{k, l} &= \|c_k - c_l\|_p = \left ( \sum_{j=1}^m|c_{k, j} - c_{l, j}|^p \right )^{1/p} \end{align} $$

 

군집화가 실패한 정도는 클러스터 내부의 분산정도에 해당하는 $ S_{k} $ 와 두 클러스터의 centroid 거리를 구하는 $ M_{k,l} $ 의 조합으로 구한다.

따라서, 두 클러스터가 구분이 잘되어 거리가 멀면 M값이 커지고, 클러스터 내부의 데이터 포인트끼리 잘 군집될수록 S값이 작아져 R값이 작아지게 된다. 따라서 클러스터 군집실패 점수가 낮아져 좋은 클러스터 점수라고 판단할 수 있게 된다.