Data compression for fast dimension reduction and clustering of high-dimensional discrete data

기술 요약: 고차원 이산 데이터의 빠른 차원 축소 및 클러스터링을 위한 데이터 압축

문제 정의
이진(binary), 범주형(categorical), 계수형(count-valued) 데이터를 포함한 고차원 이산 데이터는 유전체학, 미생물군집 연구, 행동 분석 등의 분야에서 널리 나타난다. 이러한 데이터를 클러스터링하는 것은 상당한 과제를 안겨준다. 기존 방법들은 계산 집약적이거나, 희소성(sparsity) 및 표본 공간의 이산적 특성에 민가하며, 혹은 연속형 데이터에 특화되어 설계되는 경우가 많다. 변수의 수 $p$가 표본 크기 $n$을 초과하거나 이에 필적하는 고차원 환경에서, 표준적인 접근 방식들은 "차원의 저주"에 직면한다. 즉, 거리가 정보를 덜 제공하게 되고, 노이즈가 신호를 압도하며, 유연한 모델들이 과적합(overparameterized)되는 문제가 발생한다. 차원 축소는 연속형 데이터에 대한 표준적인 전략(예: PCA를 통한)이지만, 이산 데이터에 적용하는 것은 까다롭다. 나이브한 임베딩(naive embeddings)은 구조를 왜곡할 수 있으며, 이산 데이터 특화 방법 중 다수는 확률적 최적화, 쌍별 비유사도 행렬($O(n^2)$), 또는 일반성을 제한하는 특정 분포 가정에 의존한다.

방법론
저자들은 고차원 이산 관측치를 저차원 연속 공간으로 매핑하는 결정론적이고 비확률적인 데이터 압축 프레임워크(이하 DC)를 제안한다. 핵심 메커니즘은 **스케일링된 위치 인코딩(scaled positional encoding)**이다:

1. 10진법 기반 압축: 이 방법은 각 이산 관측 벡터 $y_i \in \{0, \dots, K-1\}^p$를 $K$ 진법의 숫자로 취급한다. 표준적인 $K$ 진법 전개는 하나의 커다란 정수로의 단사 매핑(injective mapping)을 생성한다. 그러나 지수적 가중치 성장($K^{p-j}$)으로 인해 큰 $p$에 대해서는 계산적으로 불가능하다.
2. 스케일링된 변환: 수치적 안정성을 보장하기 위해, 저자들은 가중치가 정규화된 스케일링된 압축 $z_i$를 다음과 같이 정의한다:
   $$z_i = \sum_{j=1}^p \frac{K^{p-j}}{p K^{1/K}} y_{ij}$$
   계수들은 균등하게 유계(uniformly bounded)되어 있어, 큰 $p$와 임의의 $K$에 대해서도 변환이 안정적으로 유지된다.
3. 다차원 확장: 시각화하거나 더 많은 정보를 보존하기 위해, 변수들을 $q$개의 서로소인 블록(disjoint blocks)으로 분할한다. 각 블록은 동일한 스케일링 가중치 체계를 사용하여 독립적으로 압축되며, 그 결과 $q$차원의 연속 벡터 $z_i \in \mathbb{R}^q$가 생성된다.
4. 변수 순서 지정: 정보가 풍부한 특징(feature)의 분산 기여도를 극대화하기 위해, 압축 전 각 블록 내의 변수들을 감소하는 표본 분산 순으로 정렬한다.
5. 압축 공간에서의 클러스터링: 결과로 얻어진 저차원 연속 데이터 $Z$는 표준 알고리즘을 사용하여 클러스터링할 수 있다. 저자들은 특히 k-means와 **가우시안 혼합 모델(GMM)**을 평가하며, 완만한 정규성 조건(중심한계정리에 의해) 하에서 압축된 변수들이 근사적으로 가우시안 분포를 따른다는 점에 주목한다.

주요 이론적 기여
본 논문은 제안된 압축의 세 가지 주요 이론적 특성을 확립한다:

• 단사성(Injectivity): 매핑은 단사적이며, 이는 서로 다른 이산 관측치가 서로 다른 압축 값에 매핑됨을 보장한다. 이는 해밍 거리(Hamming distance)와 같은 이산 거리 측정법에서 흔히 발생하는 "동점(ties)" 문제를 방절한다.
• 근사적 가우시안성(Approximate Gaussianity): 독립성과 완만한 모멘트 조건을 가정할 때, 압축된 좌표는 근사적으로 가우시안 분포를 따른다. 이는 압축된 공간에서 모델 기반 클러스터링(GMM)을 사용하는 것에 대한 이론적 근거를 제공한다.
• 중심점 보존(Centroid Preservation): 원래의 고차원 공간에서의 클러스터 중심점 간의 분리는 압축된 공간에서도 보존된다. 원래의 중심점이 적어도 하나의 좌표에서 다르다면, 그들의 압축된 대응물 역시 구별 가능한 상태로 남는다. 이는 위치 기반 클러스터 구조가 차원 축소 후에도 식별 가능함을 보장한다.

실증적 결과
저자들은 다섯 가지 시나리오(독립 계수 데이터, 상관관계가 있는 계수 데이터, 이진 데이터, 노이즈가 포함된 계수 데이터, 그리고 다양한 표본 크기 및 차원 $n \in \{50, 200\}, p \in \{100, 5000\}$)에 걸쳐 광범적인 시뮬레이션을 수행했다. 제안된 방법(DC)을 PCA, t-SNE, 다차원 척도법(MDS), 스펙트럴 클러스터링(Spectral Clustering), 그리고 표준 k-means와 비교하였다.

• 정확도: DC 기반 클러스터링은 경쟁력 있는 차원 축소 기법들을 능가하며, 종종 완벽에 가까운 실제 클러스터 복구 성능을 보여주는 높은 조정 랜드 지수(Adjusted Rand Index, ARI)를 일관되게 달성했다. 성능은 상관관계가 있는 변수와 높은 비율의 노이즈 특징이 있는 경우에도 견고함을 유지했다.
• 강건성: 깨끗한 설정에서는 k-means가 잘 작동했지만, 노이즈가 비구형(non-spherical) 클러스터 기하 구조를 유발하는 노이즈가 많은 시나리오에서는 GMM(mclust 패키지 사용)이 더 우수한 것으로 나타났다.
• 계산 효율성: DC는 상당한 속도 향상을 입증했다. DC는 MDS보다 약 14배, PCA보다 20배, t-SNE보다 181배 더 빨랐다. DC의 복잡도는 $O(np)$인 반면, MDS는 $O(n^2p)$, t-SNE는 $O(n^2)$이다.
• 응용: 이 방법은 아일랜드의 아기 이름 기록과 미생물군집 데이터(하드자 수렵 채집인과 이탈리아 도시 성인 비교)에 적용되어, 실제 세계의 고차원 이산 데이터에 대한 실용적 유용성을 입증했다.

의의 및 주장
본 논문은 고차원 이산 데이터 클러스터링을 위한 확장 가능하고, 계산 효율적이며, 폭넓게 적용 가능한 프레임워크를 제공한다고 주장한다. 본 연구의 의의는 차원 축소의 필요성과 기존 이산 데이터 방법론의 한계 사이의 간극을 메우는 데 있다. 결정론적이고 단사적이며 수치적으로 안정적인 변환을 제공함으로써, 이 접근 방식은 연구자들이 고차원 이산 혼합 모델을 적합시키거나 쌍별 유사도를 계산하는 계산적 부담 없이, 표준적이고 효율적인 클러스터링 알고리즘(예: k-means 및 GMM)을 이산 데이터에 활용할 수 있게 한다. 저자들은 이 방법이 가우시안 기반 모델링이 가능한 연속 형태로 변환하면서도 필수적인 클러스터 구조(중심점 분리)를 보존하며, 이를 통해 이산 관측치에 대한 차원의 저주를 효과적으로 완화한다고 강조한다.