SPORE: 밀도-분산 기반의 범용 클러스터링 알고리즘 공개

실용적 조언

고차원 데이터 클러스터링 시 정확한 KNN 대신 HNSW를 사용해도 SPORE의 성능에는 큰 영향이 없으므로 연산 효율을 위해 HNSW를 권장한다.

섹션별 상세

기존 밀도 기반 클러스터링은 클러스터 간 경계가 모호할 때 서로 병합되거나 파편화되는 문제가 있다. SPORE의 1단계(Expansion)는 BFS를 수행하며 밀도-분산 제약 조건을 실시간으로 갱신하여 클러스터의 핵심 '골격(Skeleton)'을 추출한다. Z-점수(z-score) 임계값을 사용하여 밀도가 낮아지는 경계 지점에서 확장을 중단함으로써 인접 클러스터로의 침범을 방지한다. 이를 통해 데이터의 국소적 스케일에 적응하며 형태에 구애받지 않는 초기 클러스터링이 가능하다.

SPORE 알고리즘의 클러스터링 결과 시각화 자료. — Chart다양한 기하학적 구조(비볼록, 고차원 등)에서 SPORE가 어떻게 클러스터를 구분하는지 보여준다. 각 색상은 서로 다른 클러스터로 식별된 데이터 포인트들을 나타낸다.

1단계에서 남겨진 경계 지역의 파편화된 포인트들을 적절한 클러스터에 할당해야 한다. 2단계인 SCR(Small-Cluster Reassignment)은 소규모 클러스터들을 인접한 골격 클러스터로 재할당하며, KNN 분류기와 유사한 방식으로 작동한다. 기하학적 포위도(enclosure)와 KNN 개수 등을 측정하는 점수를 최대화하는 클러스터를 선택하여 날카로운 경계를 획정한다. K-Means의 파티셔닝 특성과 밀도 기반의 유연함을 결합하여 인접한 클러스터 사이에서도 명확한 구분선을 그을 수 있다.

고차원 대용량 데이터에서 KNN 그래프 구축은 계산 비용이 매우 높다. SPORE는 기본적으로 HNSW(Hierarchical Navigable Small World)를 이용한 근사 KNN 그래프 구축을 지원한다. 28개의 데이터셋(2~784차원) 벤치마크 결과, 근사 KNN을 사용해도 정확도 손실 없이 성능을 유지함이 확인됐다. 1000차원 이상의 LLM 임베딩 데이터에서도 깨끗한 클러스터링 결과를 얻을 수 있어 실무 적용성이 높다.

용어 해설

K-최근접 이웃 그래프(k-NN Graph): — 각 데이터 포인트를 노드로 하고 가장 가까운 K개의 이웃을 간선으로 연결한 그래프 구조이다. 데이터의 국소적 기하학적 구조를 캡처하는 데 필수적이며, SPORE에서는 클러스터 확장의 기반이 된다. 고차원 공간에서도 데이터 간의 관계를 효과적으로 유지할 수 있게 한다.
너비 우선 탐색(BFS): — 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. SPORE의 1단계에서 밀도-분산 제약 조건에 따라 클러스터 골격을 성장시키는 핵심 메커니즘으로 활용된다. 이를 통해 데이터 매니폴드를 따라 유연하게 클러스터를 확장할 수 있다.
Z-점수(Z-Score): — 특정 데이터 값이 평균으로부터 표준편차의 몇 배만큼 떨어져 있는지를 나타내는 통계적 척도이다. SPORE에서는 새로운 포인트를 클러스터에 추가할지 결정하는 임계값으로 사용되어 밀도가 급격히 변하는 경계면을 식별한다. 이를 통해 인접한 클러스터로의 무분별한 확장을 방지하는 안전장치 역할을 한다.
계층적 탐색 가능 소세상(HNSW): — 고차원 벡터 검색을 위해 그래프 기반의 계층적 구조를 사용하는 근사 최근접 이웃(ANN) 알고리즘이다. 대규모 데이터셋에서 KNN 그래프를 매우 빠르게 구축할 수 있게 해주며, SPORE의 기본 엔진으로 통합되어 성능을 보장한다. 정확도와 속도 사이의 균형이 뛰어나 실무에서 널리 쓰인다.
비볼록 데이터(Non-Convex Data): — 데이터 분포의 형태가 구형이나 선형이 아닌, 휘어지거나 도넛 모양처럼 복잡한 기하학적 구조를 가진 데이터이다. 전통적인 K-Means는 이러한 구조를 제대로 분리하지 못하지만, SPORE는 밀도 기반 접근법을 통해 복잡한 형태의 클러스터도 정확하게 식별해낸다.

언급된 도구

SPORE추천

General purpose clustering

HNSW추천

Approximate KNN graph construction