Class Angular Distortion Index for Dimensionality Reduction

Gunaratne, Kobourov, Miller 의 논문 "Class Angular Distortion Index for Dimensionality Reduction"에 대한 상세한 기술적 요약입니다.

1. 문제 제기

차원 축소 (DR) 기법 (예: t-SNE, UMAP, PCA) 은 고차원 데이터를 시각화하는 데 필수적입니다. 그러나 현재 DR 평가의 중요한 한계는 클러스터 관계의 오해석입니다.

• 핵심 문제: 많은 DR 방법이 클러스터를 성공적으로 분리하여 (명확한 '덩어리'로 만듦) 도출하지만, 이러한 클러스터 간의 전역 기하학적 관계를 왜곡하는 경우가 많습니다. 예를 들어, 중첩된 구조, 곡선 매니폴드, 또는 얽힌 클러스터가 투영 과정에서 평면화되거나 임의로 재배열될 수 있습니다.
• 기존 지표의 한계: 현재 품질 지표들은 다음과 같은 결함이 있는 가정에 의존하기 때문에 이러한 왜곡을 포착하지 못합니다.
  • 분리 가능성 가정: 실루엣 점수 (Silhouette Score) 와 데이비스 - 볼딘 지수 (Davies-Bouldin Index) 와 같은 지표는 클러스터가 컴팩트하고, 구형이며, 잘 분리되어 있다고 가정합니다. 이러한 지표는 진정한 위상 구조를 파괴하더라도 (예: 중첩된 구를 별도의 원으로 변환) 조밀하고 격리된 '덩어리'를 생성하는 투영을 높게 평가합니다.
  • 중심점 편향: 라벨 신뢰도 및 연속성 (Label-T&C) 과 같은 지표는 클러스터 중심점에 의존합니다. 클러스터가 겹치거나 중첩된 경우 (중심점이 일치함), 이러한 지표는 충실한 투영과 무작위 투영을 구별하지 못합니다.
  • 점 단위 대 클러스터 수준: 대부분의 지표는 점 간 또는 쌍별 거리를 평가하여 점들의 그룹 간 고차원 기하학적 관계를 놓칩니다.

2. 방법론: 클래스 각도 왜곡 지수 (CADI)

저자들은 내부 각도를 사용하여 클러스터 간 기하학적 관계의 보존을 평가하도록 설계된 새로운 지표인 CADI를 제안합니다.

핵심 개념

중심점이나 개별 점 간의 거리를 측정하는 대신, CADI 는 기준점이 한 클래스에 속하고 나머지 두 점이 다른 클래스에 속하는 점의 세 쌍 (triplets) 이 형성하는 내부 각도를 측정합니다.

• 직관: 클러스터 $C_a$의 한 점의 관점에서 (각도 $\angle jik$을 통해) 클러스터 $C_b$가 어떻게 '보이는지' 관찰함으로써, 이 지표는 클러스터의 모양과 상대적 방향을 포착합니다.
• 미분 가능성: 각도의 코사인 유사도에 의존하기 때문에 CADI 는 미분 가능하며, 최적화를 위한 손실 함수로 사용할 수 있습니다.

수학적 정의

클래스 분할 $C$를 가진 데이터셋 $X$와 투영 $Y$가 주어졌을 때:
$$\text{CADI}(X, Y, C) = \frac{1}{T} \sum_{i \in C_a, j,k \in C_b, j \neq k} \left( \cos(\theta_X(j,i,k)) - \cos(\theta_Y(j,i,k)) \right)^2$$
여기서:

• $i$는 클래스 $C_a$의 기준점입니다.
• $j, k$는 다른 클래스 $C_b$에 속하는 점들입니다.
• $\theta$는 $j$와 $k$로 향하는 벡터가 $i$에서 형성하는 내부 각도를 나타냅니다.
• $T$는 샘플링된 세 쌍의 총 수입니다.
• 목표: CADI 를 최소화합니다 (0 에 가까울수록 좋습니다).

실용적 구현

• 샘플링: 전체 합을 계산하는 것은 $O(n^3)$입니다. 저자들은 $k = O(n)$개의 세 쌍 (구체적으로 $40n$개) 을 샘플링하면 무시할 수 있는 분산으로 안정적인 결과를 얻을 수 있음을 입증하여 이 지표의 확장성을 입증했습니다.
• 불변성: CADI 는 각도에만 의존하므로 평행 이동, 회전, 균일한 스케일링에 대해 불변입니다.
• AngleEmbedding: 저자들은 CADI 를 손실 함수로 사용하여 순방향 신경망 (feedforward network) 을 통해 최적화하는 새로운 DR 알고리즘인 AngleEmbedding을 소개합니다. 이는 클래스 간 각도 관계를 특히 보존하는 투영을 생성합니다.

3. 주요 기여

1. 새로운 지표 (CADI): 기존 지표들의 '구형성'과 '분리 가능성' 가정을 넘어선 클러스터 수준의 품질 지표입니다. 중첩, 곡선, 또는 얽힌 클러스터와 같은 복잡한 구조의 보존을 특히 목표로 합니다.
2. 실패 모드 증명: 이 논문은 기존 지표들 (실루엣, Label-T&C 등) 이 종종 복잡한 위상을 충실히 보존하는 투영보다 무작위 투영이나 '덩어리' 투영을 더 높게 평가한다는 방대한 증거를 제시합니다.
3. AngleEmbedding 알고리즘: CADI 를 최적화하는 새로운 지도 학습 DR 기법으로, 이 지표가 고품질 투영 생성을 효과적으로 주도할 수 있음을 입증합니다.
4. 종합 벤치마킹: 중첩된 구, 링, 유전자 발현, 텍스트 데이터를 포함한 20 개 이상의 합성 및 실제 데이터셋에 대한 평가로, CADI 를 8 가지 다른 지표 및 8 가지 DR 알고리즘과 비교했습니다.

4. 결과

평가 결과는 CADI 와 기존 지표 간의 상당한 불일치를 강조합니다.

• 합성 데이터 (중첩된 구 및 링):
  • 시나리오: 데이터는 5 개의 중첩된 구 또는 서로 걸린 링의 사슬로 구성됩니다.
  • 기존 지표: 실루엣 점수와 Label-T&C 는 종종 링을 별도의 덩어리로 분리하거나 구를 흩뜨리는 t-SNE나 UMAP를 최상으로 평가하거나, 중심점이 겹치기 때문에 무작위 투영을 높게 평가합니다.
  • CADI: 위상을 파괴하는 방법들에 가장 낮은 점수를 부여하는 반면, 선형 또는 중첩 순서를 보존하는 AngleEmbedding과 PCA를 최상으로 올바르게 식별합니다.
• 실제 데이터 (Liver, USPS, TREC):
  • Liver 데이터: 간암 세포 (HCC) 는 건강한 세포보다 분산이 큽니다. t-SNE 는 크기가 같은 분리된 덩어리를 생성하여 이 분산을 숨깁니다. CADI 는 HCC 클러스터가 더 넓게 퍼져 있음을 올바르게 보여주는 AngleEmbedding과 PCA를 높게 평가합니다.
  • USPS (숫자): 클러스터 크기는 숫자에 따라 크게 달라집니다. t-SNE 는 크기가 같은 클러스터를 강제로 생성합니다. CADI 는 클러스터 크기가 실제 데이터 분포를 반영하는 투영 (AngleEmbedding 에 의해 보존됨) 을 높게 평가합니다.
  • 상관관계: CADI 는 다른 지표들과 낮은 상관관계를 보입니다 (예: 실루엣과의 스피어만 상관관계는 약 0.24), 이는 투영 품질의 서로 다른 측면을 측정함을 확인시켜 줍니다.
• 하이퍼파라미터 튜닝: CADI 는 UMAP 의 하이퍼파라미터 선택을 안내하는 데 성공적으로 사용되었으며, 시각적 검토가 모호할 때조차 전역 구조를 더 잘 보존하는 구성을 식별했습니다.

5. 의의 및 결론

• 패러다임 전환: 이 논문은 클러스터 관계 분석 (예: 위계, 중첩, 또는 전역 위상 이해) 과 관련된 작업의 경우, 현재의 '분리 가능성 중심' 지표는 오해의 소지가 있다고 주장합니다. CADI 는 구조적 충실도를 평가하기 위한 필수적인 대안을 제공합니다.
• 도구 선택: 저자들은 적절한 사용 사례를 명확히 합니다.
  • t-SNE/UMAP는 단순히 클러스터의 수를 식별하거나 초기 탐색을 목표로 할 때 사용합니다.
  • CADI/AngleEmbedding은 클러스터가 서로 어떻게 관련되는지, 상대적 위치, 그리고 기하학적 모양을 이해하는 것을 목표로 할 때 사용합니다.
• 향후 작업: 저자들은 AngleEmbedding 을 비유클리드 공간 (구, 쌍곡면) 으로 확장하고 각도 오차의 집계 이론에 대한 추가 분석을 제안합니다.

요약하자면, CADI는 클러스터 간 기하학의 왜곡을 정량화함으로써 차원 축소 평가의 중요한 맹점을 해결하며, 복잡하고 비구형인 데이터 구조를 다루는 분석가들에게 더 신뢰할 수 있는 지침을 제공합니다.