Local spectral clustering for heterogeneous clustering structures

기술 요약: 이질적 클러스터링 구조를 위한 국소 스펙트럴 클러스터링 (Local Spectral Clustering)

문제 정의
고전적인 클러스터링 방법들은 모든 정보성 특징(feature)이 단일한 잠재적 관측치 분할(latent partition)을 지지한다는 "글로벌 클러스터링" 패러다임 하에서 작동한다. 이러한 가정은 많은 응용 분야에서 효과적이지만, 현대의 고차원 데이터(예: 유전체학, 단백질체학, 전자 건강 기록)에는 지나치게 제한적이다. 이러한 환경에서 특징들은 과학적 의미와 의존 구조가 서로 이질적일 수 있다. 특정 특징의 부분 집합은 서로 다른 유사성 개념을 인코딩하여 서로 다른 샘플 분할을 유도할 수 있는 반면, 다른 특징들은 의미 있는 클러스터링 정보를 포함하지 않을 수 있다. 기존의 국소 클러스터링 방법들, 특히 베이지안 접근법(예: Lee et al., 2013)은 복잡한 잠재 변수 모델과 계산 집약적인 사후 샘플링에 의존하는 경우가 많다. 또한, 이들은 일반적으로 분할을 확률 모델의 간접적인 출력물로 취급하며, 이를 통해 특징 간의 구조를 비교하거나 통일된 이론적 회복 보장(recovery guarantees)을 확립하는 것을 어렵게 만든다.

방법론
저자들은 이질적인 클서터링 구조를 명시적으로 표현하는 **국소 스펙트럴 클러스터링 (Local Spectral Clustering, LSC)**을 위한 빈도주의 프레임워크를 제안한다.

• 클러스터링 행렬 표현: 핵심 혁신은 각 샘플 분할을 두 관측치가 동일한 클러스터에 속하는지 여부를 나타내는 클러스터링 행렬 $P$로 표현하는 것이다. 이 표현은 레이블 순열에 불변하므로 특징 간의 구조를 직접 비교할 수 있게 한다. 특징들은 동일한 클러스터링 행렬을 유도하는 경우 하나의 그룹으로 묶인다.
• 모델 설정: 데이터는 이질적 서브 가우시안 혼합 모델 (Heterogeneous Sub-Gaussian Mixture Model, SGMM) 하에서 모델링된다. $p$개의 특징은 $G$개의 정보성 그룹(각각 특정 샘플 분할과 $M_g$개의 클러스터를 유도함)과 하나의 비정보성 그룹(단일 클러스터를 유도함)으로 분할된다. 정보성 그룹 내의 관측치들은 그룹별 평균과 노이즈 레벨을 가진 서브 가우시안 분포를 따른다.
• 최적화 기준: 본 방법은 특징별 가우시안 커널 유사도 행렬 $K_j$를 구성한다. 그 후, 특징 그룹을 식별하고 이와 관련된 클러스터링 행렬을 동시에 추정하기 위해 최적화 문제를 해결한다. 목적 함수는 유효한 클러스터링 구조를 강제하는 제약 조건과 비정보성 특징(전부 1로 이루어진 행렬 $E_n$으로 표현됨)을 분리하는 제약 조건 하에서, 커널 행렬과 추정된 클러스터링 행렬 사이의 내적을 최대화한다.
• 알고리즘: 저자들은 K-평균(K-means)의 로이드(Lloyd) 알고리즘과 유사한 반복 알고리즘(Algorithm 1)을 제안한다. 이는 다음 과정을 교대로 수행한다:
  1. 현재 그룹 수준의 클러스터링 행렬 추정치와의 유사성을 기반으로 특징을 그룹에 할당한다.
  2. 할당된 특징들의 커널 행렬을 평균 내고 목적 함수를 최적화함으로써 그룹 수준의 클러스터링 행렬을 업데이트한다.
  3. 추정된 그룹 행렬에 대해 축소 랭크 스펙트럴 클러스터링(절단된 고윳값 분해를 통해)을 적용하여 샘플 멤버십을 회복한다.
• 튜닝: 이 프레임워크는 스케일링 파라미터($\theta_j$), 임계값 파라미터($\tau$), 그리고 고윳값 간격(eigen-gap) 휴리스틱을 사용한 클러스터 수($M_g$)를 선택하기 위한 데이터 기반 절차를 포함한다.

주요 기여

1. 새로운 통계적 정식화: 본 논문은 국소 클러스터링을 잠재 모델 파라미터가 아닌 클러스터링 행렬을 주요 통계적 객체로 사용하는 특징 그룹화 문제로 재정의하여 소개한다.
2. 계산 효율적인 프레임워크: 제안된 LSC 방법은 명시적인 가능도(likelihood) 지정이나 베이지안 사후 계산을 피한다. 이는 고차원 환경으로 확장 가능하며 결정론적인 최적화 접근 방식을 활용한다.
3. 통합된 이론적 분석: 저자들은 이질적 서브 가우시안 혼합 모델 하에서 포괄적인 이론적 프레임워크를 구축하였다. 주요 결과는 다음과 같다:
   • 오라클 추정기(특징 그룹을 알고 있다고 가정할 때)에 대한 비점근적 오차 경계.
   • 진정한 특징 그룹 구조가 높은 확률로 목적 함수의 국소 최댓값으로서 점근적으로 회복된다는 증명.
   • 여러 특징 그룹에 걸쳐 동시에 오차를 제어하는 추정된 샘플 분할에 대한 균등 상한 오차(uniform upper bounds on misclassification errors).
4. 실증적 검증: 제안된 방법은 광범위한 시뮬레이션과 실제 응용 사례를 통해 검증되었으며, 정확도와 계산 효율성 측면 모두에서 기존의 국소 클러스터링 방법(예: 비매개변수적 베이지안 국소 클러스터링) 및 글로벌 방법보다 우수함을 입증하였다.

결과

• 시뮬레이션: $G=3$개의 정보성 그룹과 다양한 샘플 크기($n$) 및 특징 수($s$)를 가진 몬테카를로 시뮬레이션에서, LSC 방법은 진정한 특징 그룹 구조와 샘플 분할을 일관되게 회복하였다. $n$과 $s$가 증가함에 따라 LSC의 성능은 실행 불가능한(infeasible) "오라클(Oracle)" 방법의 성능에 수렴하였다. LSC는 이질적 구조 하에서 실패하는 Sparse K-means(SKM) 및 Spectral Clustering with Feature Selection(SCFS)과 같은 경쟁 방법들을 크게 앞질렀다. 베이지안 방법(NBLC)이 일부 소규모 샘플 설정에서 대등한 성능을 보였으나, LSC는 특징 선택(True Negative Rate)에서 더 우수한 성능을 보였으며 계산적으로 더 효율적이었다.
• 실제 데이터 적용: 본 방법은 146명의 급성 골수성 백혈병(AML) 환자로부터 얻은 역상 단백질 어레이(RPPA) 데이터에 적용되었다. 분석 결과, 서로 다른 환자 계층화를 유도하는 두 개의 뚜렷한 단백질 그룹(PG1 및 PG2)을 식별하였다.
  • PG1은 알려진 생물학적 신호를 재현하였으며, 기존 방식(CC)에는 잘 반응하지만 베네토클락스(venetoclax, VH) 기반 치료에는 반응이 낮은 환자 군을 식별하였다.
  • PG2는 이전 분석에서 차이가 없다고 판단되었던 환자 클러스터 내에서 명확한 치료 이질성을 드러냈다. 구체적으로, PG2 기반 클러스터링은 기존의 균일한 그룹을 두 개의 하위 클러스터로 나누었으며, 두 그룹 모두 VH 치료에 비해 CC 치료 시 생존율이 유의미하게 높음을 보여주었다. 이는 PG2가 이전의 단일 분할 분석에서는 놓쳤던 치료 반응과 관련된 별개의 생물학적 메커니즘을 포착하고 있음을 시사한다.

의의
본 논문은 이질적 특징 구조를 가진 국소 클러스터링에 대한 최초의 빈도주의적 이해를 제공한다고 주장한다. 클러스터링 행렬을 기반으로 특징 그룹화 문제를 재정의함으로써, 저자들은 이론적으로 엄밀하면서도(특징 그룹과 샘플 분할 모두에 대한 회복 보장을 제공) 실용적으로 확장 가능한 방법을 제시한다. 이 프레임워크는 고차원 데이터의 글로벌 클러스터링 가정의 한계를 해결하며, 공존하는 여러 클러스터 구조를 발견할 수 있는 유연한 도구를 제공한다. 저자들은 현재의 프레임워크가 겹치지 않는 특징 그룹을 가정하고 있으나, 향후 연구를 통해 중첩되는 그룹이나 근사적 구조적 유사성을 탐구하여 유연성을 더욱 높일 수 있다고 언급하였다.