관련 포스트군집화 비지도 학습 이상 탐지 데이터 마이닝

밀도 기반 군집화(DBSCAN)

•

2026년 10월 25일 발행•2026년 10월 25일 수정

요약

반경 ε 안의 이웃 수로 밀도를 정의해 고밀도 영역을 군집으로 묶고 저밀도 점을 잡음으로 분리하는 군집화 알고리즘

초급

거리 척도와 최근접 이웃 탐색, 군집화의 기본 개념을 이해하고 매개변수가 결과에 미치는 영향을 해석할 수 있어야 한다.

태그

군집화 비지도 학습 이상 탐지 데이터 마이닝

#개념

밀도 기반 군집화(DBSCAN, Density-Based Spatial Clustering of Applications with Noise)는 데이터가 빽빽하게 모인 고밀도 영역을 하나의 군집으로 묶고, 저밀도 영역에 흩어진 점을 잡음으로 분리하는 비지도 학습(Unsupervised Learning) 기반 군집화 알고리즘이다. 1996년 Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu가 KDD 학회에서 발표했으며, 군집 개수를 미리 정하지 않고도 임의 모양의 군집을 찾을 수 있다는 점에서 K-평균 군집화(K-Means Clustering)와 대비된다.

DBSCAN은 "군집이란 주변보다 점의 밀도가 높은 연결된 영역"이라는 직관에서 출발한다. 밀도는 어떤 점을 중심으로 한 일정 반경 안에 이웃이 몇 개 있는지로 측정하며, 이를 위해 두 개의 매개변수만 사용한다. 각 매개변수의 의미는 다음과 같다.

DBSCAN의 매개변수

반경(ε, Epsilon): 한 점의 이웃 범위를 정하는 거리 임계값이다. 점 $p$의 ε-이웃은 $N_\varepsilon(p) = \{q \in D \mid dist(p, q) \le \varepsilon\}$로 정의한다.
최소 이웃 수(MinPts): 한 점이 핵심점이 되기 위해 ε-이웃 안에 있어야 하는 최소 점 개수이다. 일반적으로 자기 자신을 포함하여 세며, scikit-learn에서는 min_samples라는 이름을 쓴다.

두 매개변수가 정해지면 데이터의 모든 점은 이웃의 개수와 위치에 따라 세 가지 유형 중 하나로 분류된다. 이 분류가 군집의 뼈대와 경계, 그리고 잡음을 결정한다.

점의 세 가지 유형

핵심점(Core Point): ε-이웃 안에 MinPts개 이상의 점을 가진 점이다. 즉 $|N_\varepsilon(p)| \ge MinPts$를 만족하며, 군집의 내부를 이룬다.
경계점(Border Point): 스스로는 핵심점 조건을 만족하지 못하지만 어떤 핵심점의 ε-이웃 안에 속한 점이다. 군집의 가장자리를 이루며 군집에는 포함되지만 군집을 확장하지는 않는다.
잡음점(Noise Point): 핵심점도 경계점도 아닌 점이다. 어느 군집에도 속하지 않으며 scikit-learn에서는 레이블 -1로 표시된다.

점들 사이의 연결 관계는 밀도 도달 가능성으로 정의한다. 점 $q$가 핵심점 $p$의 ε-이웃 안에 있으면 $q$는 $p$로부터 직접 밀도 도달 가능(Directly Density-Reachable)하다고 한다. 핵심점들의 사슬 $p_1, \dots, p_n$을 따라 직접 도달이 이어지면 밀도 도달 가능(Density-Reachable)하며, 두 점이 공통의 점으로부터 모두 밀도 도달 가능하면 밀도 연결(Density-Connected)되었다고 한다. 하나의 군집은 서로 밀도 연결된 점들의 최대 집합이다.

알고리즘은 핵심점에서 출발해 밀도 도달 가능한 점을 모두 끌어모으는 방식으로 동작한다. 너비 우선 탐색과 비슷한 구조이며, 전체 절차는 다음과 같다.

알고리즘 절차

1. 점 선택: 아직 방문하지 않은 점 $p$를 하나 고르고 방문 표시를 한다.
2. 영역 질의: $p$의 ε-이웃을 구한다. 이웃 수가 MinPts보다 적으면 $p$를 일단 잡음으로 표시하는데, 이후 다른 핵심점의 이웃으로 발견되면 경계점으로 바뀔 수 있다.
3. 군집 확장: $p$가 핵심점이면 새 군집을 만들고 이웃을 대기열에 넣는다. 대기열에서 꺼낸 점이 핵심점이면 그 이웃도 대기열에 추가하는 과정을 대기열이 빌 때까지 반복한다.
4. 반복: 모든 점을 방문할 때까지 1~3단계를 반복한다. 결과적으로 각 점은 하나의 군집 번호나 잡음 레이블을 갖는다.

계산 비용의 대부분은 각 점마다 한 번씩 수행하는 영역 질의에서 발생한다. 모든 쌍의 거리를 직접 계산하면 시간 복잡도가 $O(n^2)$이며, 원 논문은 R*-트리 같은 공간 인덱스를 쓰면 평균 $O(n \log n)$에 가깝게 줄일 수 있다고 보았다. 다만 Schubert 등(2017)이 지적했듯 ε이 크거나 차원이 높으면 인덱스의 가지치기 효과가 떨어져 최악의 경우 여전히 $O(n^2)$이 된다. scikit-learn은 kd-트리, 볼 트리, 전수 탐색 중 하나를 골라 이웃을 찾는다.

DBSCAN의 가장 큰 장점은 군집의 모양을 가정하지 않는다는 것이다. 초승달, 고리, 길게 휘어진 띠처럼 볼록하지 않은 형태도 밀도만 이어져 있으면 하나의 군집으로 찾아낸다. 또한 이상치를 억지로 가장 가까운 군집에 넣지 않고 잡음으로 따로 분리하므로, 잡음이 섞인 실제 데이터에서 군집 중심이 왜곡되는 문제를 줄인다.

매개변수 선택에는 k-거리 그래프(k-Distance Graph)가 널리 쓰인다. 각 점에서 $k$번째 최근접 이웃까지의 거리를 구해 크기순으로 정렬해 그리면, 거리가 급격히 커지는 무릎(Knee) 지점이 나타나는데 이 값을 ε의 후보로 삼는다. 이때 $k$는 MinPts에 맞추며, 원 논문은 2차원 데이터에서 MinPts=4를 권장했다. 이후 연구에서는 차원이 $d$일 때 MinPts를 $2d$ 정도로 잡고, 잡음이 많거나 데이터가 크면 더 크게 하라는 경험칙이 제시되었다.

DBSCAN의 대표적인 약점은 밀도 차이 문제이다. ε과 MinPts가 데이터 전체에 하나의 전역 밀도 기준으로 적용되기 때문에, 촘촘한 군집과 성긴 군집이 함께 있으면 어느 한쪽을 놓치기 쉽다. ε을 작게 잡으면 성긴 군집이 잡음으로 흩어지고, 크게 잡으면 가까이 붙은 촘촘한 군집들이 하나로 합쳐진다.

거리 척도 선택도 결과에 큰 영향을 준다. 위경도 좌표에는 하버사인(Haversine) 거리, 텍스트나 임베딩 벡터에는 코사인 거리를 쓰는 식으로 데이터에 맞는 척도를 지정할 수 있다. 그러나 차원이 높아지면 점들 사이 거리가 서로 비슷해지는 차원의 저주(Curse of Dimensionality) 때문에 적절한 ε을 찾기 어려워진다. 따라서 고차원 데이터는 주성분 분석(Principal Component Analysis, PCA)이나 임베딩으로 차원을 줄인 뒤 적용하는 경우가 많다.

밀도 차이 문제를 풀기 위한 대표적인 확장이 OPTICS(Ordering Points To Identify the Clustering Structure)이다. 1999년 Ankerst 등이 제안한 이 방법은 각 점의 핵심 거리와 도달 거리를 계산해 점들을 특정 순서로 나열하고, 이를 도달 가능성 플롯(Reachability Plot)으로 시각화한다. 플롯의 골짜기가 군집에 해당하므로 하나의 ε 대신 여러 밀도 수준의 군집 구조를 한 번에 살펴볼 수 있다.

HDBSCAN(Hierarchical DBSCAN)은 2013년 Campello, Moulavi, Sander가 제안한 계층적 확장이다. 상호 도달 거리로 최소 신장 트리를 만들고 모든 ε에 대한 군집 계층을 구성한 뒤, 가장 오래 유지되는 안정적인 군집을 골라 평탄한 결과를 만든다. ε 대신 최소 군집 크기만 정하면 되고 밀도가 서로 다른 군집도 함께 찾을 수 있어, 실무에서는 DBSCAN보다 먼저 시도하는 경우가 늘고 있다. scikit-learn 1.3부터 기본 군집화 모듈에 포함되었다.

K-평균 군집화와 비교하면 두 알고리즘의 성격 차이가 분명하다. K-평균은 군집 수 $k$를 미리 정해야 하고, 군집을 중심점 주변의 볼록한 덩어리로 가정하며, 모든 점을 반드시 어떤 군집에 배정한다. 반면 DBSCAN은 군집 수를 스스로 결정하고 임의 모양을 다루며 잡음을 분리한다. 대신 K-평균은 학습 후 새 데이터를 가장 가까운 중심점에 바로 배정할 수 있지만, DBSCAN은 주어진 데이터 자체를 나누는 방식이라 별도의 예측 함수가 없다.

DBSCAN은 원래 공간 데이터베이스를 위해 고안된 만큼 위치 데이터 분석에서 특히 많이 쓰인다. GPS 궤적에서 사용자가 오래 머문 체류 지점을 찾거나, 배달·택시 호출이 몰리는 수요 핫스팟을 도출하거나, 매장 후보지 주변의 상권을 구분하는 데 활용된다. 위경도에 하버사인 거리를 쓰고 ε을 실제 거리(예: 200m를 지구 반지름으로 나눈 라디안 값)로 지정하면 결과를 직관적으로 해석할 수 있다.

잡음점을 별도로 분리한다는 특성 덕분에 이상 탐지(Anomaly Detection)의 간단한 기준선으로도 활용된다. 결제 기록에서 어떤 정상 패턴 군집에도 속하지 않는 거래, 센서 데이터에서 밀집 운전 구간을 벗어난 측정값, 서버 로그에서 드문 요청 패턴 등을 잡음점으로 걸러낼 수 있다. 다만 DBSCAN의 잡음 판정은 이진적이므로, 이상 정도를 점수로 매겨야 한다면 국소 이상치 계수(LOF)나 HDBSCAN의 이상치 점수를 함께 검토하는 것이 좋다.

실무에서 DBSCAN을 쓸 때는 먼저 특징의 단위를 표준화해야 한다. 거리가 그대로 밀도 판단에 쓰이므로 값의 범위가 큰 특징 하나가 결과를 좌우할 수 있다. 대용량 데이터에서는 거리 행렬을 통째로 만들지 않도록 공간 인덱스를 쓰거나 표본을 추출해 매개변수를 정한 뒤 전체에 적용한다. 군집 품질 평가에는 볼록한 군집을 가정하는 실루엣 계수보다 밀도 기반 지표인 DBCV가 더 적합하며, ε과 MinPts를 바꿔 가며 군집 수와 잡음 비율의 변화를 함께 확인하는 것이 안전하다.

#관련 용어

핵심점

반경 ε 안에 MinPts개 이상의 이웃을 가져 군집의 내부를 이루는 점

밀도 도달 가능성

핵심점들의 사슬을 따라 한 점에서 다른 점으로 이어질 수 있는 관계

k-거리 그래프

각 점의 k번째 최근접 이웃 거리를 정렬해 그려 ε 값을 고르는 데 쓰는 도표

K-평균 군집화

군집 수를 미리 정하고 중심점과의 거리로 데이터를 나누는 군집화 알고리즘

이상 탐지

정상 패턴에서 벗어난 데이터를 찾아내는 기법

차원의 저주

차원이 늘수록 데이터가 희소해지고 거리 기반 방법의 성능이 떨어지는 현상

#직무 연관도

Data Analyst높음

고객·위치·거래 데이터를 군집으로 나누고 잡음점을 해석해 세분화와 이상 징후를 분석

Data Scientist높음

군집 구조 탐색, 이상치 분리, 매개변수 선택과 결과 검증을 통해 비지도 분석 모델을 설계

Data Engineer보통

공간 인덱스와 거리 척도를 고려해 대용량 위치·로그 데이터에 군집화 파이프라인을 구현

#사용 사례

물류전자상거래금융통신제조

개요

밀도 기반 군집화는 군집 수를 모르는 상태에서 임의 모양의 군집을 찾고 잡음을 분리해야 할 때 활용된다. 물류와 통신에서는 위치·이동 데이터의 핫스팟과 체류 지점을 찾고, 금융에서는 정상 거래 군집에서 벗어난 이상 거래를 걸러내며, 제조에서는 센서 데이터의 정상 운전 구간과 이상 측정값을 구분하는 데 사용된다.

사례

배달 플랫폼에서 주문 위치의 위경도에 하버사인 거리를 적용한 DBSCAN을 수행해 주문이 몰리는 수요 핫스팟을 찾고, 어느 핫스팟에도 속하지 않는 외곽 주문은 별도 배차 정책으로 처리한다.