[ML4AM] 3.Codependence (6) Distance between Two Partitions

이전 섹션에서는 랜덤 변수 간의 유사성을 평가하는 방법을 다루었으며, 이 개념을 동일한 데이터 집합의 두 분할을 비교하는 문제로 확장할 수 있다. 이를 통해 두 분할이 얼마나 유사한지 또는 다른지를 평가할 수 있다.

ex)

포트폴리오의 자산들을 리스크 특성에 따라 여러 그룹으로 나눌 때, 두 개의 서로 다른 리스크 클러스터링 방법을 비교하는 데 사용된다. 예를 들어, 특정 알고리즘을 사용하여 자산을 클러스터링하고, 다른 알고리즘의 결과와 비교하여 어느 방법이 더 일관된 클러스터를 만드는지 평가할 수 있다.

Partition \(P\) 
데이터 셋 \(D\)의 분할 \(P\)는 상호 배타적이고 비어 있지 않은 부분 집합들의 정렬되지 않은 집합이다
  \[
  P = \{D_k\}_{k=1, ..., K}
  \]
 여기서 각 부분 집합 \(D_k\)는 공집합이 아니며, 서로 겹치지 않으며, \(D\)의 모든 요소를 포함한다

Partition \(P\)  에 대한 Entropy \(H[P]\)

• 확률 정의
  임의의 데이터 요소 \(d \in D\)를 선택할 확률 \( \tilde{p}[d] = \frac{1}{|D|} \)
  : 이는 데이터 집합 D의 모든 요소가 동일한 확률로 선택될 수 있음을 나타냄
  
  
•  \(D\)에서 임의로 선택된 요소 \(d\)가 \(D_k\)에 속할 확률 \( p[k] = \frac{|D_k|}{|D|} \).
  : 여기서 \( |D_k| \)는 부분 집합 \( D_k \)의 크기이다. 이 확률 \( p[k] \)는 불연속 랜덤 변수와 연관이 있으며, 이 랜덤 변수는 집합 \( S = \{1, \ldots, K\} \)에서 값을 가진다. 즉, 요소 \( d \)가 각 부분 집합 \( D_k \)에 속할 확률을 나타낸다
  
  
• 엔트로피 \( H[P] \)
   \[
     H[P] = - \sum_{k=1}^{K} p[k] \log p[k]
     \]

두번째 Partition \(P'\) 

• 결합 확률 정의
  두 번째 랜덤 변수  \(D\)의 임의의 요소 \(d\)가 \(D_k\)에 속하고 \(D'_{k'}\)에도 속할 확률 \(p[k, k'] = \frac{|D_k \cap D'_{k'}|}{|D|} \).
• 결합 엔트로피 
     \[
     H[P, P'] = - \sum_{k=1}^{K} \sum_{k'=1}^{K'} p[k, k'] \log p[k, k']
     \]
• 조건부 엔트로피 \(H[P|P']\)
  \[
    H[P|P'] = H[P, P'] - H[P']
    \]
• Mutual Information \(I[P, P']\)
    \[
    I[P, P'] = H[P] - H[P|P'] = \sum_{k=1}^{K} \sum_{k'=1}^{K'} p[k, k'] \log \left( \frac{p[k, k']}{p[k] p[k']} \right)
    \]
• Variation of information \(VI[P, P']\)
    \[
    VI[P, P'] = H[P|P'] + H[P'|P]
    \]
  • 여기서 \(H[P|P']\)는 \(P\)에 대한 정보를 잃는 정도를 측정하고, \(H[P'|P]\)는 \(P'\)로부터 얻는 정보를 측정한다
  • VI는 metric이며, 절대 상한선, 부분 집합의 수가 일정할 때 \(VI \leq \log|D|\) 이하이다

 

 

Marina Meilă, Comparing clusterings—an information based distance, Journal of Multivariate Analysis,
Volume 98, Issue 5,2007