Unifying Information-Theoretic and Pair-Counting Clustering Similarity

기술적 요약: 정보 이론적 방식과 쌍 계수(Pair-Counting) 클러스터링 유사성의 통합

문제 정의
클러스터링을 비교하는 것은 비지도 학습 모델을 평가하는 데 있어 근본적인 작업이지만, 실무자들은 서로 다른 유사도 지수 사이에서 빈번하게 발생하는 불일치 문제에 직면하곤 한다. 현재 이 분야는 두 가지 지배적인 계열로 나뉘어 있다. 하나는 순서가 없는 요소들의 쌍(unordered pairs)에 대한 일치도를 평가하는 쌍 계수 척도(예: Rand Index, Adjusted Rand Index, Jaccard)이며, 다른 하나는 클러스터 공생(co-occurrence)의 전체 분할표(contingency table)를 통해 의존성을 집계하는 정보 이론적 척도(예: Mutual Information, Variation of Information)이다. 이 두 계열은 동일한 파티션 쌍에 대해서도 서로 다른 결론을 내리는 경우가 많아 해석을 모호하게 만든다. 기존 연구들이 축적된 공리적 차이나 기하학적 국소 등가성을 식별해 왔음에도 불구하고, 이러한 척도들이 왜 서로 다른지—구체적으로 그들의 가중치 부여 원칙과 샘플링 공간과 관련하여—를 설명하는 통합적인 분석 프레임워크는 부족한 실정이었다.

방법론
본 논문은 공유된 **독립성 베이스라인(independence baseline)**과 기초 수학 구조의 확장을 통해 이 두 계열을 통합하는 분석적 프레임워크를 개발한다.

1. 독립성 주변에서의 잔차 확장(Residual Expansion around Independence):
   저자들은 두 클러스터링이 독립적인 상태인 중립적 참조 모델을 정의하며, 이때 기대 확률는 $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$로 특징지어진다. 저자들은 이 베이스라인으로부터의 편차를 잔차 $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$를 사용하여 분석한다.

   • 상호 정보량 (MI): 본 논문은 독립성 베이스라인 주변에서 MI의 정확한 테일러 급수 전개를 유도한다. 주항(leading term)은 한계 가중 이차 형식(marginally weighted quadratic form, $\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$)이며, 이는 피어슨 $\chi^2$ 통계량에 대응한다. 이 가중치는 기대 질량이 작은 셀(희귀한 교집합)에서의 편차를 더 높게 평가한다.
   • 쌍 계수 지수 (예: Rand Index): Rand 지수는 한계 베이스라인(우연한 일치)과 잔차 항으로 분해된다. 잔차 성분은 비가중 이차 형식(unweighted quadratic form, $\sum \delta_{ij}^2$)과 선형 정렬 항으로 구성됨이 입증되었다. MI와 달리, 쌍 계수 척도는 기대 질량으로 나누지 않으므로 큰 클러스터에 의해 지배되며 소수 클러스터의 응집된 정렬을 과소평가한다.

2. 고차 튜플(Higher-Order Tuples)로의 확장:
   저자들은 쌍 계수 프레임워크를 순서 없는 쌍을 넘어 $k$-튜플로 확장한다. 이들은 $k$개의 독립적으로 샘플링된 요소들이 동일한 클러스터(또는 동일한 분할 셀)에 속할 확률인 **충돌 확률(collision probabilities)**의 계층을 도입한다.

   • $k=2$인 경우, 이는 표준적인 쌍 계수 양상들을 회복한다.
   • $k > 2$인 경우, 저자들은 $k$-요소의 공동 할당(co-assignments)의 일관성을 측정하는 레니 엔트로피 대조(Rényi entropy contrasts) $I^{(k)}$ 계열을 정의한다.
   • 이를 통해 쌍 계수가 레니 엔트로피와 연결된 더 넓은 계층 구조의 2차(order-two) 사례임을 보여줌으로써, 그룹 수준의 응집성에 대한 점점 더 엄격한 테스트를 제공하는 가교를 형성한다.

3. 요소 중심적 연결(Element-Centric Connection):
   본 논문은 이 튜플 계수 계층을 어피니티 그래프(affinity graphs) 상의 랜덤 워크에 기반한 요소 중심 유사성과 연결한다. 저자들은 엄격한 파티션(strict partitions)에 대해, $k$-튜플 충돌 확률이 $k$단계 동안 클러스터 내에 머무르는 랜덤 워크의 확률과 대응함을 입증함으로써, 샘플링 계층에 대한 기하학적 해석을 제공한다.

주요 기여

• 분석적 가교: 본 논문은 정보 이론적 척도와 쌍 계수 척도가 모두 동일한 분할표 잔차의 함수이며, 주로 가중치 부여 방식(확률 가중 vs 비가중)과 샘플링 공간(단일 요소 vs 순서 없는 쌍)에서 차이가 난다는 것을 보여주는 엄밀한 유도를 제공한다.
• 합의의 계층 구조: 쌍 계수가 레니 엔트로피와 연결된 충돌 계수 계층(collision-counting hierarchy, $k$-tuples)의 2차 멤버가 아니라, 별개의 패러다임이 아님을 확립한다.
• 발산의 해석 가능성: 척도들을 분해함으로써, 지수 간의 불일치(예: RI vs MI)가 임의적인 것이 아니라, 거대 클러스터의 광범위한 중첩을 강조할 것인지(쌍 계수) 아니면 소수 클로스터의 날카롭고 체계적인 정렬을 강조할 것인지(정보 이론적 척도)에 대한 명시적인 수학적 선택에서 비롯됨을 설명한다.

결과
통제된 합성 예제를 통해, 본 논문은 이러한 이론적 차이의 실질적인 함의를 입증한다:

• 균형 잡힌 클러스터: 클러스터 크기가 균형을 이루고 노이즈가 대칭적일 때, 가중치 차이가 미미해지므로 두 척도는 일치하는 경향을 보인다.
• 불균형한 클러스터: 강력한 클래스 불균형 하에서는 두 척도가 크게 갈라진다.
  • 소규모-소규모 불일치: 두 개의 작은 소수 클러스터 사이에서 요소들이 교체될 때, 정보 이론적 척도(MI)는 기대 질량의 역수에 의해 가중치가 부여되므로 급격히 감소한다. 반면, 쌍 계수 척도(ARI)는 변화하지 않은 큰 클러스터들에 의해 지배되므로 상대적으로 안정적이다.
  • 대규모-소규모 불일치: 대규모 클러스터와 소규모 클러스터 사이에서 요소들이 교체될 때, 모든 척도가 감소하지만, 잔차 분석을 통해 쌍 계수 척도가 대규모 클러스터의 붕괴에 의한 비가중 이차 항에 의해 구동됨을 알 수 있다.
• 고차 민감도: $k$-튜플 대조($I^{(k)}$)는 쌍 계수 척도($I^{(2)}$)가 (쌍 계수가 동일하다면) 확산된 중첩과 집중된 중첩을 구분할 수 없는 반면, 고차 튜플($I^{(3)}$ 등)은 쌍별 일치도가 응집된 그룹 수준의 구조에 의해 뒷받침되는지를 탐지할 수 있음을 보여준다.

의의 및 주장
본 논문은 이러한 통합이 척도 간의 불일치를 단순한 번거로움이 아닌, 각 척도가 강조하는 클러스터 구조에 대한 해석 가능한 증거로 변모시킨다고 주장한다.

• 저자들은 단일한 '최선의' 척도는 존재하지 않으며, 오히려 과업에 따라 지수를 선택해야 한다고 주장한다. 쌍 계수는 크고 동질적인 그룹 간의 거친 합의를 요약하는 데 적합하다. 정보 이론적 척도는 작지만 체계적인 정렬이나 소수 하위 유형을 탐지하는 데 우수하다. 고차 튜플 요약은 쌍별 일치가 응집된 그룹으로 확장되는지를 테스트하는 중간 단계의 영역을 제공한다.
• 이 프레임워크는 정규화, 우연 보정, 샘플링 가변성을 공통된 이론적 구조 내의 조절 가능한 영역으로 재구성하여, 실무자들이 경험적 시행착오가 아닌 제1원칙에 기반하여 지수를 선택할 수 있게 한다.
• 저자들은 잔차 확장이 독립성 베이스라인 근처에서 가장 투명하게 드러나며, 고차 튜플 계수는 유한 샘플에서 희소성 문제를 겪을 수 있음을 언급하며, 향후 유한 샘플 보정 및 중첩 또는 소프트 클러스터링으로의 확장을 시사한다.