🤖 machine learning

Topology-Driven Clustering: Enhancing Performance with Betti Number Filtration

본 논문은 복잡하고 비볼록(nonconvex)하며 서로 얽힌 데이터 구조를 효과적으로 클러스터링하면서 기존의 최첨단 방식들을 능가하는, 국소 비에토리스-립스 필트레이션(local Vietoris-Rips filtrations)에서 유도된 다중 척도 베티 수열(multiscale Betti sequences)을 활용하여 위상 인식 유사도 구조를 구축하는 새로운 위상적 클러스터링 알고리즘인 BFTC를 소개한다.

원저자: Arghya Pratihar, Kushal Bose, Swagatam Das

게시일 2026-07-22

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Arghya Pratihar, Kushal Bose, Swagatam Das

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

다가올 것들의 형상

당신이 뒤섞인 거대한 장난감 더미를 분류하려고 노력하고 있다고 상상해 보세요. 어떤 것은 빨간색 블록이고, 어떤 것은 파란색 공이며, 어떤 것은 초록색 뱀입니다. 만약 당신이 단순히 바닥에 놓인 물체들이 서로 얼마나 가까이 있는지만 본다면, 빨간색 블록이 파란색 공 옆에 우연히 놓여 있다는 이유만으로 두 물체를 같은 그룹으로 묶어버릴 수도 있습니다. 이것이 많은 전통적인 컴퓨터 프로그램이 데이터를 분류하는 방식입니다. 그들은 점들 사이의 직선 거리를 측정합니다. 하지만 만약 "뱀"이 사실 "공"을 휘감고 있는 길고 구불구불한 루프라면 어떻게 될까요? 거리만으로는 그 뱀이 하나의 연결된 형태라는 것을 알 수 없습니다. 그것은 단지 흩어진 점들의 집합으로만 보일 뿐입니다.

이를 해결하기 위해 과학자들은 위상 데이터 분석(Topological Data Analysis, TDA)이라는 분야를 사용합니다. TDA를 점들의 산포도가 아니라 언덕, 계곡, 터널이 있는 풍경을 보는 방법이라고 생각하십시오. 이 분야의 핵심 도구 중 하나인 "지속성 호몰로지(persistent homology)"는 데이터의 다양한 줌 레벨(zoom levels)에서 사진을 찍는 카메라와 같습니다. 줌 아웃을 하면, 어떤 특징(도넛의 구멍이나 뱀의 루프 같은 것)이 계속 보이는지, 그리고 어떤 것이 단순한 노이즈인지 확인할 수 있습니다. 또 다른 핵심 개념인 "베티 수(Betti number)"는 이러한 특징들의 개수를 세는 것입니다. 예를 들어, 분리된 섬은 몇 개인가? 터널은 몇 개인가? 속이 빈 거품은 몇 개인가? 이러한 형상의 개수를 셈으로써, 컴퓨터는 데이터가 뒤틀려 있거나, 엉켜 있거나, 비볼록(non-convex, 즉 단순한 공이나 상자 모양이 아닌 것)하더라도 데이터의 진정한 구조를 이해할 수 있습니다.

논문의 핵심 아이디어: BFTC

이 논문에서 저자들은 베티 수 여과 기반 위상 클러스터링(Betti Number Filtration-based Topological Clustering), 줄여서 BFTC라고 불리는 새로운 방법을 소개합니다. 그들은 기존의 방법들이 이러한 위상학적 아이디어를 사용하려고 시도했지만, 전체 데이터셋을 한꺼번에 보거나 가장 단순한 특징(예: 단순히 섬의 개수만 세는 것)만을 계산함으로써 목표를 달성하지 못했다고 주장합니다. BFTC는 더 똑똑한 접근 방식을 제안합니다. 즉, 마치 특정 동네를 조사하는 탐정처럼 데이터를 국소적으로 관찰하고, 모든 스케일에서 복잡한 형상을 세는 것입니다.

마법이 일어나는 단계는 다음과 같습니다:

이웃 감시 (The Neighborhood Watch): 먼저, 알고리즘은 한 점을 선택하여 그 주변의 이웃들(가장 가까운 $k$ 개의 친구 또는 특정 반경 내의 모든 점)을 살펴봅니다.
줌 렌즈 (Filtration): 이 이웃을 단 한 번만 보는 대신, BFTC는 "여과(filtration)"를 생성합니다. 당신의 이웃 주변에서 풍선을 서서히 부풀린다고 상상해 보십시오. 풍선이 커짐에 따라 멀리 떨어져 있던 점들이 서로 연결됩니다. 이 팽창의 각 단계마다 알고리즘은 임시 형상(Vietoris–Rips 복합체라고 불림)을 구축하고 구멍과 루프의 개수를 셉니다.
위상적 지문 (The Topological Fingerprint): 풍선이 작을 때부터 클 때까지 팽창함에 따라 구멍의 개수는 변합니다. 작은 풍선은 10개의 분리된 섬을 볼 수 있습니다. 중간 크기의 풍선은 이들이 2개의 섬과 1개의 터널로 합쳐지는 것을 볼 수 있습니다. 큰 풍선은 모든 것이 1개의 거대한 섬이 되는 것을 볼 수 있습니다. 이 숫자의 시퀀스를 **베티 시퀀스(Betti sequence)**라고 하며, 이는 해당 특정 이웃의 형상이 어떻게 진화하는지를 설명하는 고유한 지문과 같습니다.
지문 매칭 (Matching Fingerprints): 그런 다음 알고리즘은 이웃한 점들의 베티 시퀀스를 비교합니다. 만약 두 점이 유사한 시퀀스를 가진다면(즉, 줌 아웃할 때 이웃의 진화 방식이 동일하다면), 그들은 물리적으로 가장 가깝지 않더라도 "위상적으로 유사하다"고 간주됩니다.
정리 작업 (Cleaning Up): 알고리즘은 이러한 유사성을 사용하여 지도를 정돈합니다. 위상적 패턴에 맞지 않는 "이상치(outliers)"나 이웃들을 제거하여, 데이터의 진정한 구조를 보여주는 더 깨끗하고 정확한 지도를 만듭니다.
최종 분류 (The Final Sort): 마지막으로, 이 새로운 위상 인식 지도에 표준 수학 기법인 스펙트럴 클러스터링(spectral clustering)을 사용하여 데이터를 클러스터로 그룹화합니다.

연구 결과

저자들은 BFTC를 합성 데이터셋을 포함한 다양한 까다로운 데이터셋에 대해 테스트했습니다. 여기에는 다른 알고리즘을 속이도록 설계된 데이터들이 포함되었습니다:

연결된 토러스 (Linked Tori): 사슬처럼 서로 얽혀 있는 두 개의 도넛(tori).
뒤틀린 형상 (Twisted Shapes): 나선, 원, 구체가 혼합되어 형성된 데이터.
실제 데이터 (Real-World Data): "Zoo"(동물 분류), "Ecoli"(박테리아), "MNIST"(손글씨 숫자)와 같은 데이터셋.

결과는 매우 유망했습니다. 시뮬레이션에서 BFTC는 ToMATo, TPCC, TKM과 같은 기존의 위상학적 접근 방식들을 포함하여 다른 최첨단 방법들을 지속적으로 능가했습니다. 예를 들어, 두 개의 도넛이 엉켜 있는 "Linked Tori" 데이터셋에서 BFTC는 거의 완벽한 점수(ARI 1.00 및 NMI 1.00)를 기록한 반면, 다른 방법들은 서로 얽힌 두 형상을 분리하는 데 어려움을 겪었습니다. 연구진이 데이터에 노이즈(무작위 정적)를 추가했을 때도 BFTC는 견고함을 유지했으며, 이는 BFTC가 지저분한 실제 정보를 잘 처리할 수 있음을 시사합니다.

논문은 또한 서로 다른 설정이 결과에 어떤 영향을 미치는지 탐구했습니다. 그들은 코사인 유사도(베티 시퀀스의 크기뿐만 아니라 방향을 비교하는 것)를 사용하는 것이 표준 거리 측정법보다 더 효과적이라는 것을 발견했습니다. 또한 "이웃"의 크기가 중요하다는 것도 발견했습니다. 이웃이 너무 작으면 큰 그림을 놓치게 되고, 너무 크면 관련 없는 형상들을 연결하게 됩니다. 그러나 이러한 설정들을 조정함으로써, BFTC는 다른 알고리즘들이 놓친 복잡한 구조들을 성공적으로 식별해 냈습니다.

한계점 (아직 해결되지 않은 부분)

이 논문이 주장하지 않는 사항을 명시하는 것도 중요합니다. 저자들은 이 방법이 모든 문제에 대한 마법의 탄환이라고 말하지 않습니다. 그들은 이 방법이 베티 수를 계산하는 것에 의존하며, 이는 매우 거대한 데이터셋에서 고차원 구멍(예: 4D 또는 5D 구멍)을 계산하려고 할 때 계산 비용이 많이 들 수 있다고 명시적으로 지적합니다. 따라서 매우 높은 차원의 경우, 수학적으로 관리가 가능한 낮은 차원(0, 1 또는 2차원)을 유지하는 것이 좋다고 제안합니다.

또한, 논문은 알고리즘이 안정적(데이터의 작은 변화가 결과를 망가뜨리지 않음)임을 수학적으로 증명하지만, 이는 가정에 기반한 이론적 증명입니다. 논문에 제시된 실제 "성과"는 특정 데이터셋에 대한 시뮬레이션과 실험에 근거한 것이지, 우주의 모든 가능한 데이터에 대한 보편적인 보증은 아닙니다. 저자들은 향후 연구가 대규모 데이터셋에 대해 이 방법을 더 빠르게 만드는 것과, 인간의 도움 없이 최적의 설정을 자동으로 선택하는 방법을 탐구하는 데 집중될 수 있다고 제안합니다.

요약하자면, BFTC는 데이터의 진화하는 구멍과 루프를 통해 데이터의 "형상"에 귀를 기울임으로써, 단순히 점들이 서로 얼마나 가까운지를 측정하는 것보다 훨씬 더 잘 복잡하고 엉킨 정보를 분류할 수 있음을 시사합니다.

기술 요약: 베티 수 여과 기반 위상적 클러스터링 (BFTC)

1. 문제 정의

전통적인 클러스터링 알고리즘(예: k-Means, DBSCAN, Spectral Clustering)은 유클리드 거리 또는 커널 기반 유사도 측정에 크게 의존한다. 이러한 방법들은 많은 응용 분야에서 효과적이지만, 비볼록(nonconvex) 형태, 다중 스케일, 또는 뒤엉킨 매니폴드와 같이 복잡한 기하학적 구조를 가진 데이터셋에서는 어려움을 겪는 경우가 많다. 이들은 루프(loop), 보이드(void), 그리고 고차원 연결성과 같은 내재적 위상 특징을 포착하는 데 자주 실패한다.

기존의 위상 데이터 분석(TDA) 접근 방식들은 이러한 간극을 메우려 시도하지만 특정 한계에 직면한다:

ToMATo: 0차원 호몰로지(연결 성분)와 밀도 랜드스케이프에 의존하며, 이는 고차원 위상 정보의 통합 능력을 제한한다.
TPCC: 심플리셜 컴플렉스(simplicial complexes)와 호지 라플라시안(Hodge Laplacians)을 사용하지만, 위상적 특징이 서로 다른 여과 스케일에서 나타나는 영역을 구별하는 데 어려움을 겪을 수 있다.
Topological k-Means (TKM): 지속성 다이어그램(persistence diagrams)을 재생 커널 힐베르트 공간(RKHS)에 임베딩하지만, 국소적인 다중 스케일 위상보다는 전역적인 위상 요약에 집중한다.

본 연구가 다루는 핵심 과제는 전역적인 지속성 요약이나 고정된 위상 스케일에 의존하지 않고, 국소적 기하 근접성과 고차원 위상 구조를 다중 스케일 방식으로 동시에 포착할 수 있는 클러스터링 알고리즘의 필요성이다.

2. 방법론: BFTC 알고리즘

제안된 방법인 **베티 수 여과 기반 위상적 클러스터링(BFTC)**은 다음 단계들을 통해 위상 인식 유사도 구조를 구축한다:

A. 이웃 그래프 구축

알고리즘은 데이터셋 $X$ 에 대한 국소 이웃 그래프를 구축하는 것으로 시작한다. 본 알고리즘은 두 가지 변형을 지원한다:

k-NN BFTC: 균일한 카디널리티와 제어된 희소성을 보장하기 위해 k-최근접 이웃 그래프를 사용한다.
$\epsilon$ -BFTC: 고정된 기하학적 반경에 기반한 $\epsilon$ -이웃 그래프를 사용하여, 메트릭 임계값 구축과 자연스럽게 정렬된다.

B. 국소 Vietoris-Rips 여과 및 베티 수열

각 데이터 포인트 $x_i$ 에 대해, 알고리즘은 해당 데이터의 국소 이웃 $N(x_i) \cup \{x_i\}$ 상에서 일련의 중첩된 Vietoris-Rips (VR) 컴플렉스를 구축한다.

여과 스케일은 임계값 시퀀스 $\epsilon_1, \epsilon_2, \dots, \epsilon_L$ 에 의해 정의된다.
각 스케일에 대해, VR 컴플렉스 $VR(x_i, \epsilon_l)$ 이 형성된다.
베티 수 (Betti Numbers): 알고리즘은 사용자가 지정한 최대 차원 $M$ 까지 베티 수 $\beta_m$ 을 계산한다 (여기서 $M$ 은 반드시 주변 특징 차원이 아닌, 내재적 위상 복잡성을 반영한다).
베티 수열 (Betti Sequences): 각 차원 $m \in [0, M]$ 에 대한 여과 스케일 전반의 베티 수 시퀀스는 베티 수열 $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$ 을 형성한다. 이 시퀀스들은 국소 이웃의 다중 스케일 위상 시그니처 역할을 한다.

C. 위상 인식 유사도 및 그래프 정제

알고리즘은 베티 수열을 비교함으로써 인접한 점들 사이의 위상적 유사도를 정량화한다.

유사도 메트릭: 인접한 점 $x_i$ 와 $x_j$ 의 각 차원 $m$ 에 대한 베티 수열 간의 코사인 유사도가 다음과 같이 계산된다:
$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$
이상치 제거: 임계값 세트 $\alpha_0, \dots, \alpha_M$ 이 적용된다. 이웃 $x_j$ 가 정제된 이웃 $N'(x_i)$ 에 유지되려면 모든 차원 $m$ 에 대해 $(d_{ij})_m \geq \alpha_m$ 을 만족해야 한다. 이 단계는 위상적으로 이질적인 이웃과 이상치를 제거하여, 더 희소하면서도 정보력이 높은 그래프를 생성한다.

D. 스펙트럴 클러스터링 (Spectral Clustering)

정제된 그래프로부터 가우시안 커널을 사용하여 대칭 가중 인접 행렬 $A'$ 를 구축한다. 라플라시안 행렬 $L' = D' - A'$ 를 계산하고, 가장 작은 $p$ 개의 고윳값에 대한 고유벡터에 대해 k-Means를 적용하는 스펙트럴 클러스터링을 수행하여 최종 클러스터를 얻는다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 명시한다:

새로운 알고리즘 (BFTC): 국소 이웃 상에서 Vietoris-Rips 컴플렉스를 구축하고 지정된 차원까지의 베티 수를 평가하는 효율적인 클러스터링 알고리즘을 제안한다. 이는 단순한 연결성( $\beta_0$ )을 넘어 고차원 특징을 포착하기 위해 베티 수열을 활용한다.
복잡한 구조에 대한 효과성: 본 방법은 밑바탕이 되는 위상적 특성을 활용함으로써 복잡하고 뒤엉킨 형태와 구조를 가진 데이터셋을 처리하도록 특별히 설계되었다.
이론적 분석: 논문은 BFTC의 수렴성과 안정성에 관한 광범위한 이론적 토대를 제공한다. 합리적인 기하학적 및 스펙트럴 분리 조건 하에서, 알고-리즘이 구조적으로 안정적임을 입증한다. 즉, 입력 데이터의 작은 섭동(perturbation)이 결과 클러스터링을 변경하지 않는다 (레이블 순열 제외).

4. 실험 결과

저자들은 합성 및 실제 데이터셋에 대해 BFTC(k-NN 및 $\epsilon$ 변형 모두)를 최신 베이스라인(k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM 등)과 비교 평가하였다.

합성 데이터셋: 비볼록 및 뒤엉킨 구조를 가진 데이터셋(예: Linked Tori, 3MC, Smile1, Torus Sphere Line)에서 BFTC는 일관되게 우수한 Adjusted Rand Index (ARI) 및 Normalized Mutual Information (NMI) 점수를 달성했다. 예를 들어, 노이즈( $\rho=0.3$ )가 있는 Linked Tori 데이터셋에서 k-NN BFTC는 0.49의 ARI와 0.56의 NMI를 기록하여, DBSCAN(0.01 ARI) 및 ToMATo(0.17 ARI)와 같은 경쟁 모델을 크게 압도했다.
실제 데이터셋: UCI 데이터셋(Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) 실험에서 BFTC는 거의 모든 경쟁 모델보다 뛰어난 성능을 보였다.
강건성: 가우시안 노이즈 섭동에 대한 안정성을 보여주었다.
절제 연구 (Ablation Studies):
- 이웃 구축: k-NN과 $\epsilon$ -이웃 모두 효과적이었으나, 매우 뒤엉킨 매니폴드의 경우 k-NN이 더 매끄러운 스펙트럴 동작을 제공했다.
- 거리 메트릭: 베티 수열 간의 코사인 유사도가 위상적 관계를 포착하는 데 유클리드 거리보다 훨씬 더 효과적임이 밝혀졌다.
- 커널 함수: 인접 행렬에 가우시안 커널을 포함하는 것이 가중되지 않은 그래프를 사용하는 것보다 성능을 개선했다.

5. 의의 및 주장

본 논문은 BFTC가 다중 스케일 위상 정보를 클러스터링 과정에 직접 통합함으로써 중요한 진전을 이루었다고 주장한다. 전역적인 지속성 요약이나 고정된 스케일에 의존하는 기존 방법들과 달리, BFTC는 베티 수열을 통해 국소적 다중 스케일 위상을 포착한다.

저자들은 이 접근 방식이 다음과 같은 기능을 가능하게 한다고 단언한다:

위상적 특징이 서로 다른 여과 스케일에서 나타나는 매니폴드의 영역을 구별한다.
기하학적 근접성과 고차원 위상 구조(루프, 보이드)를 동시에 포착한다.
전통적인 유클리드 기반 방법들이 실패하는 복잡한 비볼록 및 뒤엉킨 구조의 데이터셋에 대한 강건한 솔루션을 제공한다.

이론적 분석은 이러한 실험적 결과를 뒷받씨며, BFTC가 계산적으로 유한할 뿐만 아니라 구조적으로 안정적임을 입증하여, 클러스터링 파이프라인이 입력 데이터의 작은 섭동에 대해 국소적으로 불변함을 보장한다. 본 연구는 복잡하게 중첩된 대규모 데이터셋을 위한 위상적 측면의 탐구가 향-후 연구를 위한 유망한 방향임을 결론짓는다.