Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

기술 요약: 깊이 기반 국소 중심 클러스터링 (DLCC)

문제 정의
클러스터 분석은 데이터 과학의 기초적 요소이지만, 기존 방법론들은 다양한 실제 데이터 분포를 다루는 데 있어 종종 어려움을 겪습니다. 전통적인 접근 방식은 일반적으로 다음과 같은 특정 한계를 지닌 두 가지 범주로 나뉩니다:

• 중심 기반 방법론 (예: k-means): 각 클러스터에 하나의 대표 점을 가정하며 구형(spherical) 형태를 전제로 합니다. 이는 이상치와 초기화에 민감하며, 비볼록(non-convex) 기하 구조를 모델링하는 데 실패합니다.
• 밀도 기반 방법론 (예: DBSCAN, Mean Shift): 임의의 형태를 처리할 수 있지만, 밀도 추정이나 고정된 임계값에 의존합니다. 이는 고차원 공간이나 클러스터의 밀도가 서로 다른 경우 불안정할 수 있습니다.
• 그래프 기반 방법론은 대규모 데이터에 대해 계산적 제약을 받거나 거리 메트릭 선택에 민간한 경우가 많습니다.

이러한 패러다임 전반에 걸친 핵심적인 한계는 "엑셈플러(exemplars, 대표점)"의 정의입니다. 대부분의 방법은 엑셈플러를 차원이나 기하 구조에 관계없이 일반화될 수 없는 거리 또는 밀도 기준에 결부시킵니다. 또한, **통계적 데이터 깊이(statistical data depth)**는 다변량 데이터에 대한 강건한 중심-외곽 정렬을 제공하지만, 역사적으로는 로컬 구조와 다봉성(multimodality)을 식별하기 위한 주요 메커니즘이 아닌 보조 도구(예: 초기화 용도)로만 사용되어 왔습니다. 표준 깊이 함수는 다봉 특성을 직접 포착하지 못합니다.

방법론: DLCC 프레임워크
본 논문은 전역 거리 메트릭이나 밀도 추정에 의존하지 않고, 통계적 데이터 깊이를 활용하여 국소 중심을 정의하고 유사도를 구축하는 깊이 기반 국소 중심 클러스터링 (Depth-Based Local Center Clustering, DLCC) 프레임워크를 제안합니다.

1. 깊이 기반 유사도 행렬:
   DLCC는 유클리드 거리를 사용하는 대신, **공간 깊이(Spatial Depth, SD)**를 기반으로 유사도 행렬 $S$를 구축합니다. 깊이 개념을 국소화하기 위해, 본 방법은 각 관측치 $x_i$에 대해 원래의 샘플 $X$와 $x_i$를 통한 모든 점의 반사(reflection)로 구성된 반사 데이터셋 $X_{Ri}$를 정의합니다. $x_i$는 $X_{Ri}$의 대칭 중심이 되므로, 이 점의 깊이는 최대값(1)을 가집니다. $X_{Ri}$에 대한 다른 점 $x_j$의 깊이를 $D(x_j | X_{Ri})$라고 할 때, 이는 $x_j$와 $x_i$ 사이의 유사도 척도로 기능합니다.

   • 효율성: 저자들은 이러한 깊이를 효율적으로 계산하기 위해 단위 벡터 합과 노름(norm)을 사전 계산하여 중복 계산을 줄이는 행렬 기반 구현을 도입하였으나, 이론적 복잡도는 여전히 $O(n^3)$입니다.

2. 국소 중심 식별:
   각 점 $x_i$에 대해, 깊이 기반 유사도에 근거한 $s-1$개의 최근접 이웃들로 구성된 크기 $s$의 이웃 $N_i$가 정의됩니다. 각 이웃 내에서 가장 높은 국소 순위(가장 깊은 점)를 가진 점이 **국소 중심(local center)**으로 식별됩니다.

   • 필터링: 모든 국소 중심이 유용한 것은 아닙니다. 본 방법은 두 가지 기준으로 후보를 필터링합니다: (1) 중심은 반드시 자신의 이웃 내에서 중심적이어야 하며(순위 $\le 2$), (2) 서로 다른 이웃들 사이에서 빈번하게 나타나야 합니다(빈도 $f > 1$). 더욱 견고한 중심을 선택하기 위해 안정성 기준인 **평균 이웃 유도 깊이(Average Neighbor-Induced Depth, AND)**가 사용됩니다.

3. 그룹화 전략:
   필터링된 국소 중심들은 서로 다른 데이터 기하 구조를 처리하기 위해 두 가지 뚜렷한 전략을 사용하여 클러스터로 그룹화됩니다:

   • Min 전략: 상호 이웃 중첩을 기반으로 중심들을 보수적으로 그룹화합니다. 이는 균형 잡히고, 잘 분리되어 있거나, 중첩된 볼록(convex) 클러스터에 적합합니다.
   • Max 전략: 이웃 유사도가 임계값 $\delta$를 초과하는 연결 체인을 통해 중심들을 그룹화합니다. 이 전략은 비볼록 구조와 매우 불균형한 클러스터 크기를 처리하도록 설계되었습니다. 여기에는 고립된 국소 중심을 식별함으로써 "도처에 비볼록한(everywhere non-convex)" 영역(예: 나선형 구조)을 분리하는 메커니즘이 포함됩니다.

4. 클러스터 형성 및 분류:
   국소 중심 그룹이 형성되면, 각 그룹의 고유한 이웃들을 사용하여 **임시 클러스터(temporary clusters)**가 생성됩니다. 점들은 그룹의 중심들과 다른 그룹들과의 유사도에 따라 점수를 부여받습니다. 모호하거나 할당되지 않은 점들은 임시 클러스터 레이블로 학습된 내장 분류기(k-최근접 이웃 또는 랜덤 포레스트)를 사용하여 분류되며, 이를 통해 추가적인 하이퍼파라미터 튜닝 없이 견고한 할당을 보장합니다.

주요 기여

• 새로운 프레임워크: DLCC는 데이터 깊이를 엑셈플러 식별과 유사도 구축의 핵심에 배치하여 다봉성을 직접적으로 해결한 최초의 방법론입니다.
• 효율적 계산: 본 논문은 단순 구현에 비해 계산 속도를 크게 높여, 공간 깊이 하에서 깊이 기반 유사도 행렬을 구축하기 위한 행렬 기반 구현을 개발했습니다.
• 유연한 그룹화: 이중 전략(Min/Max) 접근 방식은 프레임워크가 다양한 클러스터 형태(볼록 vs 비볼록)와 밀도 분포에 적응할 수 있도록 합니다.
• 포괄적 평가: 저자들은 파라미터 선택 가이드라인(CVDD 인덱스 및 시각화 사용)과 광범위한 경험적 평가를 포함한 완전한 엔드 투 엔드 절차를 제공합니다.

실험 결과
저자들은 12개의 합성 데이터셋과 13개의 실제 벤치마크 데이터(고차원 이미지 및 마이크로어레이 데이터 포함)를 통해 DLCC를 평가했습니다.

• 성능: DLCC는 7개의 합성 데이터셋에서 완벽한 복구를 달នូវ했으며, 모든 실제 벤치마크에서 일관되게 상위 3위 안에 들었습니다. 또한 LW-k-means, EKM, R-MDPC, ACLR와 같은 경쟁 모델들과 비교하여 비볼록 형태, 다양한 밀도, 클래스 불균형을 처리하는 데 탁월한 성능을 입증했습니다.
• 관찰된 한계: 본 방법은 국소 이웃이 본질적으로 비볼록한 "매니폴드 형태(manifold-like)" 구조(예: "Atom" 데이터셋 및 "Blend"의 나선형 구조)에서 어려움을 겪었습니다. 이러한 경우, 국소 중심이 근사적으로 볼록한 이웃 내에 존재한다는 가정이 실패했습니다.
• 확장성: 약 $10^4$개의 관측치까지는 효과적이지만, 유사도 행렬 구축을 위한 $O(n^3)$ 복잡도는 매우 큰 규모의 데이터를 처리할 때 병목 현상으로 남습니다.

의의 및 주장
본 논문은 DLCC가 중심 기반 방법론의 경직된 가정과 고차원에서의 밀도 기반 방법론의 불안정성을 극복함으로써 전통적인 클러스터링에 대한 유연한 대안을 제공한다고 주장합니다. 데이터 깊이를 활용하여 국소 기하 구조를 정의함으로써, DLCC는 정해진 클러스터 수나 엄격한 분포 가정이 없는 다양한 시나리오에서 데이터 분석 능력을 향-상시킵니다. 저자들은 DLCC를 특히 클러스터 형태가 복잡하거나 알려지지 않은 경우 탐색적 데이터 분석을 위한 견고한 도구로 위치시키며, 확장성 개선과 파라미터 선택 자동화를 위한 향후 연구가 필요함을 인정하고 있습니다.