DBSCAN

1. 개요[편집]

DBSCAN Density-Based Spatial Clustering of Applications with Noise
제안	Ester · Kriegel · Sander · Xu (1996, KDD)
모수	이웃 반경 ε · 최소 이웃 수 minPts
안 주는 것	군집 개수 k (알고리즘이 정한다)
주는 것	임의 형상 군집 + 잡음 라벨
비용	범위질의 n번 — 최악 O(n²), 색인이 먹히면 O(n log n)
수상	2014 SIGKDD Test of Time Award

군집이 몇 개인지 모르겠고, 모양도 동그랗지 않을 것 같고, 쓰레기 데이터가 섞여 있다. 이 세 줄이 전부 맞으면 DBSCAN이다.

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 군집을 “밀도가 충분히 높은 점들이 서로 이어져 만드는 최대 연결 덩어리”로 정의하고, 그 덩어리에 속하지 못한 점을 잡음으로 명시적으로 남겨 두는 밀도 기반 군집화 알고리즘이다. 필요한 것은 반경 $\varepsilon$ 과 최소 이웃 수 $\mathrm{minPts}$ 두 개뿐이고, 군집 개수는 입력이 아니라 출력이다.

k-평균 군집화가 “중심에서 가까운 점들”로 군집을 정의하는 바람에 볼록한 덩어리밖에 못 찾고 모든 점을 어딘가에 억지로 배정하는 반면, DBSCAN은 정의 자체를 국소 밀도로 바꿔서 초승달·나선·동심원 같은 형상을 그대로 찾아내고 이상치는 이상치라고 말한다. 1996년 KDD 논문이 2014년 Test of Time Award를 받았고, 30년 가까이 지난 지금도 공간 데이터 군집화의 기본값 자리를 지키고 있다. 이유는 성능이 아니라 정의가 정직해서다 — 군집이 없는 곳에서는 군집이 없다고 말한다.¹

2. 밀도의 정의 — 점 세 종류[편집]

기호부터. 점 $p$ 의 $\varepsilon$-이웃은 $N_\varepsilon(p) = \{q \in D : \mathrm{dist}(p,q) \le \varepsilon\}$ 이고, $p$ 자신을 포함한다(원논문 정의가 그렇다. 라이브러리마다 $\mathrm{minPts}$ 를 세는 관례가 미묘하게 달라서 이걸 놓치면 결과가 한 칸씩 밀린다).

• 핵심점(core point): $|N_\varepsilon(p)| \ge \mathrm{minPts}$. 자기 주변이 충분히 붐비는 점.
• 경계점(border point): 핵심점은 아니지만 어떤 핵심점의 $\varepsilon$-이웃 안에 있는 점. 군집의 가장자리.
• 잡음점(noise point): 둘 다 아닌 점. 어디에도 소속되지 않는다.

$\varepsilon$ 과 $\mathrm{minPts}$ 가 함께 정하는 것은 결국 밀도 문턱 $\mathrm{minPts}/(\text{반경 }\varepsilon\text{ 공의 부피})$ 하나다. 이 문턱을 넘으면 군집의 몸통, 못 넘으면 가장자리나 잡음. 그래서 DBSCAN은 커널 밀도 추정의 균등 커널 판본에 수평 절단을 넣은 것으로 읽어도 무리가 없다 — 밀도 함수의 상위 준위집합(superlevel set)의 연결성분을 찾는 것이 DBSCAN이 하는 일이다.

3. 도달가능성과 연결성[편집]

군집을 정의하려면 “이어져 있다”를 정확히 해야 한다. 원논문은 세 단계로 쌓아 올린다.

1. 직접 밀도-도달가능: $q \in N_\varepsilon(p)$ 이고 $p$ 가 핵심점이면, $q$ 는 $p$ 로부터 직접 밀도-도달가능하다.
2. 밀도-도달가능: 위 관계를 이어 붙인 사슬 $p = p_1, p_2, \dots, p_m = q$ 가 존재하면 도달가능.
3. 밀도-연결: 어떤 점 $o$ 가 있어서 $p$ 와 $q$ 가 둘 다 $o$ 로부터 도달가능하면 둘은 밀도-연결이다.

그리고 군집이란 밀도-연결 관계에 대해 극대인 집합이다. 여기서 놓치기 쉬운 비대칭이 하나 있다. 밀도-도달가능은 대칭이 아니다. 경계점 $q$ 는 핵심점 $p$ 로부터 도달가능하지만, $q$ 는 핵심점이 아니므로 $q$ 에서 $p$ 로는 갈 수 없다. 대칭성을 회복하려고 중간 점 $o$ 를 끼워 넣은 것이 3단계의 밀도-연결이고, 이 한 겹이 있어야 군집이 동치류로 잘 정의된다.

이 비대칭의 대가가 DBSCAN의 유일한 비결정성이다. 한 경계점이 서로 다른 두 군집의 핵심점 이웃 안에 동시에 들어갈 수 있고, 그러면 먼저 처리된 군집이 가져간다. 즉 결과가 점의 처리 순서에 의존한다 — 핵심점의 소속만은 순서와 무관하지만 경계점은 그렇지 않다.² 캄펠로의 DBSCAN*는 아예 경계점 개념을 없애고 핵심점만으로 군집을 정의해(나머지는 전부 잡음) 완전 결정론적으로 만들었고, HDBSCAN의 이론적 기반이 이쪽이다.

극단값 하나는 알아 둘 만하다. $\mathrm{minPts}=2$ 로 두면 DBSCAN은 정확히 계층적 군집화의 단일연결법을 높이 $\varepsilon$ 에서 자른 것과 같다. 모든 점이 이웃만 하나 있으면 핵심점이 되므로, 군집이 $\varepsilon$-근접 그래프의 연결성분이 되기 때문이다. $\mathrm{minPts}$ 를 키운다는 것은 그 그래프를 만들기 전에 희박한 지역의 점을 먼저 솎아낸다는 뜻이고, 단일연결법의 고질병인 연쇄 효과(chaining)를 막는 장치가 바로 그것이다.

4. 알고리즘과 진짜 비용[편집]

구현은 놀랄 만큼 짧다.

1. 아직 방문하지 않은 점 $p$ 를 하나 집어 $N_\varepsilon(p)$ 를 질의한다.
2. 핵심점이 아니면 일단 잡음으로 표시하고 다음 점으로(나중에 다른 군집의 경계점으로 승격될 수 있다).
3. 핵심점이면 새 군집을 열고, $N_\varepsilon(p)$ 를 씨앗 큐에 넣는다.
4. 큐에서 점을 꺼내 미배정이면 현재 군집에 넣고, 그 점도 핵심점이면 그 이웃들을 큐에 추가한다. 큐가 빌 때까지 반복.

본질은 $\varepsilon$-근접 그래프 위의 너비우선 탐색이고, 각 점에 대해 범위질의를 정확히 한 번씩 한다. 여기서 유명한 오해가 하나 시작된다.

원논문은 R*-트리 같은 공간 색인을 쓰면 범위질의가 $O(\log n)$ 이라 전체가 $O(n\log n)$ 이라고 적었다. 이건 조건부로만 참이다. 슈베르트 외(2017)가 정리한 바에 따르면, 알고리즘의 실제 비용은 “범위질의 $n$ 번”이고 그 질의들이 반환하는 점의 총 개수가 곧 하한이다. $\varepsilon$ 이 커서 이웃이 평균 $O(n)$ 개면 색인이 아무리 좋아도 $\Theta(n^2)$ 이다. 색인 자체도 차원이 올라가면 무너져서, 10차원만 넘어가도 KD-트리나 볼 트리의 가지치기가 거의 작동하지 않고 사실상 전수 탐색이 된다. 간·타오(2015)는 한 걸음 더 나아가 $d \ge 3$ 에서 정확한 DBSCAN을 $O(n^{4/3})$ 보다 빨리 푸는 것은 홉크로프트 문제 수준의 돌파 없이는 불가능함을 보였고, 대신 $\rho$-근사 판본으로 기대 선형 시간을 제시했다.

실무 정리는 이렇다.

• 저차원($d \lesssim 10$)에 $\varepsilon$ 이 적당히 작으면 색인이 잘 먹혀 실제로 준선형에 가깝게 돈다. 이게 DBSCAN이 GIS·점군에서 사랑받는 이유다.
• 고차원이면 색인이 무의미해질 뿐 아니라 거리 집중 현상 때문에 $\varepsilon$ 이라는 개념 자체가 흔들린다. 차원의 저주 문서가 다루는 그 문제이며, 먼저 주성분 분석이나 다차원 척도법으로 차원을 줄이는 것이 표준 처방이다.
• 거리 행렬 $n\times n$ 을 미리 계산하지 마라. 많은 튜토리얼이 그렇게 하는데 메모리가 $O(n^2)$ 로 튀어 DBSCAN의 최대 장점(메모리 $O(n)$)을 스스로 버리는 짓이다. 대규모라면 근사 최근접 이웃 색인으로 범위질의를 근사하는 편이 낫다.

5. ε 와 minPts 고르기[편집]

두 모수 중 $\mathrm{minPts}$ 가 덜 예민하고 $\varepsilon$ 이 훨씬 예민하다. 그래서 순서는 정해져 있다 — $\mathrm{minPts}$ 를 먼저 고정하고, 그다음 $\varepsilon$ 을 데이터에게 물어본다.

$\mathrm{minPts}$ 의 관례적 출발점은 $\mathrm{minPts} \ge d+1$ 이고, 잡음이 많거나 데이터가 크면 $\mathrm{minPts} = 2d$ 를 권한다(잔더 외, 1998). 2를 쓰면 앞서 본 대로 단일연결법이 되어 연쇄 효과에 그대로 노출되므로 실전에서는 피한다. 값을 키우면 군집이 더 보수적으로 잡히고 잡음 판정이 늘어난다.

$\varepsilon$ 은 $k$-거리 그래프로 고른다. 모든 점에 대해 $k$ 번째 최근접 이웃까지의 거리($k = \mathrm{minPts}-1$, 자기 자신을 세는 관례면 $\mathrm{minPts}$)를 구해 내림차순으로 정렬해 그린다. 군집 안쪽 점들은 이 값이 작고 고르게 낮은 평지를 이루고, 잡음점들은 값이 커서 왼쪽 끝에서 급격히 치솟는다. 그 사이 무릎(knee) 이 밀도 문턱의 자연스러운 후보다.

$$k\text{-dist}(p) = \big\lVert p - \mathrm{NN}_k(p) \big\rVert$$

여기서 $\mathrm{NN}_k(p)$ 는 $p$ 의 $k$ 번째 최근접 이웃이다. 무릎이 뚜렷하면 그 데이터에는 밀도가 뚜렷이 다른 두 체제(군집/잡음)가 있다는 뜻이고, DBSCAN이 잘 맞는 데이터다. 무릎이 안 보이면 그것 자체가 진단이다 — 밀도가 연속적으로 변하고 있으니 단일 $\varepsilon$ 으로는 못 자른다는 신호이고, 다음 절의 OPTICS/HDBSCAN으로 넘어가야 한다.

거리 척도와 스케일링이 $\varepsilon$ 만큼이나 중요하다는 것도 잊기 쉽다. 위도·경도와 속도를 같은 유클리드 거리에 던지면 단위가 큰 축이 $\varepsilon$ 을 독점한다. 표준화는 선택이 아니고, 위경도라면 아예 하버사인 거리를 쓰는 것이 맞다.

6. 밀도가 다르면 깨진다[편집]

DBSCAN의 구조적 한계는 딱 하나로 요약된다. $\varepsilon$ 이 전역 상수다. 조밀한 군집과 성긴 군집이 한 데이터에 공존하면 어떤 $\varepsilon$ 을 골라도 한쪽이 망가진다.

• $\varepsilon$ 을 작게 → 조밀한 군집은 잘 잡히지만 성긴 군집이 통째로 잡음이 된다.
• $\varepsilon$ 을 크게 → 성긴 군집은 살아나지만 조밀한 군집들이 서로 붙어 하나로 병합된다.

밀도가 계단식으로 변하는 실제 데이터(도심과 교외의 GPS 로그, 은하단과 필라멘트, 응집과 확산이 공존하는 입자계)에서는 이게 예외가 아니라 기본값이다. 두 후속 알고리즘이 각각 다른 방식으로 이 문제를 푼다.

OPTICS(안케르스트 외, 1999)는 평평한 군집을 아예 내놓지 않는다. 대신 점들을 하나의 순서로 배열하면서 각 점의 도달거리를 기록한 도달거리 그래프를 출력한다. 골짜기 하나가 군집 하나이고, 골짜기 안에 더 깊은 골짜기가 있으면 그것이 하위 군집이다. 이 그래프를 높이 $\varepsilon'$ 에서 수평으로 자르면 그 $\varepsilon'$ 로 DBSCAN을 돌린 결과가 그대로 나온다. 즉 OPTICS는 “모든 $\varepsilon$ 에 대한 DBSCAN을 한 번에 계산해 둔 것”에 가깝고, 사람이 그림을 보고 자르는 지점을 고르게 한다.³

HDBSCAN(캄펠로 외, 2013)은 여기에 자동 선택을 얹는다. 핵심은 거리 자체를 바꾸는 것이다. $k$-번째 이웃까지의 거리를 핵심거리 $c_k$ 라 할 때 상호 도달거리

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

를 정의하면, 성긴 지역의 점들은 서로 인위적으로 멀어지고 조밀한 지역은 원래 거리를 유지한다. 이 변형 거리 위에서 최소 신장 트리를 만들고 간선을 긴 것부터 잘라 내려가면 군집 계층이 나오는데, 여기까지는 결국 변형 거리 위의 단일연결법이다. HDBSCAN의 진짜 기여는 그 계층에서 어떤 가지를 채택할지를 안정성(stability)이라는 목적함수로 자동 선택한다는 점이다. 오래 살아남는 가지를 고르므로 밀도가 다른 군집이 각자 다른 높이에서 동시에 채택될 수 있다. 사용자가 주는 것은 $\varepsilon$ 이 아니라 최소 군집 크기라서 훨씬 직관적이고, 덤으로 소속 확률과 이상 점수(GLOSH)까지 나온다.

세 알고리즘의 관계를 한 줄로 요약하면 이렇다. DBSCAN → (모든 $\varepsilon$ 을 한 번에 계산) → OPTICS → (계층 + 안정성 기반 자동 선택) → HDBSCAN.

그래서 요즘 “일단 DBSCAN”이라고 말할 때 실제로 손이 가는 것은 HDBSCAN 구현인 경우가 많다. 그럼에도 DBSCAN이 안 죽는 이유는 (1) 개념이 단순해 결과를 설명하기 쉽고, (2) $\varepsilon$ 이 물리적 의미를 갖는 문제(예: “5 m 이내면 같은 장애물”)에서는 오히려 자동 선택이 방해가 되기 때문이다.

7. k-평균과의 대비[편집]

항목	k-평균 군집화	DBSCAN
군집 개수	사람이 $k$ 를 준다	알고리즘이 정한다
군집 모양	볼록 다면체(보로노이 셀)	임의 형상
이상치 처리	전부 어딘가에 배정	잡음으로 분리
주는 모수	$k$	$\varepsilon$, $\mathrm{minPts}$
결정성	초기화에 의존	경계점만 순서 의존
밀도 차이	큰 군집이 작은 군집을 잠식	전역 $\varepsilon$ 때문에 한쪽이 깨짐
비용	반복당 $O(nkd)$	범위질의 $n$ 번
고차원	열화되지만 돌긴 함	거리 집중으로 사실상 붕괴

”$k$ 를 안 줘도 된다”가 공짜처럼 들리지만, 실제로는 $k$ 를 정하는 어려움이 $\varepsilon$ 을 정하는 어려움으로 옮겨 갔을 뿐이다. 차이는 $\varepsilon$ 이 데이터의 물리적 스케일과 직접 연결된 양이라 $k$ 보다 현장 지식으로 정하기 쉽다는 것, 그리고 $k$-거리 그래프처럼 데이터에게 물어보는 절차가 존재한다는 것이다. 반면 밀도가 균일하고 덩어리가 동그란 데이터라면 k-평균이 더 빠르고 더 안정적이다. 한쪽이 다른 쪽의 상위호환이 아니다.

8. 어디에 쓰이나[편집]

• 점군 분할. 라이다 점군에서 지면을 제거한 뒤 남은 점을 DBSCAN으로 묶으면 차량·보행자·기둥 같은 물체 후보가 나온다. SLAM과 자율주행 인지 파이프라인에서 가장 흔한 용례이고, $\varepsilon$ 이 “물체 간 최소 간격”이라는 물리적 의미를 갖는 대표적 자리다.
• 천체물리의 FoF. 우주론 시뮬레이션에서 헤일로를 찾는 friends-of-friends 알고리즘은 연결길이 $b$ 안의 입자를 전부 이어 붙이는 것으로, $\mathrm{minPts}=2$ 인 DBSCAN과 정확히 같다. 두 분야가 서로 모른 채 같은 알고리즘을 각자 발명한 사례다.
• 분자동역학 후처리. 응집체·미셀·기포·클러스터의 개수와 크기 분포를 궤적에서 뽑을 때 원자 좌표에 DBSCAN을 건다. 컷오프 반경이라는 개념이 이미 있는 분야라 $\varepsilon$ 을 고르는 데 저항이 없다.
• 이상치 탐지. 잡음 라벨을 그대로 이상 점수로 쓴다. 다만 이진 판정만 주므로 순위가 필요하면 이상치 탐지 쪽의 LOF나 고립 숲이 낫다. LOF가 DBSCAN과 같은 연구 그룹에서 나온 것도 우연이 아니다.
• 궤적·이벤트 군집화. GPS 로그에서 체류 지점 추출, 지진 여진의 시공간 군집, 콜센터 로그의 이상 구간 등. 시간축을 하나의 좌표로 넣되 스케일을 맞추는 것이 관건이다.

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

• 표준화했는가. 안 했으면 결과는 단위가 큰 축의 함수일 뿐이다.
• $k$-거리 그래프를 그렸는가. 무릎이 없으면 DBSCAN이 아니라 HDBSCAN으로 가라는 신호다.
• 차원이 몇인가. 15차원 이상이면 결과를 신뢰하기 전에 먼저 차원 축소를 고민해야 한다.
• 잡음 비율이 합리적인가. 90%가 잡음으로 나왔다면 $\varepsilon$ 이 너무 작거나 $\mathrm{minPts}$ 가 너무 크다. 반대로 전부 한 군집이면 $\varepsilon$ 이 너무 크다. 이 두 실패 모드가 전체의 대부분이다.
• 군집 개수가 안정적인가. $\varepsilon$ 을 ±20% 흔들었을 때 군집 개수가 3에서 27로 뛴다면, 그 결과를 보고서에 넣기 전에 다시 생각하는 게 좋다.⁴

10. 관련 문서[편집]

• k-평균 군집화 · 계층적 군집화 · 스펙트럴 군집화 · 가우시안 혼합 모형
• 커널 밀도 추정 · 이상치 탐지
• KD-트리 · 쿼드트리 · 옥트리 · 최근접 이웃 탐색
• 최소 신장 트리 · 보로노이 다이어그램
• 차원의 저주 · 주성분 분석 · 다차원 척도법
• SLAM · 분자동역학 · 점군 정합

11. Footnotes[편집]

1. 이름이 길고 억지스러운 이유가 있다. 저자들이 나중에 회고하기를, 당시 공간 데이터베이스 학계에서 “applications with noise”를 다룬다는 점을 제목에 박아 두는 것이 심사에 유리했다고 한다. 덕분에 30년째 아무도 풀네임을 외우지 못한다. ↩

2. 경계점의 순서 의존성은 보통 실무에서 무시되지만, “같은 데이터에 같은 코드를 돌렸는데 라벨이 다르다”는 재현성 이슈로 튀어나올 때가 있다. 대개 병렬 구현이나 입력 정렬 순서가 바뀐 경우다. 결과를 비교할 때는 라벨 자체가 아니라 조정 랜드 지수 같은 순열 불변 척도를 쓰는 것이 안전하다. ↩

3. OPTICS의 도달거리 그래프를 사람이 눈으로 잘라야 한다는 점은 논문 당시에는 기능이었지만(전문가가 계층을 탐색한다) 지금은 대체로 부담으로 여겨진다. 자동화 파이프라인에 사람이 그림을 보는 단계를 끼워 넣을 수 없기 때문이고, HDBSCAN이 빠르게 자리를 가져간 이유이기도 하다. ↩

4. 군집화 전반의 문제이기도 하다. 부트스트랩 재표본으로 여러 번 돌려 군집 구조가 얼마나 재현되는지 보는 안정성 기반 검증은 어떤 군집화 알고리즘에도 붙일 수 있고, 붙여 보면 대체로 우리가 발표 자료에 넣던 그림들이 생각보다 흔들린다는 사실을 알게 된다. ↩