Inference for Clustering: Conformal Sets for Cluster Labels

1. 문제 정의 (Problem Formulation)

클러스터링은 과학 및 산업 전반에 걸쳐 널리 사용되지만, 클러스터 할당 (cluster assignment) 에 대한 불확실성을 엄격한 보장을 통해 정량화하는 방법은 거의 존재하지 않습니다. 기존 연구들은 클러스터의 존재 여부 (SigClust 등) 나 모델 구조적 불확실성 (베이지안 접근법 등) 에 초점을 맞추는 경향이 있으나, 클러스터링 알고리즘이 생성한 레이블 자체의 불확실성을 모델에 구애받지 않는 (model-agnostic) 방식으로 다루는 프레임워크는 부재했습니다.

이 논문이 해결하려는 핵심 문제는 다음과 같습니다:

• 레이블의 비관측성: 클러스터링은 지도 학습과 달리 참 레이블 (ground truth) 이 관찰되지 않습니다. 데이터로부터 추정된 레이블을 사용하여 컨포멀 예측 (conformal prediction) 을 수행할 경우, 레이블 추정으로 인한 분포 이동 (distribution shift) 과 교환성 (exchangeability) 위반이 발생합니다.
• 기존 방법의 한계:
  • 단순 임계값 (Cutoff) 방식: 소프트 레이블 (확률) 에 임계값을 적용하는 방식은 레이블이 잘 보정 (calibrated) 되지 않아 과소 커버리지 (under-coverage) 또는 불필요하게 큰 불확실성 구간을 생성합니다.
  • 나쁜 분할 컨포멀 클러스터링 (Naive Split Conformal): 결정론적 (deterministic) 인 하드 레이블을 사용하는 기존 분할 컨포멀 방법은 레이블의 불확실성을 반영하지 못해 심각한 과소 커버리지를 유발합니다.

2. 제안된 방법론 (Methodology)

저자들은 확률적 레이블 (Stochastic Labels) 을 활용한 분할 컨포멀 클러스터링 (Split Conformal Clustering with Stochastic Labels) 프레임워크를 제안합니다. 이 방법은 임의의 클러스터링 알고리즘을 입력받아 데이터 공간의 모든 지점에 대해 클러스터 멤버십에 대한 신뢰 구간 (confidence sets) 을 생성합니다.

핵심 알고리즘 (Algorithm 1)

1. 데이터 분할: 데이터를 훈련 세트 ($I_{tr}$) 와 캘리브레이션 세트 ($I_{ca}$) 로 무작위 분할합니다.
2. 확률적 클러스터링 적용: 훈련 세트와 캘리브레이션 세트 각각에 대해 확률적 클러스터링 알고리즘을 적용합니다.
   • 확률적 클러스터링: 소프트 클러스터링 알고리즘 (예: 가우시안 혼합 모델, 퍼지 C-평균) 이 출력한 확률 벡터에서 레이블을 무작위로 샘플링합니다. 이는 레이블 할당의 불확실성을 모델 내부에 재도입 (re-introduce) 하는 과정입니다.
3. 소프트 분류기 학습: 훈련 세트의 (데이터, 샘플링된 레이블) 쌍을 사용하여 소프트 분류기 $\hat{\pi}$를 학습합니다.
4. 레이블 정렬 (Alignment): 훈련 세트와 캘리브레이션 세트의 클러스터링 결과가 서로 다른 순열 (permutation) 을 가질 수 있으므로, 캘리브레이션 세트에서 예측된 레이블과 샘플링된 레이블 간의 불일치를 최소화하는 순열을 찾아 정렬합니다.
5. 컨포멀 점수 및 신뢰 구간 구성: 캘리브레이션 세트의 점수 (conformity scores) 를 기반으로 임계값을 설정하고, 새로운 테스트 포인트 $x$에 대해 해당 임계값을 만족하는 레이블들의 집합 $\hat{C}(x)$를 신뢰 구간으로 반환합니다.

이론적 기반

• 교환성 회복: 결정론적 레이블 대신 확률적 레이블을 샘플링함으로써, 레이블 할당의 변동성을 고려하여 교환성 위반을 완화하고 유효한 커버리지를 보장합니다.
• 커버리지 하한 (Coverage Bound): 제안된 방법의 마진 커버리지 (marginal coverage) 는 다음 두 가지 클러스터링 알고리즘의 성질에 의해 제어됩니다.
  1. 일관성 (Consistency): 추정된 소프트 레이블이 참 레이블 분포에 수렴하는 정도.
  2. 치환-단일 안정성 (Replace-One Stability): 데이터 포인트 하나를 변경했을 때 클러스터링 결과의 분포가 얼마나 안정적인지.

3. 주요 기여 (Key Contributions)

1. 클러스터링 레이블을 위한 최초의 컨포멀 프레임워크: 비지도 학습의 특성 (레이블 비관측성) 을 극복하고, 모델에 구애받지 않는 유효한 유한 표본 (finite-sample) 커버리지를 보장하는 첫 번째 체계적인 프레임워크를 제시했습니다.
2. 확률적 레이블의 도입: 결정론적 할당의 한계를 극복하기 위해 소프트 클러스터링에서 레이블을 샘플링하는 '확률적 클러스터링' 개념을 도입하여, 교환성 위반 문제를 해결하고 커버리지 보장을 이론적으로 증명했습니다.
3. 이론적 분석:
   • 유한 표본에서의 커버리지 하한을 일관성과 안정성 항으로 분해하여 제시했습니다.
   • 잘 지정된 (well-specified) 매개변수 혼합 모델 (parametric mixture models) 에서 점근적 커버리지가 보장됨을 증명했습니다.
4. 실증적 검증:
   • 시뮬레이션 (가우시안 및 감마 혼합 모델) 을 통해 제안된 방법이 목표 커버리지 (예: 90%) 를 달성하면서도 정보력 있는 (informative) 신뢰 구간 크기를 유지함을 보였습니다.
   • 반면, 나쁜 방법 (Naive) 들은 과소 커버리지를 보이거나 불필요하게 큰 구간을 생성함을 확인했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 (GMM 및 GaMM):
  • 커버리지: 제안된 방법 (Split CC Stochastic) 은 다양한 분산 조건과 표본 크기에서 목표 커버리지를 달성했습니다. 반면, 하드 레이블을 사용한 나쁜 방법 (Split CC Naive) 은 표본 크기가 커져도 과소 커버리지를 보였습니다.
  • 구간 크기: 제안된 방법은 불확실성이 높은 경계 영역에서는 여러 레이블을 포함하는 구간을 생성하고, 명확한 영역에서는 단일 레이블을 선택하여 불확실성을 직관적으로 표현했습니다.
• 실제 데이터 적용 (단일 세포 RNA 시퀀싱, PBMC-3K):
  • 7 가지 세포 유형을 식별하는 데 적용했습니다.
  • B 세포 및 NK 세포: 명확한 마커 유전자를 가지고 있어 높은 확신 (단일 레이블 신뢰 구간) 을 보였습니다.
  • T 세포 및 단핵구/수지상 세포: 생물학적으로 이질적이고 중첩된 상태이므로, 불확실성이 높아 신뢰 구간 크기가 커지는 (여러 레이블 포함) 결과가 나왔습니다. 이는 실제 생물학적 특성과 일치하며 방법론의 해석 가능성을 입증했습니다.

5. 의의 및 결론 (Significance)

이 논문은 비지도 학습과 분포 자유 추론 (distribution-free inference) 을 연결하는 중요한 이정표를 세웠습니다.

• 과학적 신뢰성 향상: 클러스터링 결과의 불확실성을 정량화함으로써, 특히 단일 세포 분석과 같이 민감한 과학적 발견에서 잘못된 결론을 내리는 위험을 줄이고 결과의 신뢰성을 높입니다.
• 해석 가능성: 데이터 포인트가 어떤 클러스터에 속하는지 명확한지, 아니면 여러 클러스터의 경계에 있는지 (모호한 영역) 를 시각적으로 보여줌으로써 연구자들이 데이터의 구조를 더 깊이 이해할 수 있게 돕습니다.
• 미래 방향: 클러스터 수 $K$를 선택하는 과정의 불확실성 통합, 하드 레이블 알고리즘 (K-means 등) 을 부트스트래핑 등을 통해 확률적으로 변환하는 방법, 그리고 가중치 컨포멀 추론을 통한 분포 이동 보정 등 향후 연구의 중요한 방향성을 제시했습니다.

요약하자면, 이 연구는 클러스터링 레이블의 불확실성을 엄격하게 정량화할 수 있는 새로운 표준을 제시하며, 데이터 과학 및 생물정보학 분야에서 더 견고하고 해석 가능한 클러스터링 분석을 가능하게 합니다.