DBSCAN이란 무엇인가?
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 '노이즈를 고려한 밀도 기반 공간 클러스터링'을 의미하는 밀도 기반 군집화 알고리즘입니다. 이 알고리즘은 충분히 높은 밀도를 가진 영역을 클러스터로 확장해 나가며, 노이즈가 섞여 있는 공간 데이터베이스에서도 임의의 모양을 가진 클러스터를 찾아냅니다. DBSCAN에서 하나의 클러스터는 밀도 연결(density-connected)된 점들의 최대 집합으로 표현됩니다.
K-평균(K-Means)과 같은 전통적인 군집화 기법이 구형(spherical) 클러스터만 잘 찾는 것과 달리, DBSCAN은 반달형이나 고리형처럼 복잡한 형태의 클러스터도 효과적으로 발견할 수 있다는 강점이 있습니다.
밀도 기반 군집화의 핵심 정의
밀도 기반 군집화를 제대로 이해하려면 다음과 같은 핵심 개념들을 먼저 알아야 합니다.
ε-근방(ε-neighborhood): 주어진 객체를 중심으로 반지름 ε(엡실론) 이내에 있는 이웃 영역을 의미합니다.
핵심 객체(core object): 어떤 객체의 ε-근방에 최소 객체 수(MinPts) 이상의 객체가 포함되어 있다면, 그 객체를 핵심 객체라고 부릅니다.
직접 밀도 도달 가능(directly density-reachable): 객체 집합 D에서 객체 p가 객체 q의 ε-근방 내부에 있고, q가 핵심 객체라면 p는 q로부터 직접 밀도 도달 가능하다고 말합니다.
밀도 도달 가능(density-reachable): 객체 집합 D에서 ε와 MinPts 조건 하에, p₁ = q이고 pₙ = p인 객체 사슬 p₁, ..., pₙ이 존재하고, 각 pi+1이 pi로부터 직접 밀도 도달 가능하다면(1 ≤ i ≤ n, pi ∈ D), 객체 p는 q로부터 밀도 도달 가능하다고 정의합니다.
밀도 연결(density-connected): 객체 집합 D에서 어떤 객체 o ∈ D가 존재하여 p와 q가 모두 o로부터 밀도 도달 가능하다면, p와 q는 밀도 연결되어 있다고 말합니다.
밀도 도달 가능성과 밀도 연결성의 성질
밀도 도달 가능성(density reachability)은 직접 밀도 도달 가능성의 추이적 폐포(transitive closure)이지만, 이 관계는 비대칭적입니다. 즉, 오직 핵심 객체들만이 서로에게 밀도 도달 가능합니다. 반면 밀도 연결성(density connectivity)은 대칭 관계입니다.
밀도 기반 클러스터란 밀도 연결된 객체들의 집합 중 밀도 도달 가능성 측면에서 최대(maximal)인 그룹을 의미합니다. 어떤 클러스터에도 속하지 않는 객체는 모두 노이즈(noise)로 간주됩니다.
DBSCAN의 동작 방식
DBSCAN은 데이터베이스 내 모든 점에 대해 ε-근방을 검사하는 방식으로 클러스터를 찾습니다. 특정 점 p의 ε-근방에 MinPts보다 많은 점이 포함되어 있다면, p를 핵심 객체로 하는 새로운 클러스터가 생성됩니다. 이후 DBSCAN은 이러한 핵심 객체들로부터 직접 밀도 도달 가능한 객체들을 반복적으로 수집하며, 이 과정에서 여러 개의 밀도 도달 가능한 클러스터가 병합될 수도 있습니다. 더 이상 어떤 클러스터에도 새로운 점을 추가할 수 없게 되면 알고리즘은 종료됩니다.
계산 복잡도
공간 인덱스(spatial index)를 사용하는 경우 DBSCAN의 계산 복잡도는 O(n log n)입니다. 여기서 n은 데이터베이스 객체의 수이며, 공간 인덱스를 사용하지 않으면 O(n²)이 됩니다. 사용자가 매개변수 ε와 MinPts를 적절히 설정하면, 이 알고리즘은 임의의 모양을 가진 클러스터를 효율적으로 발견할 수 있습니다.