Extending TCLUST to higher dimensions

기술 요약: tHDDC를 통한 TCLUST의 고차원 확장

문제 정의
이상치(Outliers)는 표준 클러스터링 방법의 결과를 크게 왜곡하여, 의미 있는 클러스터가 병합되거나 가짜 클러스터가 탐지되는 등 신뢰할 수 없는 분할을 초래할 수 있습니다. 절단(Trimming)에 기반한 TCLUST(Trimmed Clustering)와 같은 강건한 클러스터링 기법들이 이러한 문제를 완화하기 위해 개발되었으나, 고차원 설정에서는 심각한 한계에 직면합니다. 차원 $p$가 증가함에 따라, TCLUST는 두 가지 주요 요인으로 인해 어려움을 겪습니다: 전체 공분산 구조와 관련된 방대한 수의 파라미터를 추정하는 데 따르는 계산 복잡성, 그리고 알고리즘을 효과적으로 초기화하는 것의 어려움입니다. 반대로, 데이터가 저차원 부분 공간(subspaces) 근처에 위치한다고 가정하는 Robust Linear Grouping(RLG)과 같은 대안적 접근 방식은 차원 축소를 제공하지만, 등방성 직교 오차(isotropic orthogonal errors) 가정이나 교차하는 부분 공간을 처리하는 데 어려움을 겪는 등의 단순화된 가정을 따릅로 인해 한계가 있습니다.

방법론: tHDDC 접근 방식
이러한 한계를 해결하기 위해, 저자들은 TCLUST의 강건성과 HDDC(High-Dimensional Data Clustering)의 부분 공간 모델링을 결사한 방법인 tHDDC(Trimmed High-Dimensional Data Clustering)를 제안합니다.

• 모델 프레임워크: tHDDC는 데이터가 $G$개의 가우시안 성분의 혼합(mixture)으로부터 발생한다고 가정합니다. 전체 공분산 행렬을 추정하는 TCLUST와 달리, tHDDC는 각 클러스터 $g$가 고유 차원 $q_g$ ($q_g < p$)를 가진 아핀 부분 공간(affine subspace) $B_g$ 주변에 집중되어 있다는 절약된(parsimonious) 구조를 채택합니다.
• 공분산 구조: 각 클러스터의 산포 행렬(scatter matrix) $\Sigma_g$는 특정 부분 공간 $B_g$ (가장 큰 고윳값 $\lambda_{g1}, \dots, \lambda_{gq_g}$에 대응하는 $q_g$개의 고유벡터에 의해 생성됨)와 그 직교 보공간(orthogonal complement) $B_g^\perp$로 분해됩니다. $B_g^\perp$ 내에서의 분산은 하나의 공통 파라미터 $\lambda_g$에 의해 모델링됩니다. 이는 전체 공분산 추정에 비해 파라미터 수를 크게 줄여줍니다.
• 절단 및 제약 조건: 이 방법은 가장 이상치에 가까운 관측치들을 제외하기 위해 절단 수준 $\alpha$를 포함합니다. 수학적 적절성을 보장하고 퇴화된 해(degenerate solutions)를 방und하기 위해, 두 가지 고윳값 비율 제약 조건이 부과됩니다:
  1. 부분 공간 내 최대 고윳값들 간의 비율에 대한 제약 $c_1$.
  2. 클러스터 간 최소 고윳값(공통 노이즈 분산 $\lambda_g$)의 비율에 대한 제약 $c_2$.
• 알고리즘: 저자들은 EM 알고리즘의 변형인 "집중 단계(concentration steps, C-steps)"를 기반으로 하는 실행 가능한 알고리즘을 제시합니다. 절차는 다음과 같습니다:
  1. 무작위 초기화: 부분 공간 파라미터를 초기화하기 위해 관측치의 작은 부분 집합을 선택합니다.
  2. C-단계: 멤버십 가중치를 업데이트하고(가장 낮은 가능성을 가진 관측치를 절단), 클러스터 평균을 업데이트하며, 부분 공간 파라미터를 반복적으로 업데이트합니다.
  3. 고윳값 절단(Eigenvalue Truncation): 각 업데이트 후 고윳값 제약($c_1, c_2$)을 강제하기 위한 특정 절차를 도입하며, 이는 TCLUST에서 사용된 절단 방법을 확장한 것입니다.
  4. 고유 차원 추정: 과적합을 피하기 위해 복잡도 페널티를 사용하는 Cattell 기준에 기반한 데이터 구동형 절차를 통합하여 고유 차원 $q_g$를 자동으로 추정합니다.

주요 기여

1. 이론적 확장: 본 논문은 엄격하게 양수인 절단 수준이 사용될 경우, 완만한 조건 하에서도 모집단 극대화자(population maximizer)가 존재함을 증명함으로써 tHDDC 추정량의 존재성과 일관성을 확립합니다.
2. 알고리즘 혁신: HDDC의 절약된 파라미터화를 처리하면서 TCLUST의 강건한 절단 및 고윳값 제약을 통합하는 새로운 C-단계 알고리즘을 개발했습니다. 여기에는 이중 제약($c_1, c_2$)을 충족하기 위한 새로운 고윳값 절단 메커니즘이 포함됩니다.
3. 자동 차원 선택: 고유 차원 $q_g$를 자동으로 결정하는 방법을 제안하여, 수동 지정의 필요성을 줄이고 복잡도 페널티가 적용된 가능도 기준을 통해 과적합 위험을 완화합니다.
4. 진단 도구: 클러스터의 적절성을 평가하고 이상치를 탐지하기 위한 점수 거리(score distances) 및 직교 거리(orthogonal distances)를 포함한 그래픽 진단 도구와, 클러스터 할당 및 절단 결정의 신뢰성을 평가하기 위한 "판별 인자(discriminant factors)"를 도입합니다.

결과

• 시뮬레이션 연구: 클러스터 중첩 정도와 부분 공간 방향이 다양한 200차원($p=200$) 합성 데이터에 대한 실험에서, tHDDC는 모든 시나리오에서 완벽에 가까운 분류 정확도를 달리는 것을 보여주었습니다. 반면, TCLUST는 고차원에서 성능이 저하되었으며, RLG는 부분 공간이 교차할 때 실패했습니다. 또한, tHDDC는 유사한 조건 하에서 TCLUST보다 계산적으로 약 2.5배에서 3배 더 빠릅니다.
• 실제 데이터 적용: 이 방법은 인공적 및 실제 이상치가 혼입된 필기 숫자 데이터셋(USPS358)에 적용되었습니다. tHDDC는 약 7%(절단되지 않은 데이터 기준)의 분류 오차를 기록하여, TCLUST(오차 > 38%)와 비강건한 HDDC(오차 > 39%)를 크게 능가했습니다. 이 분석은 숫자 클러스터의 구조를 보존하면서 인공적인 이상치를 성공적으로 식별하고 제거했습니다.

의의 및 주장
본 논문은 tHDDC가 파라미터 폭발과 초기화 민감도로 인해 기존의 TCLUST와 같은 전통적인 방법들이 실패하는 중간 정도의 고차원 설정에서 강건하고 계산 효율적인 솔루션을 제공한다고 주장합니다. HDDC의 부분 공간 가정을 TCLUST의 강건한 절단과 결합함으로써, tHDDC는 교차하는 부분 공간과 비등방성 오차를 처리할 수 있는 RLG보다 덜 단순한 대안을 제공합니다. 저자들은 이 방법론이 클러스터 구조와 오염이 알려지지 않은 데이터셋에 특히 가치가 있으며, 기존의 강건한 고차원 클러스터링 기법에 비해 향상된 정확도와 감소된 계산 비용을 제공한다고 강조합니다. 향후 연구 과제로 함수형 데이터 확장 및 셀 단위 절단(cellwise trimming) 전략이 언급되었습니다.