HDBSCAN

통계 수치해석 소프트웨어 마지막 수정: 2026-09-03 04:46:18

1. 개요[편집]

HDBSCAN Hierarchical DBSCAN
제안	Campello · Moulavi · Sander (2013) → Campello 외 (2015, TKDD 확장판)
실질 모수	min_cluster_size (+ 보조적으로 min_samples = k)
없앤 것	DBSCAN 의 전역 반경 ε
내부 구조	상호 도달거리 → MST → 응축 트리 → 안정성 선택
덤으로	소속 확률(soft clustering) · GLOSH 이상 점수
복잡도	이중트리 보루프카로 저차원 대략 O(n log n), 최악 O(n²)

” $\varepsilon$ 을 뭘로 줘야 하나요?”라는 질문을 30년 동안 받은 알고리즘이 있고, 그 질문을 없애 버린 알고리즘이 있다.

HDBSCAN(Hierarchical DBSCAN)은 점마다 다른 국소 밀도를 반영하는 상호 도달거리 위에서 최소 신장 트리를 만들어 모든 밀도 문턱에 대한 군집 계층을 한 번에 구성하고, 그 계층에서 «가장 오래 살아남는» 가지들을 안정성이라는 목적함수로 자동 선택해 평평한 군집화를 뽑아내는 밀도 기반 군집화 알고리즘이다. 사용자가 주는 것은 반경이 아니라 최소 군집 크기뿐이다.

DBSCAN이 남긴 구조적 문제 — 전역 상수 $\varepsilon$ 이라서 밀도가 다른 군집이 공존하면 어느 값을 골라도 한쪽이 깨진다 — 를 푸는 방식이 OPTICS와 갈린다. OPTICS는 모든 $\varepsilon$ 에 대한 결과를 도달거리 그래프로 늘어놓고 사람이 눈으로 자르게 했고, HDBSCAN은 같은 정보를 계층으로 만든 뒤 알고리즘이 자르게 한다. 그 자동 절단이 왜 정당한지, 그리고 그 절단이 어떤 편향을 갖는지가 이 문서의 핵심이다.

이름의 “H”는 계층(hierarchical)이지만, 계보상 더 정확한 조상은 캄펠로의 DBSCAN*다. 경계점 개념을 아예 버리고 핵심점만으로 군집을 정의하는(나머지는 전부 잡음) 변형이며, DBSCAN의 유일한 비결정성이던 경계점 배정 순서 의존성이 여기서 사라진다. HDBSCAN이 만드는 계층은 모든 $\varepsilon$ 에 대한 DBSCAN* 결과를 한 나무에 담은 것이다.¹

2. 상호 도달거리 — 거리를 밀도로 왜곡하기[편집]

먼저 핵심거리(core distance). 점 $x$ 의 $k$ 번째 최근접 이웃까지의 거리를 $c_k(x)$ 라 한다. 이것은 커널 밀도 추정의 $k$ -최근접 이웃 판본과 같은 양이며, $c_k(x)$ 가 작으면 붐비는 곳, 크면 한적한 곳이다. 라이브러리에서 이 $k$ 가 min_samples이고, min_cluster_size와 전혀 다른 모수인데 기본값이 서로 연동되어 있어 자주 혼동된다.

그다음 상호 도달거리(mutual reachability distance).

d_{\text{mreach}}(a,b) = \max\big(c_k(a),\ c_k(b),\ d(a,b)\big)

한적한 곳의 점은 자기 핵심거리 때문에 모든 이웃으로부터 인위적으로 멀어지고, 붐비는 곳의 점들은 원래 거리를 그대로 유지한다. 즉 저밀도 영역의 연결이 선택적으로 비싸진다. 여기에 잡음 한 점이 두 군집 사이에 놓여 다리를 놓는 상황을 넣어 보면 효과가 분명하다 — 잡음점의 핵심거리가 크므로 그 다리의 비용이 크게 부풀고, 계층에서 늦게 붙는다. 단일연결법의 고질병인 연쇄 효과가 거리 정의 단계에서 억제되는 것이 이 변형의 목적이다.

성질 두 개를 알아 둘 만하다. $d_{\text{mreach}}$ 는 대칭이고 삼각부등식을 만족한다(오른쪽 항 셋 중 어느 것이 최대여도 부등식이 성립한다). 그런데 $d_{\text{mreach}}(a,a)=c_k(a)>0$ 이므로 거리 공리 중 자기 거리 0을 위반한다. 그래서 정확히는 거리가 아니지만 삼각부등식에 의존하는 공간 색인 가지치기는 그대로 쓸 수 있고, 이것이 뒤에 나오는 트리 가속의 근거가 된다.

이론적으로 이 구성은 밀도 함수의 준위집합 나무(cluster tree)를 추정하는 절차로 정당화된다. 초두리·다스굽타(2010) 계열의 로버스트 단일연결법 분석이 밀접한 배경이며, 밀도가 매끄러우면 표본이 커질 때 추정 계층이 참 계층에 수렴한다는 종류의 결과가 있다. HDBSCAN의 계층은 임의의 발명품이 아니라 밀도의 위상 구조를 추정한 것이라는 뜻이다.

3. MST 에서 계층으로[편집]

상호 도달거리를 가중치로 갖는 완전 그래프에서 최소 신장 트리를 만든다. 그다음 MST 간선을 가중치 오름차순으로 정렬해 유니온-파인드로 병합하면 정확히 단일연결 계층적 군집화 덴드로그램이 나온다. 여기까지는 “변형 거리 위의 단일연결법”이고 새로운 것이 없다.²

HDBSCAN은 세로축을 뒤집어 쓴다. 병합 거리 $\varepsilon$ 대신

\lambda = \frac{1}{\varepsilon}

를 쓰는데, $\lambda$ 는 밀도 문턱의 눈금이다. $\lambda$ 가 작을 때는(문턱이 낮음) 모든 점이 한 덩어리이고, $\lambda$ 를 키우면(문턱을 높임) 성긴 부분이 먼저 떨어져 나가고 조밀한 핵만 남는다. 각 군집 $C$ 에는 태어난 값 $\lambda_{\text{birth}}$ 가 있고, 각 점 $p$ 에는 자기 군집에서 떨어져 나간 값 $\lambda_p$ 가 있다. 이 $\lambda$ 좌표계가 다음 절 전체의 언어다.

4. 응축 트리[편집]

$n-1$ 번의 병합을 전부 담은 덴드로그램은 사람도 알고리즘도 다루기 벅차다. HDBSCAN은 이것을 위에서 아래로 훑으며 응축 트리(condensed tree)로 압축한다. 규칙은 하나다.

어떤 분기에서 갈라진 두 조각 중, 점 개수가 min_cluster_size보다 적은 조각은 군집이 아니다. 그 조각의 점들은 부모 군집에서 «떨어져 나간» 것으로 기록되고( $\lambda_p$ 를 남기고), 부모 군집은 같은 정체성을 유지한 채 계속 존재한다. 두 조각이 모두 최소 크기를 넘으면 그것이 진짜 분열이며, 부모는 죽고 자식 둘이 태어난다.

이 한 규칙이 두 가지를 동시에 해낸다. 첫째, 잡음점 하나가 떨어지는 것을 “군집이 둘로 쪼개졌다”로 오독하지 않는다 — 단일연결 덴드로그램을 실전에서 못 쓰게 만드는 그 문제다. 둘째, 트리 크기가 $n-1$ 개 내부 노드에서 실제 군집 후보 개수로 줄어든다. 실무 데이터에서 응축 트리는 노드 수십 개 규모라 그림으로 읽을 수 있고, 그 시각화(가지 굵기 = 점 개수, 세로 = $\lambda$ )가 HDBSCAN 사용 경험의 절반을 차지한다.

5. 안정성 — 어느 가지를 뽑을 것인가[편집]

응축 트리는 여전히 계층이다. 평평한 군집화를 얻으려면 서로 겹치지 않는 노드 집합을 골라야 하는데, 그 선택 기준이 안정성(stability) 또는 초과 질량(excess of mass)이다.

S(C) = \sum_{p\in C}\big(\lambda_p - \lambda_{\text{birth}}(C)\big)

각 점이 그 군집 안에서 얼마나 오래 버텼는지를 $\lambda$ 축에서 재어 전부 더한 값이다. 밀도 문턱을 넓은 범위로 올려도 구성원이 그대로 남아 있는 군집이 큰 값을 받는다. 직관적으로 ” $\varepsilon$ 을 어떻게 흔들어도 계속 보이는 덩어리”에 점수를 주는 것이고, 그것은 DBSCAN 문서가 마지막에 권했던 안정성 진단을 목적함수로 승격시킨 것에 가깝다.

선택은 잎에서 뿌리로 올라가는 한 번의 순회로 끝난다.

잎 노드는 전부 선택 상태로 시작한다.
내부 노드 $C$ 에서 자식들의 (전파된) 안정성 합 $\sum S(C_i)$ 와 자기 $S(C)$ 를 비교한다.
자식 합이 크면 자식들을 유지하고 $C$ 의 안정성을 그 합으로 덮어써서 위로 전달한다.
자기 값이 크면 $C$ 를 선택하고 후손 전부를 버린다.

이 탐욕적 한 번의 순회가 “겹치지 않는 노드 집합의 총 안정성 최대화”라는 조합 문제의 정확한 최적해를 준다는 것이 캄펠로 외의 논지다. 트리 구조 위의 동적계획법이라 상향 전파가 최적성을 보존하기 때문이다. 뿌리는 선택 후보에서 제외되고(전체를 한 군집으로 부르는 것은 정보가 없다), 선택되지 못한 점은 잡음이 된다.

결과의 성격을 하나 짚어야 한다. 안정성은 큰 군집에 유리하다. $S(C)$ 가 점 개수에 대한 합이므로 점이 많은 가지가 유리하고, 큰 성긴 군집 안에 작은 조밀한 군집이 들어 있으면 부모가 자식들을 삼키는 일이 생긴다. 라이브러리가 제공하는 cluster_selection_method='leaf'는 이 편향을 우회해 항상 잎 노드를 뽑는 대안이고, 실제로 “군집이 너무 크게 뭉쳐 나온다”는 증상의 표준 처방이다. 나중에 추가된 cluster_selection_epsilon(말처·바움, 2020)은 “이 거리보다 가까운 것은 쪼개지 말라”는 하한을 걸어 DBSCAN식 물리적 스케일 지식을 다시 주입하는 하이브리드다.

6. 모수가 하나로 줄어드는 이유[편집]

$\varepsilon$ 이 사라진 자리에 남는 것은 두 개, 실질적으로는 하나다.

모수	역할	민감도
`min_cluster_size`	이보다 작은 덩어리는 군집으로 인정하지 않음	결과를 직접 결정
`min_samples` ( $=k$ )	핵심거리 계산에 쓰는 이웃 수 = 보수성	잡음 비율을 조절

min_cluster_size는 개수라서 사람이 도메인 지식으로 정할 수 있다. “10개 미만짜리 덩어리는 어차피 보고서에 안 쓴다”는 판단이 그대로 입력이 된다. $\varepsilon$ 처럼 데이터 스케일·단위·차원에 얽힌 양이 아니라는 것이 결정적인 차이다. min_samples는 키우면 핵심거리가 전반적으로 커져 더 많은 점이 잡음으로 판정되고, 계층이 보수적으로 변한다. 대표 구현이 이 값의 기본을 min_cluster_size와 같게 두기 때문에 명목상 손잡이가 하나가 된다.

여기서 정직하게 인정할 것 — 모수가 사라진 게 아니라 사람이 잘 정할 수 있는 형태로 바뀐 것이다. min_cluster_size를 5에서 50으로 바꾸면 결과는 당연히 달라진다. DBSCAN에서 $k$ -거리 그래프의 무릎을 찾아 $\varepsilon$ 을 추측하던 절차를 개수 하나로 대체했다는 것이 실질적 성과이고, 그것만으로도 충분히 크다.

7. GLOSH 와 소프트 군집화[편집]

계층을 손에 들고 있으면 부가 산출물이 공짜로 나온다.

GLOSH(Global-Local Outlier Score from Hierarchies)³는 점 $p$ 의 이상 점수를 자기 군집이 도달한 최대 밀도와 자신이 떨어진 밀도의 비로 정의한다.

\mathrm{GLOSH}(p) = 1 - \frac{\lambda_p}{\lambda_{\max}(C_p)}

$\lambda_{\max}(C_p)$ 는 $p$ 가 속한 군집(또는 그 후손)이 도달한 가장 높은 밀도 문턱이다. 자기 군집이 훨씬 조밀해질 때까지 버티지 못하고 일찍 떨어진 점이 높은 점수를 받는다. 값이 $[0,1)$ 이고 국소 밀도로 정규화되어 있어서 밀도가 다른 영역을 함께 비교할 수 있다는 점이 이상치 탐지의 LOF와 같은 계열의 발상이며, 군집화를 돌린 부산물로 얻어진다는 것이 이득이다.

소프트 군집화는 각 점에 대해 군집별 소속 벡터를 준다. 계산은 두 성분의 조합이다 — 군집 «중심»격 점(밀도가 가장 높은 지점)까지의 거리 기반 성분, 그리고 그 군집에 얼마나 오래 남아 있었는지를 $\lambda$ 로 재는 성분. 가우시안 혼합 모형의 사후 확률처럼 확률 모형에서 유도된 양이 아니므로 «확률»이라 부르기엔 무리가 있고, 군집 경계에 걸친 점을 식별하는 진단 도구로 보는 편이 정확하다.

또 하나. 계층을 $\lambda=1/\varepsilon$ 에서 수평으로 자르면 그 $\varepsilon$ 에 대한 DBSCAN* 군집화가 그대로 나온다. HDBSCAN 한 번을 돌려 두면 어떤 $\varepsilon$ 에 대한 DBSCAN* 결과든 재계산 없이 뽑을 수 있고, 라이브러리도 그 기능을 노출한다. OPTICS가 도달거리 그래프로 하던 일이 여기서는 계층 절단으로 대체된다.

8. 복잡도와 구현[편집]

병목은 두 곳이다. 핵심거리를 위한 $k$ -최근접 이웃 질의 $n$ 번, 그리고 상호 도달거리 그래프의 MST. 완전 그래프의 간선이 $O(n^2)$ 개라 소박하게 하면 $O(n^2)$ 이 하한이고, 실제로 초기 구현은 그랬다.

가속의 핵심은 간선을 모두 만들지 않고 MST를 구성하는 것이다. KD-트리나 볼 트리로 점을 색인한 뒤 이중트리 보루프카(dual-tree Borůvka, March·Ram·Gray, 2010)를 돌린다. 보루프카 알고리즘은 매 라운드마다 모든 성분에 대해 «성분 밖으로 나가는 최소 간선»을 동시에 찾는데, 이 질의가 공간 색인 위의 최근접 이웃 탐색과 같은 모양이라 가지치기가 먹힌다. 라운드가 $O(\log n)$ 번이므로 저차원에서 전체가 대략 $O(n\log n)$ 으로 떨어진다. 상호 도달거리가 삼각부등식을 만족한다는 앞의 성질이 여기서 정확히 쓰인다.

한계도 같은 자리에서 온다.

차원이 오르면 색인이 무너진다. 10~15차원을 넘어가면 가지치기가 거의 작동하지 않아 사실상 $O(n^2)$ 이 되고, 게다가 거리 집중 때문에 핵심거리 자체의 의미가 흐려진다. 차원의 저주는 DBSCAN과 똑같이 온다.
메모리는 $O(n)$ 이 유지된다. MST 간선이 $n-1$ 개이고 거리 행렬을 만들지 않으므로, 거리 행렬을 미리 계산하는 구현만 피하면 대규모에서도 메모리는 문제가 아니다.
증분·스트리밍이 아니다. 계층 전체가 전역 구조라서 점 하나 추가에 재계산이 필요하다. 새 점을 기존 계층에 «끼워 넣어» 라벨만 예측하는 근사 예측 기능이 따로 제공되지만, 계층 자체는 갱신되지 않는다.

9. DBSCAN 과 무엇이 달라지나[편집]

항목	DBSCAN	HDBSCAN
주는 모수	$\varepsilon$ , minPts	min_cluster_size (+ min_samples)
밀도 문턱	전역 상수 하나	군집마다 다른 값이 선택됨
밀도 차이	한쪽이 반드시 깨짐	동시에 채택 가능
경계점	존재, 순서 의존	없음 (DBSCAN* 의미) → 결정론적
잡음 비율	보통 낮음	보통 더 높음
출력	라벨 + 잡음	라벨 + 잡음 + 소속도 + GLOSH
계층 정보	없음	응축 트리 전체
저차원 비용	범위질의 $n$ 번	$k$ -NN + MST, 대략 $O(n\log n)$
물리적 스케일 주입	$\varepsilon$ 로 직접	cluster_selection_epsilon 으로 간접

마지막 행이 DBSCAN이 안 죽는 이유다. “5 m 이내면 같은 장애물”처럼 $\varepsilon$ 이 도메인에서 오는 문제라면 자동 선택은 도움이 아니라 방해다. 반대로 “이 데이터에 구조가 있는지 모르겠다”에서 출발하는 탐색적 분석에서는 HDBSCAN이 거의 항상 낫다.

10. 실전 사용[편집]

차원 축소 뒤 군집화가 사실상 표준 파이프라인이다. 단일세포 전사체, 문서 임베딩, 이미지 임베딩에서 UMAP이나 t-SNE로 2~10차원으로 줄인 뒤 HDBSCAN을 거는 조합이 널리 쓰인다. 토픽 모형 계열 도구가 이 조합을 내부에 박아 놓은 사례도 있다. 다만 비선형 차원 축소가 밀도를 왜곡한다는 점은 정직하게 인식해야 한다 — 축소 후 공간의 «밀도»는 원 공간의 밀도가 아니고, 군집의 통계적 의미는 그만큼 약해진다.
천체 카탈로그. 위치·고유운동·시차를 좌표로 놓고 성단·이동성군을 찾는 데 널리 쓰인다. 배경 별이 압도적으로 많고 성단마다 밀도가 다른 데이터라 HDBSCAN의 홈그라운드다.
점군과 궤적. 라이다 점군의 물체 분할, GPS 체류지점 추출 등 DBSCAN의 전통적 무대에서도 밀도가 거리에 따라 달라지는 경우(라이다는 멀어질수록 성기다)에는 HDBSCAN이 유리하다.
이상치 순위 매기기. 군집화가 목적이 아니고 GLOSH만 쓰는 용법도 흔하다.

11. 쓰기 전에 확인할 것[편집]

표준화했는가. 밀도 기반 방법 전체에 해당하는 1번 항목이다.
잡음 비율이 이상하지 않은가. 60%가 잡음이면 min_samples를 낮추거나 min_cluster_size를 줄여 본다. DBSCAN보다 잡음이 많이 나오는 것은 정상이지만 과반은 신호다.
군집이 너무 크게 뭉쳤는가. 안정성 선택의 큰 군집 편향이다. leaf 선택으로 바꿔 응축 트리의 잎을 직접 본다.
응축 트리를 그려 봤는가. HDBSCAN을 라벨 벡터만 받아 쓰는 것은 절반만 쓰는 것이다. 가지가 두꺼운데 짧으면 그 군집은 «있긴 있지만 곧 부서지는» 구조다.
차원이 몇인가. 20차원 원 공간에 그대로 걸었다면 결과를 신뢰하기 전에 축소를 검토한다.
결과가 재현되는가. 경계점이 없으므로 라벨은 결정론적이지만, 근사 최근접 이웃 색인을 쓰거나 차원 축소를 앞에 붙이면 그 단계의 난수가 전부 흘러들어온다. “HDBSCAN은 결정론적”이라는 문장이 파이프라인 전체에 대한 보장은 아니다.⁴

12. 관련 문서[편집]

DBSCAN* 라는 이름에 붙은 별표는 R*-트리처럼 «개선판»을 뜻하는 관례를 따른 것인데, 하필 검색 엔진과 정규표현식이 별표를 싫어해서 문헌 검색이 유난히 불편한 이름이 되었다. 논문에서도 그냥 “HDBSCAN*“라고 별표를 붙여 쓰는 판본과 안 붙이는 판본이 섞여 있다. ↩
MST 위에서 간선을 긴 것부터 잘라 내려가는 것이 단일연결법과 같다는 사실은 1969년 고워·로스가 정리했고, 그래서 «단일연결법을 빠르게 하려면 MST를 구하라»는 것이 반세기 된 상식이다. HDBSCAN이 새로 한 일은 알고리즘 발명이 아니라 어떤 거리 위에서 그것을 하고 결과를 어떻게 읽을지를 정한 것이다. ↩
GLOSH의 “Global-Local”이라는 작명은 국소 밀도로 정규화하면서도 계층 전체(전역)를 참조한다는 뜻이다. 이름이 길고 억지스러운 것은 이 계열 알고리즘의 전통에 충실한 결과다 — 애초에 DBSCAN이라는 이름부터 그랬다. ↩
실제로 “같은 코드인데 군집 수가 다르다”는 제보의 대부분이 앞단 UMAP의 시드 문제다. HDBSCAN 자체를 의심하기 전에 파이프라인의 난수 소스를 전부 고정하고 다시 돌려 보는 것이 순서다. 그러고도 결과가 흔들린다면 그건 알고리즘 문제가 아니라 데이터에 안정적인 군집 구조가 없다는 정보다. ↩